2595. Стена

Василий Пупкин решил переклеить обои на стене размером n метров в высоту и m метров в ширину. Как известно, обои продаются рулонами шириной в 1 метр и длиной k метров. Их клеят на стену вертикально – от потолка до пола. Василий так хочет наклеить обои, чтобы не было горизонтальных стыков, сплошными полосами (то есть один сплошной кусок клеится от потолка до пола). От рулона можно отрезать кусок нужного размера. Конечно, если останется кусок меньшего размера, он уйдет в отходы. Какое наименьшее количество рулонов следует покупать Василию и сколько метров обоев при этом уйдет в отходы?

Вход. Три целых числа n, m и k (1 ≤ n ≤ 100, 1 ≤ m ≤ 100, n ≤ k ≤ 100).

Выход. Выведите два числа – минимальное количество рулонов и общую длину обоев, которые ушли в отходы.

Пример входа	Пример выхода
6 7 20	3 18

РЕШЕНИЕ

математика

Анализ алгоритма

Длина одного рулона k метров, высота стены n метров. Следовательно одного рулона хватит на lines = полос. Для поклейки стены шириной m метров достаточно rolls = рулонов.

От одного рулона останется остаток в k % n метров. Из rolls рулонов, необходимых для поклейки стены, rolls – 1 рулонов будет использовано полностью, а последний рулон, возможно, будет использован не весь. Следовательно от rolls – 1 рулонов в отходы пойдет (k % n) * (rolls – 1) метров обоев.

Последним рулоном следует покрыть p = m – lines * (rolls – 1) полных полос. Следовательно отходы от него составят k – p * n метров.

Реализация алгоритма

Читаем входные данные.

scanf("%d %d %d",&n,&m,&k);

Вычисляем на сколько вертикальных полос хватит одного рулона.

lines = k / n;

Вычисляем количество использованных рулонов: = (m + lines – 1) / lines.

rolls = (m + lines - 1) / lines;

Находим остаток от одного рулона при полной поклейке.

waste = k % n;

Находим остаток от полностью использованных rolls – 1 рулонов.

waste *= (rolls - 1);

Последний рулон может быть использован как полностью, так и нет. Вычисляем количество вертикальных полос, покрытых последним рулоном.

p = m - lines * (rolls - 1);

Добавим отходы от последнего рулона.

waste += k - p * n;

Выводим ответ.

printf("%d %d\n",rolls,waste);