Как стать автором
Обновить

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

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

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

Желаю удачи!
Благодарю.
Магические константы и не совсем логичный код сделаны специально, чтобы ускорить работу алгоритма. Тем более, что с 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 секунды.
А, да, сам код:

#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 центов, а вы не разводите руками в ответ, а гордо протягиваете пустую ладонь :)

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

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

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

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

Собственно формула: Тогда 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 секунды.
==
Повторюсь: А вы пробовали эту задачу решать? да так, чтобы она прошла на сайте?
Попробую дать ответ на логическую задачу:
Он дал деньги десятками ;)
Вы молодец, даю ссылку на вас в посте.
Еще вариант, если они глухонемые и общаются жестами, а деньги протянул только один. Тогда тоже можно молча.
Кондуктор тоже глухонемой? :)
Необязательно быть глухонемым, чтобы понимать язык жестов :) Хотите задачку в тему?

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

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

А вторая задача была бы интересной, если бы номиналы монет были не в условии а задавались как входные параметры (например, достоинством, противоречащим логике)
Не успел первым ответить на логическую задачу, но второй моей догадкой как раз стало то, что он расплатился десятью купюрами по десять рублей, что как раз намекает на то, что сдачи он не ждет, так как билет стоит двадцать, и платит за всех.
А можно это написать красиво в функциональном стиле в одну строчку?
pastebin.com/qYEr5Zfh
Забыл ссылку на императивный вариант на python
НЛО прилетело и опубликовало эту надпись здесь
Нет. Для 6 найдет способы 1+5 и 1+1+1+1+1+1.
НЛО прилетело и опубликовало эту надпись здесь
Мне кажется, вы всё усложняете. Рекуррентное соотношение должно быть проще:
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)

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

Хотя это и не сильно отличается от хранения всей матрицы — учитывая, что в каждой строке всего 5 элементов :)
Если решать задачу для более общего случая с M монет, тогда использование памяти станет более критичным.
Поторопился. Уточнение:
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:

<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)

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

<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%.

<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). Но, очевидно, Ваше решение в данном виде проигрывает по эффективности. Если у Вас есть лишнее время, можете попробовать потестировать на больших числах и множестве тестов.
Смысл второго листинга не в максимальном быстродействии для _одного_ вычисления. А в том, что повторные вызовы функции N() будут использовать предыдущие вычисления. То есть максимальное быстродействие для ряда вычислений.

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

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

Подсказка: рассчитывать следует примерно на 108 операций в секунду на тестирующем сервере.
30000 можно получить 543065523200 способами, если точно.
Да. Выше даже есть мой код, с глупой ошибкой)
PS. Некропостинг в массы?)
1. Что вы собираетесь перебирать? Все способы?
Это едва ли проще, и работать будет, как говорится, O(∞)
2. У «тупого» решения будет хуже ассимптотика, причем существенно. То есть не составит труда задать ограничения, на которых нормальное решение работает быстро, а «тупое» — дольше любых разумных ограничений.
ладно дома найду трубопаскаль и засеку время за которое он переберет все варианты для набора суммы в 30,000 центов.
Боюсь, что к тому времени, как это досчитается, про этот топик (а скорее всего — и вообще про хабрахабр) все давно забудут.
Поэтому, пожалуйста, напишите сначала время для 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 часов :)
Для 1000 ответ будет 801451.
да, лажанул, забыл что integer гораздо меньше :)
В паскале integer 16битный. Так что считает неправильно. Ну да ладно.
Для 30000 будет считать в 678054 раза дольше, т.е. чуть меньше двух лет. Так что про сроки я немного загнул, про хабр помнить еще будут. Но по таймлимиту не проходит даже близко.
Только мне показалось, что количество комбинаций для 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
… и так далее
А монеты в 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/ вот.

И кстати по задаче. На реальной олимпиаде заметив бы эту задачу я бы за пять минут написал перебор для всех значений, который бы сгенерил мне константный массивчик ответов, и сдал бы вот так хитро. Это быстрее чем придумывать динамику, и генериться оно будет не так уж и долго. Так что и задачка не очень то олимпиадная, в реальности редко дают задачи решаемые прегенерацией.
Перебираться оно будет почти вечность. 543 427 145 501 способами можно набрать 30000. Успеете это сгенерировать за отведенное на раунд время?)
Задача простая, для человека, хоть сколько-нибудь занимавшийся олимпиадным программированием, как писать здесь динамику — очевидно.
Простая, но перебор почти всегда писать легче =). Да, вы правы, даже со всякими эвристиками оно не переберётся.
Именно что «почти». В этом случае, как мне кажется, это не так.
И почти всегда перебор не посчитается ни за какое разумное время.
Каждому своё. Я перебор почти что с закрытыми глазами пишу, а с динамическим программированием, по правде говоря не сильно дружу.
На тех олимпиадах которые я удосуживался писать, обычно одна-две задачи решались перебором (или их было возможно решить перебором). В прикладном программировании конечно перебором злоупотреблять не стоит.
habrahabr.ru/blogs/sport_programming/109384/#comment_3475824
перебором долго слишком получается.
конечно перебор есть куда оптимизировать, но… сами засеките время
За всю жизнь решил две-три олимпиадные задачи, а что такое динамическое программирование, узнал сегодня (:
Эта задача меня так вдохновила, что я напряг свой застоявшийся от работы мозг, и родил-таки вот этот прямолинейный и тормозной код (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
Решение не очень красивое. А если бы монеты были бы, например, достоинством 1, 2, 5 и 10?
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории