Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 89
В 9 или 10 классе на олимпиаде мне эта задача мозг выела, не решил (((
Была, кстати, задачка с конем на шахматной доске, его нужно было доставить в точку. Я последние шаги рандомом загонял в точку, ржачно было, когда у меня приняли это задание.
я такую рекурсией решал… хорошая задачка)
Очень не сложная задачка, алгоритм поиска очень простой: Начиная от начальной точки помечаете не помеченные клетки доски, в которые можно добраться в 1 шаг цифрой 1, потом все клетки, в которые можно добраться конем из клеток с цифрой 1 помечаете цифрой 2 и т.д. В итоге получаете доску с размеченным числом шагов до любой клетки. По этим цифрам несложно было пройти путь обратно от конечной точки до начальной.
Тоже решал рекурсией, на C вышло примерно 25 строк. Но мозга я поломал много.
Похожая задачка с конем была в виде: пройти конем всю шахмотную доску… там и алгоритм на ето был, и рекурся не понадобилась.
Если я правильно понимаю условие (найти путь с наименьшим числом ходов), то решать следует так:
0) Текущая точка = стартовая точка.
1) Если расстояние до конечной точки <= 4, переходим к шагу 5.
2) Выпустим 8 лучей из текущей точки, чтобы все возможные ходы коня приходился на различные части плоскости (разделенными нашими лучами).
3) Проанализируем, в какой из частей плоскости находится конечная точка.
4) Делаем ход в соответствующем направлении, переходим к шагу 1.
5) Рисуем квадрат — и поиском в ширину находим кратчайший путь.
0) Текущая точка = стартовая точка.
1) Если расстояние до конечной точки <= 4, переходим к шагу 5.
2) Выпустим 8 лучей из текущей точки, чтобы все возможные ходы коня приходился на различные части плоскости (разделенными нашими лучами).
3) Проанализируем, в какой из частей плоскости находится конечная точка.
4) Делаем ход в соответствующем направлении, переходим к шагу 1.
5) Рисуем квадрат — и поиском в ширину находим кратчайший путь.
Я знаю, что я могу сделать задания, меня всегда напрягало ограничение по времени. Я потом приходил домой и спокойно всё делал. Мне надо посидеть в тишине, чтоб никого не было вокруг, задуматься и вуаля всё как по маслу. Я так после олимпиад по информатике делал, расстраивался. Потом вступительные по математике завалил на 3, домой пришел быстро всё сделал.
такая же ситуация :) решил самую сложную, а потом на 4 оставшиеся простенькие никак не смог мозг перестроить. еще помню как на олимпиаде по физике у меня напрочь выпало слово «конденсируется» и я долго парился потом так судьям и сказал «я слово забыл но не концентрируется а както по другому» :)
Пост очень хорошо написан, читать интересно и занимательно, но мне кажется, что задачи, которые вы разбираете, ну уж очень очевидны. Я думаю, что стоит попробовать увеличить сложность задач.
P.S. Посмотрел ваш код. На мой взгляд у вас слишком много магических констант да и вообще код плохо читается. В подобных задачах принято заводить массив значений номиналов монет (массы грузов, стоимости товаров, etc) и писать более логичный код с двумя циклами.
Желаю удачи!
P.S. Посмотрел ваш код. На мой взгляд у вас слишком много магических констант да и вообще код плохо читается. В подобных задачах принято заводить массив значений номиналов монет (массы грузов, стоимости товаров, etc) и писать более логичный код с двумя циклами.
Желаю удачи!
Благодарю.
Магические константы и не совсем логичный код сделаны специально, чтобы ускорить работу алгоритма. Тем более, что с C++ я, мягко говоря, почти не знаком и изучаю его параллельно со своим хобби. Но я обещаю совершенствоваться со временем. Кстати, отмечу что эта задача не такая уж и очевидная, во всяком случае для меня.
Магические константы и не совсем логичный код сделаны специально, чтобы ускорить работу алгоритма. Тем более, что с C++ я, мягко говоря, почти не знаком и изучаю его параллельно со своим хобби. Но я обещаю совершенствоваться со временем. Кстати, отмечу что эта задача не такая уж и очевидная, во всяком случае для меня.
Я бы решал эту задачу (как мне кажется) проще, без поиска каких-либо закономерностей. Состояние нашей динамики 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 секунды.
Итак — ставим в массиве 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 секунды.
А, да, сам код:
#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
There is only 1 way to produce 0 cents change
Разве не так должно быть?
0
There are 0 ways to produce 0 cents change
Но вот это смутило.
0
There is only 1 way to produce 0 cents change
Разве не так должно быть?
0
There are 0 ways to produce 0 cents change
В данной задаче (как и во многих других), более естественно считать, что нулевую сумму набрать можно всегда, причем единственным способом.
Представлять себе это можно примерно так: у вас просят 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] будет ответом.
Ваше более понятно, хотя я бы использовал дп «назад», а не вперед, так проще перевести рекуррентную формулу в дп.
Также тут количество операций в пять раз больше, чем достаточно.
Собственно формула: Тогда 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] будет ответом.
А вы пробовали эту задачу решать? да так, чтобы она прошла на сайте?
==
Я тоже сначала массив констант (номиналы монет) заводил, и не прошло ограничение по времени.
Потом думал 2 дня и упростил решение. Сделал магические числа, и всё равно не прошло.
по времени выполнения не прошло. нужно 3 секунды.
==
Повторюсь: А вы пробовали эту задачу решать? да так, чтобы она прошла на сайте?
==
Я тоже сначала массив констант (номиналы монет) заводил, и не прошло ограничение по времени.
Потом думал 2 дня и упростил решение. Сделал магические числа, и всё равно не прошло.
по времени выполнения не прошло. нужно 3 секунды.
==
Повторюсь: А вы пробовали эту задачу решать? да так, чтобы она прошла на сайте?
Попробую дать ответ на логическую задачу:
Он дал деньги десятками ;)
Он дал деньги десятками ;)
Вы молодец, даю ссылку на вас в посте.
Еще вариант, если они глухонемые и общаются жестами, а деньги протянул только один. Тогда тоже можно молча.
Кондуктор тоже глухонемой? :)
Необязательно быть глухонемым, чтобы понимать язык жестов :) Хотите задачку в тему?
В аудитории идет экзамен. Сидят студенты, за кафедрой сидит преподаватель. Вдруг неожиданно один встает, ни говоря ни слова, подходит к преподавателю с зачеткой, получает «отлично» и выходит. Никакого листочка или любой другой письменной работы студент не сдавал. Вопрос — по какому предмету экзамен? Можно даже предположить сферу знаний, преподаваемую в вузе.
В аудитории идет экзамен. Сидят студенты, за кафедрой сидит преподаватель. Вдруг неожиданно один встает, ни говоря ни слова, подходит к преподавателю с зачеткой, получает «отлично» и выходит. Никакого листочка или любой другой письменной работы студент не сдавал. Вопрос — по какому предмету экзамен? Можно даже предположить сферу знаний, преподаваемую в вузе.
среднестатистический кондуктор все равно спросил бы: «сколько с этой стопки десяток?» :)
на логическую задачу…
кондуктор видел, что деньги протягивает только один, а остальные 0 внимания, следовательно, они вместе
кондуктор видел, что деньги протягивает только один, а остальные 0 внимания, следовательно, они вместе
По поводу первой — он расплатился комбинацией купюр, позволявшей без сдачи с меньшей итоговой суммой оплатить за 1,2,3 и 4 человек (например, дал стопку по рублю)
А вторая задача была бы интересной, если бы номиналы монет были не в условии а задавались как входные параметры (например, достоинством, противоречащим логике)
А вторая задача была бы интересной, если бы номиналы монет были не в условии а задавались как входные параметры (например, достоинством, противоречащим логике)
Не успел первым ответить на логическую задачу, но второй моей догадкой как раз стало то, что он расплатился десятью купюрами по десять рублей, что как раз намекает на то, что сдачи он не ждет, так как билет стоит двадцать, и платит за всех.
А можно это написать красиво в функциональном стиле в одну строчку?
pastebin.com/qYEr5Zfh
Забыл ссылку на императивный вариант на python
Забыл ссылку на императивный вариант на python
Мне кажется, вы всё усложняете. Рекуррентное соотношение должно быть проще:
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)
Таким образом видим, что при каждой итерации используются только значения, полученные на текущей итерации и значения предыдущей итерации,
что позволяет нам хранить только две строки условной матрицы.
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)
Таким образом видим, что при каждой итерации используются только значения, полученные на текущей итерации и значения предыдущей итерации,
что позволяет нам хранить только две строки условной матрицы.
Зато при хранении всей матрицы не нужно пересчитывать динамику целиком для каждого теста во входном файле — достаточно посчитать ее один раз.
Если я правильно понял условие задачи, то для входных тестов достоинства монет не изменяются, изменяется только общая сумма, которую требуется разложить. Матрица нужна только в случае, если нужно хранить разложения для подмножеств монет.
Поторопился. Уточнение:
N(i, k) = N(i-1, k) + N (i, k-C(i) ),
То есть, количество разложений, когда мы используем монету C(i)-го достоинства (не менее одного раза) + количество разложений, когда мы монету С(i)-го достоинства не использовали ни разу.
N(i, k) = N(i-1, k) + N (i, k-C(i) ),
То есть, количество разложений, когда мы используем монету C(i)-го достоинства (не менее одного раза) + количество разложений, когда мы монету С(i)-го достоинства не использовали ни разу.
Пересчёт можно вести в единственном массиве. =)
Да, это больше на правду похоже:
N(i, S) = N(i-1, S) + N(i-1, S — Ci)
Кол-во наборов той же суммы без монет Ci.
Плюс кол-во набором с хотя бы одной монетой.
На JavaScript:
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>
Ну и немного исследований.
Добавление 2-х центовой монеты к набору монет {1,5,10,25,50}, как и ожидалось, резко увеличивает число вариантов.
Кол-во вариантов:
для 17 центов стало 28 (для набора без 2-х центовой монеты было — 6)
для 100 центов стало 3953 (для набора без 2-х центовой монеты было 292)
:-)
Добавление 2-х центовой монеты к набору монет {1,5,10,25,50}, как и ожидалось, резко увеличивает число вариантов.
Кол-во вариантов:
для 17 центов стало 28 (для набора без 2-х центовой монеты было — 6)
для 100 центов стало 3953 (для набора без 2-х центовой монеты было 292)
:-)
О каком массиве идет речь, не понимаю… Зачем нужен?
Чтобы не пересчитывать уже посчитанные ранее результаты — суть динамического программирования.
Динамическая версия :-)
<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>
Как-то Вы всё усложняете. Рекурсия тут вообще не нужна.
Заполнение массива:
Заполнение массива:
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]];
}
}
Рекурсия позволяет вычислять только те промежуточные суммы, которые необходимы.
Ваш пример посчитает все подряд.
Например, для S = 1000 кол-во промежуточных сумм будет равно 458, то есть экономия на вычислениях превышает 50%.
Ваш пример посчитает все подряд.
Например, для 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>
Вы считаете, что Ваше решение «экономное»?
Просто пара замечаний:
Вы используете поиск по ассоциативному массиву с текстовым (!) ключом. Даже если рассматривать реализацию его в виде хеш-таблицы всё равно это не единичное время доступа.
Вызов функции всегда сопряжён с накладными расходами. Особенно, когда Вы используете рекурсию и не хвостовую.
Мелочи, вроде конкатенации строк и преобразования чисел в строку также далеко не дешёвые.
Итого, если считать, что поиск в массиве по текстовому ключу занимает O(1), то асимптотическая оценка наших реализаций будет одинакова O(C*S). Но, очевидно, Ваше решение в данном виде проигрывает по эффективности. Если у Вас есть лишнее время, можете попробовать потестировать на больших числах и множестве тестов.
Просто пара замечаний:
Вы используете поиск по ассоциативному массиву с текстовым (!) ключом. Даже если рассматривать реализацию его в виде хеш-таблицы всё равно это не единичное время доступа.
Вызов функции всегда сопряжён с накладными расходами. Особенно, когда Вы используете рекурсию и не хвостовую.
Мелочи, вроде конкатенации строк и преобразования чисел в строку также далеко не дешёвые.
Итого, если считать, что поиск в массиве по текстовому ключу занимает O(1), то асимптотическая оценка наших реализаций будет одинакова O(C*S). Но, очевидно, Ваше решение в данном виде проигрывает по эффективности. Если у Вас есть лишнее время, можете попробовать потестировать на больших числах и множестве тестов.
Смысл второго листинга не в максимальном быстродействии для _одного_ вычисления. А в том, что повторные вызовы функции N() будут использовать предыдущие вычисления. То есть максимальное быстродействие для ряда вычислений.
Для поиска в хеше я просто воспользовался удобствами JavaScript. Вместо хеша можно использовать массив, заполненный нулями. И обращаться по индексу, который вычисляется из i и S. Это будет занимать O(N).
Для поиска в хеше я просто воспользовался удобствами JavaScript. Вместо хеша можно использовать массив, заполненный нулями. И обращаться по индексу, который вычисляется из i и S. Это будет занимать O(N).
Рискую показаться занудой, но тем не менее.
Рекурсивное решение в данном случае может отработать быстрее в случае, если у нас один тест (нужно посчитать количество вариантов для одной суммы). Но в этом случае вам придётся использовать не массив, как вы пишете, а матрицу C×S (массив размера C*S, что то же), или же вернуться к хеш-таблице.
Рекурсивное решение в данном случае может отработать быстрее в случае, если у нас один тест (нужно посчитать количество вариантов для одной суммы). Но в этом случае вам придётся использовать не массив, как вы пишете, а матрицу C×S (массив размера C*S, что то же), или же вернуться к хеш-таблице.
Что-то не верится в ваше рекурсивное соотношение… Не поясните, как получилось?
я б такую задачу решил тупо перебором.
на современных скоростях даже глазом не успеешь моргнуть как она все переберет, по 1000 раз лишних операций сделает и выдаст ответ так же быстро как и ваша.
на современных скоростях даже глазом не успеешь моргнуть как она все переберет, по 1000 раз лишних операций сделает и выдаст ответ так же быстро как и ваша.
Суть в том, чтобы мозги развивать. :)
Число комбинаций, как говорит автор статьи, не укладывается в восьмибайтовый long long. Вы уверены, что вы всех их успеете за три секунды перебрать?
Подсказка: рассчитывать следует примерно на 108 операций в секунду на тестирующем сервере.
Подсказка: рассчитывать следует примерно на 108 операций в секунду на тестирующем сервере.
1. Что вы собираетесь перебирать? Все способы?
Это едва ли проще, и работать будет, как говорится, O(∞)
2. У «тупого» решения будет хуже ассимптотика, причем существенно. То есть не составит труда задать ограничения, на которых нормальное решение работает быстро, а «тупое» — дольше любых разумных ограничений.
Это едва ли проще, и работать будет, как говорится, O(∞)
2. У «тупого» решения будет хуже ассимптотика, причем существенно. То есть не составит труда задать ограничения, на которых нормальное решение работает быстро, а «тупое» — дольше любых разумных ограничений.
ладно дома найду трубопаскаль и засеку время за которое он переберет все варианты для набора суммы в 30,000 центов.
Боюсь, что к тому времени, как это досчитается, про этот топик (а скорее всего — и вообще про хабрахабр) все давно забудут.
Поэтому, пожалуйста, напишите сначала время для 8000 (их «всего» 2796029201 вариантов).
Поэтому, пожалуйста, напишите сначала время для 8000 (их «всего» 2796029201 вариантов).
я всетаки скачал борланд паскаль на работе
и забубенил 5 вложенных циклов :)
dl.dropbox.com/u/930263/habr/for.jpg
и так на двухядерном цилероне
время расчета для 1000 центов = 1 минута 32 секунды
значение 15019 вариантов
Прикинем сейчас 00:01:32/15019*2796029201=05:34:45
:)
Всего то 5,5 часов :)
и забубенил 5 вложенных циклов :)
dl.dropbox.com/u/930263/habr/for.jpg
и так на двухядерном цилероне
время расчета для 1000 центов = 1 минута 32 секунды
значение 15019 вариантов
Прикинем сейчас 00:01:32/15019*2796029201=05:34:45
:)
Всего то 5,5 часов :)
Только мне показалось, что количество комбинаций для 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
… и так далее
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
… и так далее
Уже второй раз читаю ваши статьи и немножечко поражаюсь. Я занимаюсь олимпиадным программированием достаточно долго и привык что у задачи есть ограничения. «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/ вот.
И кстати по задаче. На реальной олимпиаде заметив бы эту задачу я бы за пять минут написал перебор для всех значений, который бы сгенерил мне константный массивчик ответов, и сдал бы вот так хитро. Это быстрее чем придумывать динамику, и генериться оно будет не так уж и долго. Так что и задачка не очень то олимпиадная, в реальности редко дают задачи решаемые прегенерацией.
На вашем месте я бы использовал acm.timus.ru/ ну или informatics.mccme.ru/ вот.
И кстати по задаче. На реальной олимпиаде заметив бы эту задачу я бы за пять минут написал перебор для всех значений, который бы сгенерил мне константный массивчик ответов, и сдал бы вот так хитро. Это быстрее чем придумывать динамику, и генериться оно будет не так уж и долго. Так что и задачка не очень то олимпиадная, в реальности редко дают задачи решаемые прегенерацией.
Перебираться оно будет почти вечность. 543 427 145 501 способами можно набрать 30000. Успеете это сгенерировать за отведенное на раунд время?)
Задача простая, для человека, хоть сколько-нибудь занимавшийся олимпиадным программированием, как писать здесь динамику — очевидно.
Задача простая, для человека, хоть сколько-нибудь занимавшийся олимпиадным программированием, как писать здесь динамику — очевидно.
Простая, но перебор почти всегда писать легче =). Да, вы правы, даже со всякими эвристиками оно не переберётся.
Именно что «почти». В этом случае, как мне кажется, это не так.
И почти всегда перебор не посчитается ни за какое разумное время.
И почти всегда перебор не посчитается ни за какое разумное время.
Каждому своё. Я перебор почти что с закрытыми глазами пишу, а с динамическим программированием, по правде говоря не сильно дружу.
На тех олимпиадах которые я удосуживался писать, обычно одна-две задачи решались перебором (или их было возможно решить перебором). В прикладном программировании конечно перебором злоупотреблять не стоит.
На тех олимпиадах которые я удосуживался писать, обычно одна-две задачи решались перебором (или их было возможно решить перебором). В прикладном программировании конечно перебором злоупотреблять не стоит.
habrahabr.ru/blogs/sport_programming/109384/#comment_3475824
перебором долго слишком получается.
конечно перебор есть куда оптимизировать, но… сами засеките время
перебором долго слишком получается.
конечно перебор есть куда оптимизировать, но… сами засеките время
За всю жизнь решил две-три олимпиадные задачи, а что такое динамическое программирование, узнал сегодня (:
Эта задача меня так вдохновила, что я напряг свой застоявшийся от работы мозг, и родил-таки вот этот прямолинейный и тормозной код (accepted, 0.564):
Эта задача меня так вдохновила, что я напряг свой застоявшийся от работы мозг, и родил-таки вот этот прямолинейный и тормозной код (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";
}
}
Я один не могу зайти на сайт uva.onlinejudge.org/index.php?
Решение не очень красивое. А если бы монеты были бы, например, достоинством 1, 2, 5 и 10?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Олимпиадное хобби. Размен монет