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

    Размен монет Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта 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)
    Поделиться публикацией

    Комментарии 89

      +2
      В 9 или 10 классе на олимпиаде мне эта задача мозг выела, не решил (((
        –2
        Была, кстати, задачка с конем на шахматной доске, его нужно было доставить в точку. Я последние шаги рандомом загонял в точку, ржачно было, когда у меня приняли это задание.
          +1
          я такую рекурсией решал… хорошая задачка)
            0
            Очень не сложная задачка, алгоритм поиска очень простой: Начиная от начальной точки помечаете не помеченные клетки доски, в которые можно добраться в 1 шаг цифрой 1, потом все клетки, в которые можно добраться конем из клеток с цифрой 1 помечаете цифрой 2 и т.д. В итоге получаете доску с размеченным числом шагов до любой клетки. По этим цифрам несложно было пройти путь обратно от конечной точки до начальной.
              0
              не работает для бесконечной доски (да и для больших размеров, порядка 10^5 x 10^5 уже тоже не пройдёт). для этого обычно доводят до шара определённого радиуса, а в нём уже решают задачу для небольшой доски (тут уже ваш поиск в ширину сгодится)
                +1
                В школе не было бесконечной доски. Но ваше замечание очень кстати, я даже не задумывался о бесконечных досках…
                  +1
                  А как формулируется эта задача для бесконечной доски?
                0
                Тоже решал рекурсией, на C вышло примерно 25 строк. Но мозга я поломал много.
                  0
                  Похожая задачка с конем была в виде: пройти конем всю шахмотную доску… там и алгоритм на ето был, и рекурся не понадобилась.
                    0
                    Если я правильно понимаю условие (найти путь с наименьшим числом ходов), то решать следует так:
                    0) Текущая точка = стартовая точка.
                    1) Если расстояние до конечной точки <= 4, переходим к шагу 5.
                    2) Выпустим 8 лучей из текущей точки, чтобы все возможные ходы коня приходился на различные части плоскости (разделенными нашими лучами).
                    3) Проанализируем, в какой из частей плоскости находится конечная точка.
                    4) Делаем ход в соответствующем направлении, переходим к шагу 1.
                    5) Рисуем квадрат — и поиском в ширину находим кратчайший путь.
                      0
                      Я знаю, что я могу сделать задания, меня всегда напрягало ограничение по времени. Я потом приходил домой и спокойно всё делал. Мне надо посидеть в тишине, чтоб никого не было вокруг, задуматься и вуаля всё как по маслу. Я так после олимпиад по информатике делал, расстраивался. Потом вступительные по математике завалил на 3, домой пришел быстро всё сделал.
                    +1
                    такая же ситуация :) решил самую сложную, а потом на 4 оставшиеся простенькие никак не смог мозг перестроить. еще помню как на олимпиаде по физике у меня напрочь выпало слово «конденсируется» и я долго парился потом так судьям и сказал «я слово забыл но не концентрируется а както по другому» :)
                    +3
                    Пост очень хорошо написан, читать интересно и занимательно, но мне кажется, что задачи, которые вы разбираете, ну уж очень очевидны. Я думаю, что стоит попробовать увеличить сложность задач.

                    P.S. Посмотрел ваш код. На мой взгляд у вас слишком много магических констант да и вообще код плохо читается. В подобных задачах принято заводить массив значений номиналов монет (массы грузов, стоимости товаров, etc) и писать более логичный код с двумя циклами.

                    Желаю удачи!
                      0
                      Благодарю.
                      Магические константы и не совсем логичный код сделаны специально, чтобы ускорить работу алгоритма. Тем более, что с C++ я, мягко говоря, почти не знаком и изучаю его параллельно со своим хобби. Но я обещаю совершенствоваться со временем. Кстати, отмечу что эта задача не такая уж и очевидная, во всяком случае для меня.
                        +5
                        Я бы решал эту задачу (как мне кажется) проще, без поиска каких-либо закономерностей. Состояние нашей динамики d[i][j] — количество способов набрать сумму в j центов, если максимальная монета в наборе имеет i-ый номинал (i=0, 1, 2, 3, 4 соответствуют монетам в v[i]=1, 5, 10, 25, 50 центов). Хранение максимального номинала позволяет нам делать переходы из состояния d[i][j] в состояния d[i][j + v[0]], d[i + 1][j + v[1]], d[i + 2][j + v[2]]...: мы просто делаем новый набор из старого «докидыванием» монет в порядке неубывания (мы не можем кинуть сначала 1 цент, потом 5 центов, а потом еще 1 цент — иначе мы так второй раз посчитаем комбинацию 1+1+5).

                        Итак — ставим в массиве d[5][30001] начальное значение d[0][0]=1 и двигаемся вперед, постепенно заполняя все элементы массива. На каждой итерации делаем примерно 5 переходов, итоговое асимптотическое время работы: 5*5*30000 = 7,5*10^5, для олимпиадных задач этого хватает с огромным запасом. Чтобы узнать ответ для конкретного n, суммируем все 5 значений в n-ом столбце (∑d[i][n], i=0..4).

                        К сожалению, под рукой нет ни одного подходящего компилятора, поэтому код писал в блокноте. Прошло со второго раза (был WA из-за опечатки — вместо ans в конце набрал сначала n). 0.028 секунды.
                          +2
                          А, да, сам код:

                          #include <iostream>
                          
                          using namespace std;
                          
                          int main(int argc, char **argv)
                          {
                          	int v[5];
                          	v[0] = 1;
                          	v[1] = 5;
                          	v[2] = 10;
                          	v[3] = 25;
                          	v[4] = 50;
                          
                          	unsigned long long d[5][30001];
                          	for (int i = 0; i < 5; i++)
                          		for (int j = 0; j < 30001; j++)
                          			d[i][j] = 0;
                          	d[0][0] = 1;
                          
                          	for (int i = 0; i < 30000; i++)
                          		for (int j = 0; j < 5; j++)
                          			for (int k = j; k < 5; k++)
                          				if (i + v[k] <= 30000)
                          					d[k][i + v[k]] += d[j][i];
                          
                          	int n;
                          	
                          	while (cin >> n) {
                          		unsigned long long ans = 0;
                          		for (int i = 0; i < 5; i++)
                          			ans += d[i][n];
                          		
                          		if (ans > 1)
                          			cout << "There are " << ans << " ways to produce " << n << " cents change.\n";
                          		else
                          			cout << "There is only 1 way to produce " << n << " cents change.\n";
                          	}
                          	
                          	return 0;
                          }
                          
                            0
                            Спасибо за решение!

                            Но вот это смутило.
                            0
                            There is only 1 way to produce 0 cents change

                            Разве не так должно быть?
                            0
                            There are 0 ways to produce 0 cents change
                              +1
                              В данной задаче (как и во многих других), более естественно считать, что нулевую сумму набрать можно всегда, причем единственным способом.

                              Представлять себе это можно примерно так: у вас просят 0 центов, а вы не разводите руками в ответ, а гордо протягиваете пустую ладонь :)

                              В общем, набор из пустого множества монет — тоже набор, и его сумма как раз равно нулю, то есть он засчитывается.
                                0
                                а, спасибо.
                                а гордо протягиваете пустую ладонь

                                большой палец вверх
                            0
                            Да, мне тоже кажется, что автор перемудрил с решением.

                            Ваше более понятно, хотя я бы использовал дп «назад», а не вперед, так проще перевести рекуррентную формулу в дп.

                            Также тут количество операций в пять раз больше, чем достаточно.

                            Собственно формула: Тогда f(t, n) = f(t, n — v[t]) + f(t — 1, n)

                            Ну или если пользоваться вашей терминологией, то делать переходы из d[i][j] в d[i + 1][j] и d[i][j + v[i]]

                            Ну а если дп «назад»:
                            База: dp[0][i] = 1
                            Переход: dp[i][j] = dp[i — 1][j] + dp[i][j — v[i]] (в реальном коде понадобится добавить проверку на выход j — v[i] за пределы массива)

                            При этом d[i][j] будет означать количество способов набрать сумму в j центов, если максимальная монета в наборе имеет не более, чем i-ый номинал.
                            И собственно d[i][n] будет ответом.
                          0
                          А вы пробовали эту задачу решать? да так, чтобы она прошла на сайте?
                          ==
                          Я тоже сначала массив констант (номиналы монет) заводил, и не прошло ограничение по времени.
                          Потом думал 2 дня и упростил решение. Сделал магические числа, и всё равно не прошло.

                          по времени выполнения не прошло. нужно 3 секунды.
                          ==
                          Повторюсь: А вы пробовали эту задачу решать? да так, чтобы она прошла на сайте?
                          +12
                          Попробую дать ответ на логическую задачу:
                          Он дал деньги десятками ;)
                            +1
                            Вы молодец, даю ссылку на вас в посте.
                              0
                              Еще вариант, если они глухонемые и общаются жестами, а деньги протянул только один. Тогда тоже можно молча.
                                0
                                Кондуктор тоже глухонемой? :)
                                  0
                                  Необязательно быть глухонемым, чтобы понимать язык жестов :) Хотите задачку в тему?

                                  В аудитории идет экзамен. Сидят студенты, за кафедрой сидит преподаватель. Вдруг неожиданно один встает, ни говоря ни слова, подходит к преподавателю с зачеткой, получает «отлично» и выходит. Никакого листочка или любой другой письменной работы студент не сдавал. Вопрос — по какому предмету экзамен? Можно даже предположить сферу знаний, преподаваемую в вузе.
                                    +1
                                    Препод азбукой морзе настучал, что первый, кто подойдет, получит отлично автоматом.
                            0
                            среднестатистический кондуктор все равно спросил бы: «сколько с этой стопки десяток?» :)
                            –2
                            на логическую задачу…

                            кондуктор видел, что деньги протягивает только один, а остальные 0 внимания, следовательно, они вместе
                              +5
                              Угу, таких вариантов можно много придумать:
                              — кондуктор знал их в лицо, они всегда входят вместе и платит один
                              — это были отец и 4 маленьких ребенка
                              — плативший и кондуктор молчали, но еще один из вошедших сказал: «за всех»
                              — и т.д.
                                +1
                                — они все были близнецы.
                                  +1
                                  -> что ничто не указывало на то, что все они были вместе?
                                    0
                                    Прочитайте выше и поймете, что я забыл тег [irony]
                              0
                              Если интересен сей вопрос, то советую глянуть ТУТ ...
                              Ооочень много интересных задачек.
                                0
                                По большому счету, не важно с какого сайта брать задачи. Только тем, кто готовится к ACM, лучше решать задачи на английском языке
                                • НЛО прилетело и опубликовало эту надпись здесь
                                +3
                                По поводу первой — он расплатился комбинацией купюр, позволявшей без сдачи с меньшей итоговой суммой оплатить за 1,2,3 и 4 человек (например, дал стопку по рублю)

                                А вторая задача была бы интересной, если бы номиналы монет были не в условии а задавались как входные параметры (например, достоинством, противоречащим логике)
                                  0
                                  Не успел первым ответить на логическую задачу, но второй моей догадкой как раз стало то, что он расплатился десятью купюрами по десять рублей, что как раз намекает на то, что сдачи он не ждет, так как билет стоит двадцать, и платит за всех.
                                    0
                                    А можно это написать красиво в функциональном стиле в одну строчку?
                                      0
                                      pastebin.com/qYEr5Zfh
                                      Забыл ссылку на императивный вариант на python
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                          0
                                          Нет. Для 6 найдет способы 1+5 и 1+1+1+1+1+1.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                      0
                                      Мне кажется, вы всё усложняете. Рекуррентное соотношение должно быть проще:
                                      C(i) — достоинство монеты i. C отсортирован в порядке возрастания.
                                      С = {1,5,10,25,50} для нашего случая.

                                      N (i, S) — количество разложений суммы денег S монетами достоинством от С(0) до C(i) включительно.

                                      N(i,0) = 1 для любого i

                                      N(i, k) = N( i-1, k — C(i) ) + N (i, k — C(i) ) (следует учитывать, что если индекс лежит за границами массива, значение равно 0)

                                      Таким образом видим, что при каждой итерации используются только значения, полученные на текущей итерации и значения предыдущей итерации,
                                      что позволяет нам хранить только две строки условной матрицы.
                                        0
                                        Зато при хранении всей матрицы не нужно пересчитывать динамику целиком для каждого теста во входном файле — достаточно посчитать ее один раз.
                                          0
                                          Если я правильно понял условие задачи, то для входных тестов достоинства монет не изменяются, изменяется только общая сумма, которую требуется разложить. Матрица нужна только в случае, если нужно хранить разложения для подмножеств монет.
                                            0
                                            Да, верно — в принципе, достаточно хранить только массив ans[i], содержащий ответы для каждой из строк исходной матрицы.

                                            Хотя это и не сильно отличается от хранения всей матрицы — учитывая, что в каждой строке всего 5 элементов :)
                                              0
                                              Если решать задачу для более общего случая с M монет, тогда использование памяти станет более критичным.
                                          0
                                          Поторопился. Уточнение:
                                          N(i, k) = N(i-1, k) + N (i, k-C(i) ),
                                          То есть, количество разложений, когда мы используем монету C(i)-го достоинства (не менее одного раза) + количество разложений, когда мы монету С(i)-го достоинства не использовали ни разу.
                                            0
                                            Пересчёт можно вести в единственном массиве. =)
                                              0
                                              Да, это больше на правду похоже:

                                              N(i, S) = N(i-1, S) + N(i-1, S — Ci)

                                              Кол-во наборов той же суммы без монет Ci.
                                              Плюс кол-во набором с хотя бы одной монетой.

                                              На JavaScript:

                                              <script>

                                              var C = [ 1,5,10,25,50 ];

                                              function N(S, i) {
                                              if (i === undefined) i = C.length - 1;
                                              if (S < 0 || i < 0) return 0;
                                              if (S == 0 || i == 0) return 1;
                                              return N(S, i - 1) + N(S - C[i], i);
                                              }

                                              var a = parseInt(prompt("Сумма?", 17));
                                              alert('Кол-во вариантов: ' + N(a));
                                              </script>

                                                0
                                                Ну и немного исследований.

                                                Добавление 2-х центовой монеты к набору монет {1,5,10,25,50}, как и ожидалось, резко увеличивает число вариантов.

                                                Кол-во вариантов:
                                                для 17 центов стало 28 (для набора без 2-х центовой монеты было — 6)
                                                для 100 центов стало 3953 (для набора без 2-х центовой монеты было 292)

                                                :-)
                                                0
                                                О каком массиве идет речь, не понимаю… Зачем нужен?
                                                  0
                                                  Чтобы не пересчитывать уже посчитанные ранее результаты — суть динамического программирования.
                                                    0
                                                    Динамическая версия :-)

                                                    <script>

                                                    var M = {}, C = [ 1,5,10,25,50 ];

                                                    function N(S, i) {
                                                    if (i === undefined) i = C.length - 1;
                                                    if (S < 0 || i < 0) return 0;
                                                    if (S == 0 || i == 0) return 1;
                                                    var k = S + '@' + i;
                                                    M[k] = M[k] || N(S, i - 1) + N(S - C[i], i);
                                                    return M[k];
                                                    }

                                                    var a = parseInt(prompt("Сумма?", 17));
                                                    alert('Кол-во вариантов: ' + N(a));

                                                    </script>

                                                      0
                                                      Как-то Вы всё усложняете. Рекурсия тут вообще не нужна.
                                                      Заполнение массива:

                                                      S = 100;
                                                      var C=[1,5,10,25,50];
                                                      var N = {};
                                                      for (i=0;i<S;i++) N[i]=0;
                                                      
                                                      for (i=0;i<C.length;i++)
                                                      {
                                                        N[0] = 1;
                                                        for (j=1;j<S;j++)
                                                        {
                                                             	if (j-C[i] >=0)  N[j] += N[j-C[i]];
                                                        }
                                                      }
                                                      
                                                        0
                                                        Рекурсия позволяет вычислять только те промежуточные суммы, которые необходимы.

                                                        Ваш пример посчитает все подряд.

                                                        Например, для S = 1000 кол-во промежуточных сумм будет равно 458, то есть экономия на вычислениях превышает 50%.

                                                        <script>

                                                        var M = {}, C = [ 1,5,10,25,50 ];

                                                        function N(S, i) {
                                                        if (i === undefined) i = C.length - 1;
                                                        if (S < 0 || i < 0) return 0;
                                                        if (S == 0 || i == 0) return 1;
                                                        var k = S + '@' + i;
                                                        M[k] = M[k] || N(S, i - 1) + N(S - C[i], i);
                                                        return M[k];
                                                        }

                                                        var a = parseInt(prompt("Сумма?", 100));
                                                        alert('Кол-во вариантов: ' + N(a));

                                                        var Z = 0;
                                                        for (var i in M) Z++;

                                                        alert('Кол-во промежуточных сумм: ' + Z);

                                                        </script>

                                                          0
                                                          Вы считаете, что Ваше решение «экономное»?
                                                          Просто пара замечаний:
                                                          Вы используете поиск по ассоциативному массиву с текстовым (!) ключом. Даже если рассматривать реализацию его в виде хеш-таблицы всё равно это не единичное время доступа.
                                                          Вызов функции всегда сопряжён с накладными расходами. Особенно, когда Вы используете рекурсию и не хвостовую.
                                                          Мелочи, вроде конкатенации строк и преобразования чисел в строку также далеко не дешёвые.

                                                          Итого, если считать, что поиск в массиве по текстовому ключу занимает O(1), то асимптотическая оценка наших реализаций будет одинакова O(C*S). Но, очевидно, Ваше решение в данном виде проигрывает по эффективности. Если у Вас есть лишнее время, можете попробовать потестировать на больших числах и множестве тестов.
                                                            0
                                                            Смысл второго листинга не в максимальном быстродействии для _одного_ вычисления. А в том, что повторные вызовы функции N() будут использовать предыдущие вычисления. То есть максимальное быстродействие для ряда вычислений.

                                                            Для поиска в хеше я просто воспользовался удобствами JavaScript. Вместо хеша можно использовать массив, заполненный нулями. И обращаться по индексу, который вычисляется из i и S. Это будет занимать O(N).
                                                              0
                                                              Рискую показаться занудой, но тем не менее.
                                                              Рекурсивное решение в данном случае может отработать быстрее в случае, если у нас один тест (нужно посчитать количество вариантов для одной суммы). Но в этом случае вам придётся использовать не массив, как вы пишете, а матрицу C×S (массив размера C*S, что то же), или же вернуться к хеш-таблице.
                                              0
                                              Что-то не верится в ваше рекурсивное соотношение… Не поясните, как получилось?
                                                +1
                                                У меня чуть выше получились практически те же формулы (разве что направление динамики другое — не назад, а вперед).

                                                Все тут правильно (ну, с учетом поправки).
                                              –2
                                              я б такую задачу решил тупо перебором.
                                              на современных скоростях даже глазом не успеешь моргнуть как она все переберет, по 1000 раз лишних операций сделает и выдаст ответ так же быстро как и ваша.
                                                0
                                                Суть в том, чтобы мозги развивать. :)
                                                  +1
                                                  Число комбинаций, как говорит автор статьи, не укладывается в восьмибайтовый long long. Вы уверены, что вы всех их успеете за три секунды перебрать?

                                                  Подсказка: рассчитывать следует примерно на 108 операций в секунду на тестирующем сервере.
                                                    0
                                                    30000 можно получить 543065523200 способами, если точно.
                                                      0
                                                      Может 543427145501?
                                                        0
                                                        Да. Выше даже есть мой код, с глупой ошибкой)
                                                        PS. Некропостинг в массы?)
                                                    +1
                                                    1. Что вы собираетесь перебирать? Все способы?
                                                    Это едва ли проще, и работать будет, как говорится, O(∞)
                                                    2. У «тупого» решения будет хуже ассимптотика, причем существенно. То есть не составит труда задать ограничения, на которых нормальное решение работает быстро, а «тупое» — дольше любых разумных ограничений.
                                                      0
                                                      ладно дома найду трубопаскаль и засеку время за которое он переберет все варианты для набора суммы в 30,000 центов.
                                                        +1
                                                        Боюсь, что к тому времени, как это досчитается, про этот топик (а скорее всего — и вообще про хабрахабр) все давно забудут.
                                                        Поэтому, пожалуйста, напишите сначала время для 8000 (их «всего» 2796029201 вариантов).
                                                          0
                                                          я всетаки скачал борланд паскаль на работе
                                                          и забубенил 5 вложенных циклов :)
                                                          dl.dropbox.com/u/930263/habr/for.jpg
                                                          и так на двухядерном цилероне
                                                          время расчета для 1000 центов = 1 минута 32 секунды
                                                          значение 15019 вариантов
                                                          Прикинем сейчас 00:01:32/15019*2796029201=05:34:45
                                                          :)
                                                          Всего то 5,5 часов :)
                                                            0
                                                            Для 1000 ответ будет 801451.
                                                              0
                                                              да, лажанул, забыл что integer гораздо меньше :)
                                                              0
                                                              В паскале integer 16битный. Так что считает неправильно. Ну да ладно.
                                                              Для 30000 будет считать в 678054 раза дольше, т.е. чуть меньше двух лет. Так что про сроки я немного загнул, про хабр помнить еще будут. Но по таймлимиту не проходит даже близко.
                                                      0
                                                      Только мне показалось, что количество комбинаций для 17 центов неправильное? Может условие неполное…

                                                      1) 10+5+2
                                                      2) 10+5+1+1
                                                      3) 10+2+2+2+1
                                                      4) 10+2+2+1+1+1
                                                      5) 10+2+1+1+1+1+1
                                                      6) 10+1+1+1+1+1+1+1
                                                      7) 5+5+5+2
                                                      … и так далее
                                                        0
                                                        А монеты в 2 цента то у вас откуда появились?
                                                          0
                                                          Просто двухцентовых монет нету :)
                                                            +1
                                                            Упс, проглядел :) Спасибо.
                                                          0
                                                          Уже второй раз читаю ваши статьи и немножечко поражаюсь. Я занимаюсь олимпиадным программированием достаточно долго и привык что у задачи есть ограничения. «The input will consist of a set of numbers between 0 and 30000 inclusive, one per line in the input file.» — весь формат входного файла, и обозначает что в файле может быть бесконечность строк. Конечно можно догадаться что количество строк > 30000 скорее всего не будет, а если задача лежит в теме «Dynamic Programming», а не перебор (что первое приходит в голову любому олимпиадному программисту) и ограничение три секунды, то скорее всего нам придётся ответить на все 30000 запросов. Но вот такое догадаться — это ужасно. Против вашей стати я ничего не имею, она хороша, но этот UVa Online Judje меня как-то раздражает.

                                                          На вашем месте я бы использовал acm.timus.ru/ ну или informatics.mccme.ru/ вот.

                                                          И кстати по задаче. На реальной олимпиаде заметив бы эту задачу я бы за пять минут написал перебор для всех значений, который бы сгенерил мне константный массивчик ответов, и сдал бы вот так хитро. Это быстрее чем придумывать динамику, и генериться оно будет не так уж и долго. Так что и задачка не очень то олимпиадная, в реальности редко дают задачи решаемые прегенерацией.
                                                            0
                                                            Перебираться оно будет почти вечность. 543 427 145 501 способами можно набрать 30000. Успеете это сгенерировать за отведенное на раунд время?)
                                                            Задача простая, для человека, хоть сколько-нибудь занимавшийся олимпиадным программированием, как писать здесь динамику — очевидно.
                                                              0
                                                              Простая, но перебор почти всегда писать легче =). Да, вы правы, даже со всякими эвристиками оно не переберётся.
                                                                0
                                                                Именно что «почти». В этом случае, как мне кажется, это не так.
                                                                И почти всегда перебор не посчитается ни за какое разумное время.
                                                                  0
                                                                  Каждому своё. Я перебор почти что с закрытыми глазами пишу, а с динамическим программированием, по правде говоря не сильно дружу.
                                                                  На тех олимпиадах которые я удосуживался писать, обычно одна-две задачи решались перебором (или их было возможно решить перебором). В прикладном программировании конечно перебором злоупотреблять не стоит.
                                                          +2
                                                          За всю жизнь решил две-три олимпиадные задачи, а что такое динамическое программирование, узнал сегодня (:
                                                          Эта задача меня так вдохновила, что я напряг свой застоявшийся от работы мозг, и родил-таки вот этот прямолинейный и тормозной код (accepted, 0.564):

                                                          #include <iostream>
                                                          #include <vector>

                                                          using namespace std;

                                                          vector< vector<unsigned long long> > cache;

                                                          unsigned long long compress(const vector<unsigned> &coins, unsigned n, unsigned i)
                                                          {
                                                              unsigned long long result = 0;

                                                              if (!n)
                                                                  return 0;

                                                              if (coins[i] == 1)
                                                                  return 1;
                                                                  

                                                              const unsigned n_coins = n / coins[i];

                                                              if (!n_coins)
                                                              {
                                                                  unsigned long long *cached_value = &cache[n][i - 1];
                                                                  
                                                                  if (!*cached_value)
                                                                      *cached_value = compress(coins, n, i - 1);

                                                                  return *cached_value;
                                                              }

                                                              for (unsigned j = 0; j <= n_coins; ++j)
                                                              {
                                                                  const unsigned piece_to_cut = j * coins[i];
                                                                  
                                                                  if (piece_to_cut == n)
                                                                      ++result;
                                                                  else if (i > 1)
                                                                  {
                                                                      const unsigned remainder = n - piece_to_cut;

                                                                      unsigned long long *cached_value = &cache[remainder][i - 1];
                                                                      
                                                                      if (!*cached_value)
                                                                          *cached_value = compress(coins, remainder, i - 1);
                                                                      
                                                                      result += *cached_value;
                                                                  }
                                                                  else
                                                                      ++result;
                                                              }

                                                              return result;
                                                          }

                                                          unsigned long long solve_v3(unsigned n, const vector<unsigned> &coins)
                                                          {
                                                              if (cache.size() < n + 1)
                                                                  cache.resize(n + 1);

                                                              for (unsigned i = 0; i < cache.size(); ++i)
                                                              {
                                                                  if (cache[i].size() < coins.size())
                                                                      cache[i].resize(coins.size());
                                                              }

                                                              return compress(coins, n, coins.size() - 1);
                                                          }

                                                          int main()
                                                          {
                                                              vector<unsigned> coins;
                                                              coins.push_back(1);
                                                              coins.push_back(5);
                                                              coins.push_back(10);
                                                              coins.push_back(25);
                                                              coins.push_back(50);
                                                              
                                                              unsigned n;
                                                              
                                                              while (cin >> n)
                                                              {
                                                                  unsigned long long solutions = solve_v3(n, coins);
                                                                  
                                                                  if (solutions > 1)
                                                                      cout << "There are " << solutions << " ways to produce " << n << " cents change.\n";
                                                                  else
                                                                      cout << "There is only 1 way to produce " << n << " cents change.\n";
                                                              }
                                                          }
                                                          Colored with dumpz.org
                                                            0
                                                            Я один не могу зайти на сайт uva.onlinejudge.org/index.php?
                                                              0
                                                              Решение не очень красивое. А если бы монеты были бы, например, достоинством 1, 2, 5 и 10?

                                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                              Самое читаемое