| Условие задачи | | Прогресс |
|
Темы:
Динамическое программирование на таблицах
Простые игры
В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a1, a2, …, aN. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.
Входные данные
В первой строке записано число N (1 ≤ N ≤ 100). Во второй строке записаны натуральные числа a1, a2, …, aN (1 ≤ ai ≤ 100).
Выходные данные
Выведите одно число – выигрыш первого игрока.
|
Ввод |
Вывод |
|
8
3 1 4 1 5 9 2 6
|
5 |
| |
![]()
|
|
Темы:
Динамическое программирование на таблицах
Вася и Петя играют в следующую игру. Они берут колоду из 36 карточек. На каждой карточке написано число от 1 до 9 и каждая карточка покрашена в один из 4 цветов так, что есть ровно по 9 карточек каждого цвета и они пронумерованы числами от 1 до 9. Карты перемешиваются, и игрокам раздается по 18 карт.
Дальше игроки по очереди делают ходы. За один ход игрок может выложить на стол одну карточку по следующим правилам. Карточку с цифрой 5 можно выкладывать на стол в любой момент. Карточку с другой цифрой можно выкладывать только если на стол уже выложена карточка того же цвета, на которой написано число на 1 большее или на 1 меньшее, чем на данной карточке (не важно, была ли эта карточка выложена вами или вашим противником, и была ли она выложена на предыдущем ходе или раньше). Если игрок может выложить хоть какую-то карточку, он обязан делать ход. Если ни одну карточку игрок выложить не может, он пропускает ход.
Выигрывает тот, кто первым выложит все свои карточки на стол.
Напишите программу, которая по информации о том, кому какие карточки достались, определяет, кто выиграет при оптимальной игре обоих игроков.
Входные данные
Во входном файле записаны 18 пар чисел, описывающих карточки, которые достались первому игроку. Каждая карточка описывается двумя числами — номером цвета (от 1 до 4) и цифрой, которая написана на карточке (от 1 до 9). Второму игроку, соответственно, достались все остальные карточки.
Выходные данные
В выходной файл выведите одно число (1 или 2) — номер игрока, который выиграет при оптимальной игре обоих игроков.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9 |
1 |
| |
![]()
|
|
Темы:
Динамическое программирование на таблицах
Дана сетка с N + 1 рядами и M + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку (N, M). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем T раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку (N, M). Так как это число может быть очень большим, выведите остаток от его деления на Z.
Входные данные
В первой строке входного файла задается 5 целых чисел: N, M, K, T и Z (1 ≤ N,M ≤ 300000, 0 ≤ K, T 20, 1 ≤ Z ≤ 109). В каждой из следующих K строк расположены координаты соответствующей клетки с ловушкой X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (N, M) ловушек нет.
Выходные данные
Выведите требуемое число.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 1 1 0 100
0 1 |
1 |
| 2 |
2 2 0 0 10 |
6 |
| |
![]()
|
|
Темы:
Динамическое программирование на таблицах
У вас есть таблица c N строками и M столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка - значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение K-го пути в этом отсортированном листе.
Входные данные
В первой строке задается два целых числа N - количество рядов и M - количество столбцов заданной таблицы (1 ≤ N, M ≤ 30). Каждая из следующих N строк содержит ровно M строчных букв английского алфавита. Последняя строка входного файла содержит целое число K (1 ≤ K ≤1018). Гарантируется, что для K ответ всегда существует.
Выходные данные
Первая и последняя строка выходного файла должна содержат одну строку - ответ к задаче.
Пояснения к примеру
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 4
abcd
efdg
hijk
4 |
abfdgk |
| |
![]()
|
|
Темы:
Динамическое программирование по профилю
Динамическое программирование на таблицах
Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.
Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!
Входные данные
Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).
Выходные данные
Выведите единственное число – количество различных симпатичных узоров, которые можно выложить во дворе размера N х M. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 2 |
4 |
| 2 |
2 3 |
50 |
| |
![]()
|
|
Темы:
Динамическое программирование на таблицах
В прямоугольной таблице NxM в левой верхней клетке стоит шашка. За один ход разрешается переместить шашку в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть вариантов переместить шашку в правую нижнюю клетку.
Входные данные
Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10).
Выходные данные
Выведите искомое количество вариантов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 3 |
3 |
| |
![]()
|
|
Темы:
Динамическое программирование на таблицах
Для биномиальных коэффициентов (числа сочетаний из n по k) хорошо известна рекуррентная формула: \(C^k_n=C^{k-1}_{n-1}+C^{k}_{n-1}\), \(C^0_n = C^n_n=1\).
Входные данные
Вводится 2 числа - n и k.
Выходные данные
Необходимо вывести значение \(С^k_n\) .
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 2 |
6 |
| |
![]()
|
|
Темы:
Динамическое программирование на таблицах
Элементарная геометрия
Алгоритмы на графах
Дед Мороз за ночь должен посетить N городов. У него есть двумерный план расположения всех городов. План нарисован в декартовой системе координат, в которой точкой (0, 0) обозначено место старта Деда Мороза. Каждый город на плане отмечен точкой с координатой (Xi, Yi). Также на карте обозначены M точек с координатами (Pi, Qi), в которых расположены ускорители. Чтобы успеть разнести все подарки, Дед Мороз может воспользоваться ускорителем, который увеличивает его скорость в два раза (а может им и не пользоваться).
Дед Мороз в Новогоднюю ночь начинает с места старта, посещает все N городов и возвращается обратно.
Начальная скорость Деда Мороза равна 1. Найдите наименьшее время, необходимое Деду Морозу, чтобы посетить все города и вернуться обратно. Временем, при котором он раскладывает все подарки будем пренебрегать!
Входные данные
Первая строка входных данных содержит два целых числа N и M (1 <= N <= 12, 0 <= M <=5). Следующие N строк содержат координаты городов (Xi, Yi). Далее идут M строк с координатами ускорителей (Pi, Qi). Все координаты различны и среди них нет координаты (0, 0).
Выходные данные
Выведите ответ на задачу, с точностью не менее 6 знаков после запятой.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
2 1
1 1
0 1
1 0 |
2 1
1 1
0 1
1 0 |
Вот один из оптимальных способов разнести все подарки
- Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
- Пройти расстояние 1 от ускорителя 1 до города 1 со скоростью 2, затратив время 0,5.
- Пройти расстояние 1 от города 1 до города 2 со скоростью 2, затратив время 0,5.
- Пройти расстояние 1 от города 2 до начала координат со скоростью 2, затратив время 0,5.
|
| 2 |
2 1
1 1
0 1
100 0 |
3.4142135624 |
Вот один из оптимальных способов разнести все подарки
- Пройти расстояние 1.41... от начала координат до города 1 со скоростью 1, затратив время 1.41....
- Пройти расстояние 1 от города 1 до города 2 со скоростью 1, затратив время 1.
- Пройти расстояние 1 от города 2 до начала координат со скоростью 1, затратив время 1.
|
| 3 |
1 2
4 4
1 0
0 1 |
4.3713203436 |
Вот один из оптимальных способов разнести все подарки
- Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
- Пройти расстояние 1,41... от ускорителя 1 до ускорителя 2 со скоростью 2, затратив время 0,707....
- Пройти расстояние 5 от ускорителя 2 до города 1 со скоростью 4, затратив время 1,25.
- Пройти расстояние 5,65... от города 1 до начала координат со скоростью 4, затратив время 1,41....
|
| |
![]()
|