В гостинице для жирафов администрация хочет запастись подушками так, чтобы можно было удовлетворить потребности любого своего возможного постояльца. Известно, что жирафам в зависимости от длины их шеи нужно сложить стопку из одной или нескольких подушек толщиной от 1 до 50 дециметров.
Однажды горничная сообщила, что у неё осталось только шесть свободных подушек толщиной 1, 2, 5, 7, 16, 19 дециметров. Несложно заметить, что в сумме они дают 50 дециметров. В гостиницу должен заехать один очень важный жираф, но, к сожалению, длина его шеи администрации не была известна.
Администрация решила заранее определить возможную длину шеи гостя, при которой ему не смогут подобрать набор подушек нужной толщины.
Определите все возможные длины шеи жирафа (от 1 до 50), для которых нельзя подобрать набор подушек среди имеющихся нужной толщины. Каждое значение записывайте в отдельное поле, добавляя их по мере необходимости. Ответы выражайте в дециметрах.
1 Ответ
Для решения данной задачи можно использовать алгоритм, который проверяет все возможные комбинации имеющихся подушек и определяет, для каких длин шеи жирафа невозможно подобрать набор подушек. У нас получился следующий ответ: 4дм, 11дм, 39дм, 46дм