#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;
}
Я бы решал эту задачу (как мне кажется) проще, без поиска каких-либо закономерностей. Состояние нашей динамики 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 секунды.
Я аналогичную проблему решил переключением на английский язык — все скачалось нормально, установилась все равно русская версия (возможно, из-за того, что у меня это было обновлением).
Я вот вроде бы внимательно прочитал, но так и не понял суть ошибки в описании таблицы log. Что там не так?
Наличие суррогатного ключа? Но вы вроде бы сами приходите к выводу, что суррогатный айдишник оказывается полезнее реального времени — хотя бы потому, что реальные события происходят на непрерывной шкале времени, а у любого счетчиков есть некоторая частота дискретизации и в дискретном выражении несколько событий могут быть одновременными.
Или все-таки лишним было само поле log_occured_on? Тоже, казалось бы, нет — точное время несет полезную информацию при рассмотрении логов, хотя на ключевое поле и не тянет вроде.
очки давали еще за удачные попадания (+3 за снежки и +8 за ледышку), по 3 очка за каждую оставшуюся на конец игры льдинку и по очку за каждые 5 градусов температуры (хитпоинтов) на конец игры.
а при подбирании снеговика-бонуса давали только 2 очка, льдинку и пару градусов тепла :)
> Итоговый монитор значительно отличался от монитора, на момент заморозки.
не так сильно, как обычно — наша, команда, например, не сдала ни одной задачи после заморозки (да и вообще за последние 2 полконтеста), но так и осталась на 7 месте.
> Одна из команд топа сдала 9 задачу, став единственной командой с 9 задачами.
собственно, Saratov SU#2, причем эту задачу они сдали всего за 7 минут до конца контеста (если не ошибаюсь, тем самым вырвав победу в самый последний момент).
фразой про разрушение Карфагена один римский деятель заканчивал все свои выступления — независимо от того, о чем шла речь ранее
постоянное упоминание возможности удалить профиль во всех постах про эту социальную сеть видится мне весьма схожим с постоянным употреблением процитированной фразы про Карфаген
еще немного иронии добавляет тот факт, что в обоих предложениях упоминаются деструктивные действия
И раньше ж делал, и еще сильнее. И перешарпливал, и контрастность менял вполне себе целенаправленно.
Изначально так и вовсе они ж ужимались до четверти нормального размера экрана. Трудно понять фотографов, рассчитывавших получить в таких условиях приличные изображения своих шедевров.
Сейчас же сначала увеличили размер до адекватных величин, а теперь и степень пережатия на сервере снижают (что, как было замечено выше, и подразумевалось под «увеличением контрастности и насыщенности»). Но «профессиональные фотографы» все равно недовольны — теперь, оказывается, вес фотографий стал больше!
Итак — ставим в массиве 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 секунды.
Кстати, сервер все хуже справляется с хабраэффектом — вечно 500 Internal Error вылетает.
Понял, что не силен я в таком хардкорном пиксель-арте.
roem.ru/2010/10/11/addednews16806/?c#message76467
Наличие суррогатного ключа? Но вы вроде бы сами приходите к выводу, что суррогатный айдишник оказывается полезнее реального времени — хотя бы потому, что реальные события происходят на непрерывной шкале времени, а у любого счетчиков есть некоторая частота дискретизации и в дискретном выражении несколько событий могут быть одновременными.
Или все-таки лишним было само поле log_occured_on? Тоже, казалось бы, нет — точное время несет полезную информацию при рассмотрении логов, хотя на ключевое поле и не тянет вроде.
а при подбирании снеговика-бонуса давали только 2 очка, льдинку и пару градусов тепла :)
читать «за последние полконтеста» или «2,5 часа»
не так сильно, как обычно — наша, команда, например, не сдала ни одной задачи после заморозки (да и вообще за последние 2 полконтеста), но так и осталась на 7 месте.
> Одна из команд топа сдала 9 задачу, став единственной командой с 9 задачами.
собственно, Saratov SU#2, причем эту задачу они сдали всего за 7 минут до конца контеста (если не ошибаюсь, тем самым вырвав победу в самый последний момент).
фразой про разрушение Карфагена один римский деятель заканчивал все свои выступления — независимо от того, о чем шла речь ранее
постоянное упоминание возможности удалить профиль во всех постах про эту социальную сеть видится мне весьма схожим с постоянным употреблением процитированной фразы про Карфаген
еще немного иронии добавляет тот факт, что в обоих предложениях упоминаются деструктивные действия
И раньше ж делал, и еще сильнее. И перешарпливал, и контрастность менял вполне себе целенаправленно.
Изначально так и вовсе они ж ужимались до четверти нормального размера экрана. Трудно понять фотографов, рассчитывавших получить в таких условиях приличные изображения своих шедевров.
Сейчас же сначала увеличили размер до адекватных величин, а теперь и степень пережатия на сервере снижают (что, как было замечено выше, и подразумевалось под «увеличением контрастности и насыщенности»). Но «профессиональные фотографы» все равно недовольны — теперь, оказывается, вес фотографий стал больше!