Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование в играх
---> 9 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На столе лежит кучка из N спичек. Двое играют в такую игру. За один ход разрешается взять из кучки одну, две или три спички, так чтобы оставшееся количество спичек не было простым числом (Например, можно оставить в кучке 1 или 4 спички, но нельзя оставить 2 или 3). Выигрывает тот, кто забирает последнюю спичку. Требуется определить, кто из игроков имеет выигрышную стратегию.

Входные данные

Вводится одно число N (1<=N<=10000).

Выходные данные

Выведите число 1, если выигрышую стратегию имеет начинающий игрок, или число 2, если выигрышную стратегию имеет второй игрок.

Примеры
Входные данные
1
Выходные данные
1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На столе изначально лежат N камней. За ход игрок может взять

  • 1 или 2 камня, если текущее число камней делится на 3;
  • 1 или 3, если текущее число камней при делении на 3 дает остаток один;
  • 1, 2 или 3, если текущее число камней при делении на 3 дает остаток два.

Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.

Входные данные

Вводится целое число 0 < N <= 100.

Выходные данные

Выведите 1 или 2 – номер игрока, который выиграет при правильной игре.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
3
Выходные данные
2
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Файлы: coins.in coins.out

Два участника олимпиады играют в следующую игру. Участники по очереди бросают монетки (одну или больше) в хитрый ящик. Если в ящике находится в точности X1, или X2, ..., или Xn монеток, то они, кроме одной, отдаются участнику, сделавшему последний ход. Оставшаяся монетка "исчезает" из игры. Игра заканчивается, если у одного из участников игры не осталось монеток. При этом монетки из ящика (все до одной) отдаются другому участнику(он является победителем игры). Определить наибольшее количество монеток, которое может выиграть первый участник при наилучшей игре второго. Если первый участник не может выиграть, то результатом является число 0.

Входные данные

В первой строке входного файла два числа 0 < S,T <= 50 (число монеток у первого и второго игроков). Во второй строке N (0 <= N <= 50) - число хитрых состояний ящика. В третьей строке целые числа X1, X2,..., Xn, 0 < X1 <= X2 <= ... <= Xn <= 100.

Выходные данные

Вывести число монеток у первого участника или 0.

Примеры
Входные данные
8 4
4
1 2 3 4 
Выходные данные
4
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася очень хочет попасть на сборы в СУНЦ и, к счастью, живет недалеко от него. Поэтому он решил дойти до места проведения сборов пешком. Васе известен план города - какие перекрестки соединены улицами и сколько времени требуется, чтобы пройти по каждой улице. Движение по любой улице разрешено в обе стороны.

Администрация города, однако, решила устроить в этот день уборку улиц от снега. Если на какой-то из улиц происходит уборка, то движение по ней замедляется в два раза. В распоряжении города есть K снегоуборочных машин.

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

Дом Васи находится около перекрестка с номером 1, а СУНЦ - около перекрестка с номером N. Таким образом, перемещение Васи от дома до СУНЦа выглядит следующим образом. В начале глава выбирает дороги, на которых будет проводиться уборка, затем Вася выбирает улицу, по которой он пойдет от перекрестка 1 (Вася достаточно наблюдателен, чтобы заметить, на каких улицах идет уборка). Когда он доходит до конца выбранной улицы и оказывается на перекрестке, процесс повторяется: глава вновь выбирает улицы для уборки, и машины туда мгновенно перемещаются, а затем Вася - улицу, по которой идти, и т. д. Процесс продолжается, пока Вася не попадет в СУНЦ.

Ваша задача - выяснить, за какое минимально возможное время Васе удастся достичь СУНЦа при условии, что глава администрации всегда действует оптимально.

Входные данные

Первая строка содержит числа N - количество перекрестков в городе, M - количество улиц и K - количество снегоуборочных машин (1 <= N <= 100, 0 <= K <= M <= 20000). Следующие M строк содержат описания улиц в следующем формате: a и b - номера перекрестков, которые данная улица соединяет, t - время движения по данной улице (целое положительное число, не превосходящее 1000).

Выходные данные

Выведите одно число - минимальное время, за которое Вася может добраться до СУНЦа. или -1, если добраться туда невозможно.

Примеры
Входные данные
3 3 2
1 2 3
1 3 5
2 3 1
Выходные данные
8
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Необходимо найти три наиболее удаленные вершины дерева. Удаленность считается как сумма расстояний между парами вершин.

В одном государстве имеется $N$ городов. Некоторые города соединены дорогами, причем для любых двух городов $A$ и $B$ выполняется следующее свойство: существует ровно один способ попасть из города $A$ в город $B$ если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.

Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов $A$, $B$ и $C$ минимальное количество дорог, которое необходимо использовать, чтобы доехать от $A$ до $B$, затем от $B$ до $C$ и затем от $C$ до $A$ (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).

Требуется найти три города, для которых взаимная удаленность друг от друга будет максимальной.

Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).

Входные данные

В первой строке вводится число $N$ - количество городов (3 <= $N$ <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит $K_i$ - количество городов, с которыми он соединен дорогами (1 <= $K_i$ < $N$), а затем $K_i$ чисел - номера городов, с которыми он соединен. Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.

Выходные данные

Выведите три различных числа - номера трех наиболее удаленных друг от друга городов в произвольном порядке. Если решений несколько, выведите любое из них

Примеры
Входные данные
5
1 3
1 3
3 1 2 4
2 3 5
1 4
Выходные данные
5 2 1
Входные данные
5
1 3
1 3
4 1 2 4 5
1 3
1 3
Выходные данные
1 2 4

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест