Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Камни

Динамическое программирование: один параметр Простые игры

На столе лежат N камней. За ход игрок может взять
 
1 или 2 камня, если N делится на 3;
1 или 3, если N при делении на 3 дает остаток один;
1, 2 или 3, если N при делении на 3 дает остаток два.
Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.
 
Входные данные
Вводится целое число 0 < N <= 100.
 
Выходные данные
Выведите 1 или 2 – номер игрока, который выиграет при правильной игре.

Ввод Вывод
1 1
3 2


 

Шоколадка - революция

Простые игры

Петя получил золотую медаль на IOI, за что от правительства ему положена благодарность в виде шоколадки. На данный момент имеется N видов шоколадок, которые производит государственная шоколадная фабрика. У каждой шоколадки есть стоимость. Кроме того, у каждого вида, кроме шоколадки "Юлька", есть вид-прародитель. Известно, что прародителем может быть только шоколадка, которая была выпушена хронологически раньше. Исторически самый первый вид - "Юлька". Чиновник и Петя выбирают шоколадку ему в подарок. При этом цель первого - сэкономить, второго - получить настолько дорогую шоколадку, насколько это возможно. Начинается выбор с "Юльки". Петя за ход либо берет текущую шоколадку, либо меняет свой выбор на шоколадку-потомка (если это возможно). Чиновнику же кажется, что позже выпущенные виды хуже и дешевле, поэтому он меняет выбор на шоколадку-потомка (если это возможно), либо покупает Пете шоколадку (если потомков нет). Они ходят по очереди, Петя - первый. Определите, на шоколадку какой стоимости может претендовать Петя.
 
Входные данные
Сначала вводится число 0 < N <= 200000 - количество видов. "Юлька" имеет номер 1. Далее идут N строк с парами чисел 0 <= Pi <= N - номер сорта-предка (для шоколадки "Юлька" указан 0, у остальных Pi > 0) и 0 < Ci <= 1000000000 - стоимость i-го сорта.
 
Выходные данные
Выведите стоимость шоколадки, которую Петя может себе гарантировать при правильных действиях.

Ввод Вывод
8
0 4
5 3
1 2
5 1
1 5
4 8
3 6
3 7
6

Шоколадка - перезагрузка

Простые игры

Напомним содержание первой серии. Двое играют в такую игру: перед ними лежит шоколадка размера NxM. За ход можно разломить имеющийся кусок шоколадки вдоль одной из сторон на 2 "непустых".
 
Однако, нельзя разламывать куски размером не больше, чем 1k (куски можно поворачивать; мы считаем, что один кусок "не больше" другого, если он равен ему или его части). Таким образом, нельзя разламывать куски размером 11, 12, , 1k, а остальные куски разламывать можно.
 
Теперь куски, которые нельзя ломать, можно есть (не более одного за раз).
 
За один ход можно либо разламывать подходящий по размеру кусок, либо есть.
 
Проигрывает тот, кто не может сделать ход. Определите, кто же станет победителем в игре, если известны начальные размеры шоколадки.
 
Входные данные
Вводятся целые числа 0 < N, M, K <= 100.
 
Выходные данные
Выведите 1 или 2 - номер игрока, который выиграет при правильной игре.

Ввод Вывод
1 1 1 1
1 1 100 1

Игра Ним - 2

Простые игры

Двое играют в игру. Есть несколько кучек спичек. За один ход разрешается взять любое ненулевое количество спичек из любой кучки, кто не может сделать ход, тот проиграл. Определите, кто выигрывает при правильной игре.
 
Входные данные
В первой строке входного файла записано натуральное число N — количество кучек. Во второй строке записаны N целых чисел — количество спичек в кучках. Все числа во входном файле не превосходят 100000.
 
Выходные данные
Выведите «1», если выигрывает первый игрок или «2», если выигрывает второй игрок. Если выигрывает первый игрок, во второй строке выведите число K — общее количество выигрышных ходов. В последующие K строк выведите информацию о выигрышных ходах — пары чисел, перечисленные в порядке возрастания первой координаты, а при равенстве в порядке возрастания второй координаты. В каждой такой паре первое число должно обозначать номер кучки, а второе — количество спичек, которые необходимо взять из этой кучки.

Ввод Вывод
1
10
1
1
1 10
2
1 1
2

Игра с пешкой

Динамическое программирование на таблицах Простые игры

В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a1, a2, …, aN. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

3              
  1            
    4          
      1        
        5      
          9    
            2  
              6


Входные данные
В первой строке записано число N (1 ≤ N ≤ 100). Во второй строке записаны натуральные числа a1, a2, …, aN (1 ≤ ai ≤ 100).
 
Выходные данные
Выведите одно число – выигрыш первого игрока.

Ввод Вывод
8
3 1 4 1 5 9 2 6
5

Охота на Снарка

Простые игры

В начальный момент времени Снарк находится в точке прямой с целой неотрицательной координатой X. За ход он может оказаться в любой точке с целой координатой Y при условии, что |X-Y| <= S. Кроме того, Снарк не любит булочки, поэтому он никогда не прыгнет в клетку, где одна из этих противных штук лежит. Булочник не хочет, чтобы Снарк попал домой. После каждого хода Снарка Булочник может положить булочку в любую точку прямой при условии, что это не начало координат (дом Снарка) и в этой клетке нет Снарка. Определите, сможет ли Булочник помешать Снарку оказаться дома. Изначально в некоторых клетках лежат булочки.
 
Входные данные
В первой строке задаются целые числа 0 <= X < 10000, 0 < S <= 100 и 0 <= N < max(X-1, 0) - количество булочек, которые уже лежат на прямой. Далее идут N различных чисел 0 < bi < X - координаты точек, где лежит гадость.
 
Выходные данные
Выведите "YES", если Булочник сможет реализовать свои грязные планы, "NO" - если при любых действиях врага Снарк сможет припрыгать домой.

Ввод Вывод
1 1 0 NO
10 3 3
7 8 9
YES

Игра НИМ

Простые игры

Двое играют в игру. Есть несколько кучек спичек. За один ход разрешается взять любое ненулевое количество спичек из любой кучки, кто не может сделать ход, тот проиграл. Определите, кто выигрывает при правильной игре.
 
Входные данные
В первой строке входного файла записано натуральное число N — количество кучек. Во второй строке записаны N целых чисел — количество спичек в кучках. Все числа во входном файле не превосходят 100000.
 
Выходные данные
Выведите «1», если выигрывает первый игрок или «2», если выигрывает второй игрок.

Ввод Вывод
1
10
1
2
1 1
2