Немного о себе: я увлекаюсь спортивным программированием и люблю решать задачи. В качестве языка, по понятным причинам, я выбрал C++
Вот, хочу в своем блоге публиковать исходные коды/разборы некоторых задач. Возможно, кому-нибудь пригодиться. Лично я много раз сталкивался с тем, что негде почитать про идеи или реализацию для некоторых задач.
Итак, начнем с задач попроще:
Задача 1073. Квадратная страна
Автор задачи: Станислав Васильев
Источник задачи: Ural State Univerisity Personal Contest Online February'2001 Students Session
Метки: динамическое программирование
Исходный код: скачать
Примечание: вариация на тему задачи о банкомате - выдать нужную сумму минимальным количеством банкнот. Зачада решается простой динамикой.
Функция динамического программирования:
A[i] = min(A[i-w[0]], A[i-w[1]], ... , A[i-w[j]])+1;
где A[] - массив чисел. w[] - массив квадратов.
Задача 1209. 1, 10, 100, 1000...
Автор задачи: Алексей Лахтин
Источник задачи: USU Open Collegiate Programming Contest October'2002 Junior Session
Метки: задача для начинающих
Исходный код: скачать
Примечание: решаем за О(1).
После недолгих рассуждений понимаем, что номер, на котором стоит единичка задается формулой:
F(n) = 2 + n + n*(n+1)/2;
F(n) = (n^2+3n+4)/2;
Пусть K — номер позиции в последовательности, про который надо узнать, какая цифра там находится.
(n^2+3n+2)/2 = K;
n^2+3n+4-2K = 0;
D = 8K-7;
D = M^2, значит 8K-7 = M^2, если на позиции с номером K стоит единица.
Задача 1087. Время забирать камни
Автор задачи: Антон Ботов
Источник задачи: Третье командное соревнование школьников Свердловское области по программированию, 4 марта 2001
Метки: игра
Исходный код: скачать
Примечание: это задача на моделирование игры. Почитать
здесь
Решается определением всех возможных выигрышных и проигрышных позиций со значениями от 0 до n.
Скачать:
