Матч 177, Лестница (Stairs)

Дивизион 2, Уровень 1

Лестница состоит из набора ступенек. Каждая ступенька характеризуется высотой и длиной. Лестница начинается и заканчивается подъемом и выглядит следующим образом:

+........

|

+---+

|

+---+

|

........+

Ступеньки лестницы удовлетворяют следующим условиям:

1. Все высоты ступенек одинаковы (равны одному и тому же целому числу);

2. Все длины ступенек одинаковы (равны одному и тому же целому числу);

3. Высота каждой ступеньки должна быть не больше maxHeight;

4. Длина каждой ступеньки должна быть не меньше minWidth;

Высота всей лестницы равна totalHeight (высота всех ступенек), длина – totalWidth (длина всех ступенек).

Класс: Stairs

Метод: int designs(int maxHeight, int minWidth,

int totalHeight, int totalWidth)

Ограничения: 1 £ maxHeight, minWidth, totalHeight, totalWidth £ 1000.

Вход. Максимально возможная высота ступеньки maxHeight, минимально возможная длина ступеньки minWidth, суммарная высота ступенек totalHeight и суммарная длина ступенек totalWidth.

Выход. Количество разных лестниц, которое можно построить согласно входным данным.

Пример входа

maxHeight	minWidth	totalHeight	totalWidth
22	25	100	100
25	25	60	100
1000	1	600	600

Пример выхода

1

2

6

РЕШЕНИЕ

перебор

Переберем все возможные высоты тупенек i, которые могут изменяться от 1 до maxHeight. Количество подъемов в лестнице равно totalHeight / i, то есть totalHeight должно нацело делиться на i. Число горизонтальных частей в лестнице на 1 меньше числа подъемов и равно cnt = totalHeight / i – 1. Длина ступенек является натуральным числом (totalWidth должно делиться на cnt), а также быть не меньшей minWidth. Если для очередной высоты i все указанные условия выполняются, то лестница с подъемом ступенек i существует. В переменной res подсчитываем количество таких лестниц.

ПРОГРАММА

#include <stdio.h>

class Stairs

{

public:

int designs(int maxHeight, int minWidth, int totalHeight, int totalWidth)

{

int i, cnt, res = 0;

for(i = 1; i <= maxHeight; i++)

{

if(totalHeight % i) continue;

cnt = totalHeight / i - 1;

if(cnt == 0 || totalWidth % cnt || totalWidth / cnt < minWidth)

continue;

res++;

}

return res;

}

};