Pull to refresh

Олимпиадное хобби. Размен монет

Reading time 5 min
Views 68K
Размен монет Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта http://uva.onlinejudge.org/. Сегодня нам предстоит решить задачу о размене монет из области динамического программирования. Задача не очень сложная, но есть над чем поразмыслить, поэтому заинтересовавшихся прошу под кат. К слову, это третья наша задача, но, безусловно, из всех самая интересная.

Небольшое лирическое отступление.

Мой программистский путь начался далеко не в 3 года, когда многие будущие программисты уже разбирали калькулятор и делали из него компьютер. Я начал заниматься программированием в школе в 8 классе. К слову сказать, моя школа была далека от технического направления, поэтому в своих начинаниях я был почти одинок. Но, благодаря директору нашей школы, у нас был «кружок» по программированию, где мы готовились к школьной олимпиаде по программированию. Нас там было не более трех человек единовременно, но нашего преподавателя, к счастью, это не расстраивало. Моим преподавателем программирования был Кавокин А.А., отчасти благодаря ему я и встал на столь удивительный путь программиста. Так вот, каждый урок наш наставник начинал с логической задачки, чтобы мы расшевелили свои извилины. Это мне настолько нравилось в школе, что я решил вас тоже так помучить, поэтому сегодня мы начнем с небольшой логической задачки, которая поможет нам размяться.

Логическая задачка для разминки:
В нашем городе проезд в общественном транспорте оплачивается непосредственно во время поездки, для чего по автобусу курсирует кондуктор, собирая со всех плату за проезд. Стоимость билета составляет 20 рублей. Однажды, на одной из остановок в автобус зашли 5 человек. Один из них молча заплатил кондуктору 100 рублей, и тот, не задавая никаких вопросов, отсчитал 5 билетов и отдал платившему. Вопрос: как кондуктор догадался, что оплата происходит сразу за всех пятерых, при условии, что ничто не указывало на то, что все они были вместе?
Позволю оставить задачу без ответа, потому что уверен в вашей сообразительности. А как только в комментариях появится правильный ответ, сразу вынесу ссылку сюда.
UPD: Ответ найден в комментарии пользователя ogra

Условие

Надеюсь задачка, которую я вам подкинул для разогрева, успешно подействует на вашу мозговую активность. Сейчас мы, наконец-то займемся решением олимпиадной задачи. Наша сегодняшняя задача — это задача о размене монет.

Краткий перевод условия задачи
После закупки в большом универмаге Мелу досталась сдача в размере 17 центов. Он получил одну десятицентовую монету, одну пятицентовую и 2 монеты по 1 центу. Позже, в этот же день, он делал покупки в мини-маркете, где тоже получил сдачу в размере 17 центов. На этот раз он получил две монеты по 5 центов и 7 монет по 1 центу. Тогда Мел задался вопросом: «Как много магазинов я могу посетить и получить сдачу в 17 центов различным набором монет?» После небольшого мозгового штурма, он определил, что ответ 6. Тогда он бросил вызов вам для решения более общего случая.

Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму.

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

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

Пример:
Input:
17
11
4

Output:
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.

Как обычно, рекомендую вам самим попытаться решить задачу. А как только решите, возвращайтесь к нам и хвастайтесь своим результатом.

Итак, приступим…
Решение

Задача явно из области динамического программирования, а такие задачи, как правило, решаются с помощью рекурсивных зависимостей. Нам необходимо определить, какая именно рекурсивная зависимость в нашем случае.

Можно сразу заметить, что число комбинаций не отличается при сдаче от 1 цента до 4 — это 1 вариант, при сдаче от 5 центов до 9 — это 2 варианта, при сдаче от 10 центов до 14 — это 4 варианта и т.д. Это происходит потому, что внутри такой «пятерки» монеты достоинством в 1 цент невозможно ничем заменить. Таким образом мы определили, что решать задачу для каждого числа бессмысленно, поэтому мы будем решать ее для каждой «пятерки».

Также можно заметить, комбинации для каждой следующей «пятерки» точно повторяют комбинации предыдущей «пятерки» (с добавлением в конец комбинации нужного числа монет по 1 центу) и некоторого числа новых комбинаций. Становится понятным, что число комбинаций следующей «пятерки» имеет зависимость от числа комбинаций предыдущих «пятерок». Нарисуем таблицу, где столбцами будут «пятерки», а строками виды монет, а на пресечении будет определяться, какое количество новых комбинаций породил данных вид монет ( в комбинации со всеми более мелкими) на конкретном шаге — «пятерке»:
  10 15 20 25 30 35 40 45 50 55                                                                      
1 1 0 0 0 0 0 0 0 0 0 0 0
5 0 1 1 1 1 1 1 1 1 1 1 1
10 0 0 1 1 2 2 3 3 4 4 5 5
25 0 0 0 0 0 1 1 2 2 3 4 5
50 0 0 0 0 0 0 0 0 0 0 1 1
1 2 4 6 9 13 18 24 31 39 50 62
В последней строке выведено число комбинаций на данной «пятерке»
К примеру: на шаге 35 (8 пятерка: 35-39)
имея только 1 центовую монету, новых комбинаций не появляется,
из монет 1 цент и 5 центов, можно выдумать 1 новую комбинацию: 5+5+5+5+5+5+5+1(от 0 до 4)
1 цент, 5 центов, 10 центов — 3 комбинации: 10+10+10+5+1(от 0 до 4), 10+10+5+5+5+1, 10+5*5+1
1, 5, 10, 25 — 2 новых комбинации: 25+10+1, 25+5+5+1

Число новых комбинаций на каждом шаге из монет 1 цент и 5 центов равняется 1, потому что это комбинация порождается добавлением 5 центовой монеты к предыдущей комбинации. Т.е. для второй пятерки 5+1, потом 5+5+1, потом 5+5+5+1 и т.д., по 1 новой комбинации на каждом шаге.
Также в этой таблице не трудно углядеть рекурсивную зависимость: число новых комбинаций на шаге i, составленных из монет 1-10 равняется числу новых комбинаций из монет 1-5 на шаге i-1 плюс число новых комбинаций из монет 1-10 на шаге i-2 (когда у нас в распоряжении было на 1 десятицентовую монету меньше). Аналогично для 25-ти центовой монеты и 50-ти центовой монеты.

В итоге мы имеем 2 формулы и 3 рекурсивных зависимости:
N(1, i) = 0, кроме N(1, 0) = 1
N(5, i) = 1
N(10, i) = N(5, i-1) + N(10, i-2)
N(25, i) = N(10, i-3) + N(25, i-5)
N(50, i) = N(25, i-5) + N(50, i-10)
S(i) = S(i-1) + N(1, i) + N(5, i) + N(10, i) + N(25, i) + N(50, i)
Где N — это матрица, определенная выше, а S — искомое число комбинаций.

Теперь нам остается лишь просчитать нужное число шагов от начала до запрашиваемой «пятерки», подсчитывая на каждом шаге общее число комбинаций (S). Учитывая тот факт, что тестов в задаче будет много, можно использовать для новых тестов, ранее просчитанный кусок матрицы и дополнять лишь ее недостающую часть. Еще очень важно понимать, что при максимальной сумме, заданной условием задачи: 30000 центов, суммарное число комбинаций перевалит за пределы int и даже long, поэтому для подсчета числа комбинаций рекомендую использовать 8 байтовые беззнаковые переменные.

Полагаю, что есть более изящное решение, чем предложенное выше, но я его пока не вижу, поэтому жду от вас интересных алгоритмов. Мое решение на C++ можно скачать тут. Проверить правильность своего решения можно здесь (требуется регистрация). Удачи, господа!

Accepted (0.024)
Tags:
Hubs:
+27
Comments 89
Comments Comments 89

Articles