Числа и ввод · 36 из 37
Вагонка без распилов
Стену обшивают вагонкой встык, доски двух длин. Пилить Валерий Степанович отказывается наотрез: «Каждый распил — минус доска и плюс опилки в заказчице». Значит, длину стены надо набрать целыми досками, и досок — как можно меньше.
Стены бывают и в кабинке душа, и вдоль забора на километр.
Что сделать
Наберите длину стены целыми досками двух длин — без распилов и как можно меньшим их числом.
Что приходит
stena— длина стены в миллиметрах, целое от 0aиb— длины досок в миллиметрах; досок каждой длины сколько угодно
Что вернуть
Наименьшее число досок, которые встык дают ровно stena, — или -1, если без распила не выйти.
Допишите функцию doski в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Стена 330 мм, доски 90 и 120: две по 120 и одна 90 дают ровно 330 — ответ 3. Из одних досок по 90 не выйти вовсе: 330 на 90 не делится.
doski(330, 90, 120)
3
Все длины — целые, в миллиметрах. Длина стены — от 0 до 10¹⁵, длины досок — от 1 до 10⁶, могут совпадать. Нужно найти неотрицательные целые x и y с x·a + y·b = длина стены и наименьшей суммой x + y. Ноль досок на стену нулевой длины — ответ 0. На самых больших числах ответ нужен за доли секунды.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.