Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1506. Сдача
Сложение и вычитание длинных целых, умножение и деление на короткоеДинамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 24/10/2010 | Региональные отборочные командные соревнования для школьников (H) |
| 16/07/2015 | Практика 1 и 2 курса (3 командное) (H) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0) 
"Я знаю больше двухсот способов сдать сдачу в один доллар и один пенни" – сказал Апу,
отсчитывая сдачу Гомеру с пятерки за конфеты.
"Думаю, даже если использовать монеты всех шести номиналов, количество способов не
может быть больше ста" – ответил Гомер.
Чтобы Гомер смог проверить утверждение Апу, напишите программу, которая определяет
количество способов сдать сдачу монетами заданных номиналов.
Первая строка ввода содержит два целых числа – сумма сдачи `S` (`1\ ≤\ S\ ≤\ 10000`) и
количество различных номиналов монет `N` (`1\ ≤\ N\ ≤\ 10`). В следующей строке `N` различных
целых чисел в диапазоне от 1 до 1000 в порядке возрастания – номиналы монет.
Вывести одно целое число – количество количество способов сдать сдачу монетами заданных номиналов.
Пример ввода
101 6 1 5 10 25 50 100
Пример вывода
293
