МОЛОДЕЖНОЕ НАУЧНОЕ ОБЩЕСТВО "Q-BIT"

http://www. qbit.

mail: *****@***

СЛОЖНОЕ - ИГРАЮЧИ!
 
, 8(068), 8(063)

1-Й ТУР ОТБОРА. 10-11 КЛАСС. 21.02.2009

Задача A. Неориентированный граф называется четно-нечетным, если найдутся две его вершины, между которыми существует пути как из четного, так и из нечетного числа ребер. Напишите программу, которая:

a. определяет, является ли заданный граф четно-нечетным;

b. В случае отрицательного ответа на пункт (а.) находит максимальное подмножество X вершин графа такое, что для любых двух вершин i и j из X выполняется следующее условие: все пути между i и j состоят из четного числа ребер.

ПРИМЕР

a. in

a. out

3
1 2

NO
2
2 3

Входные данные. Первая строка входного файла содержит число вершин графа N (1≤N≤100), а каждая последующая – пару чисел (i, j), означающих, что в графе присутствует ребро, соединяющее вершины с номерами i и j.

Выходные данные. Первая строка выходного файла должна содержать ответ на пункт (а.) в форме YES/NO. В случае отрицательного ответа на пункт (а.) вторая строка должна содержать количество вершин в множестве X, а третья – номера вершин из этого множества в порядке возрастания, записанные через пробел. Если вариантов решений несколько, то достаточно вывести любое из них.

Задача B. Для игры «Отравленный пирог» используется прямоугольный пирог, разделенный на M «строк» горизонтальными разрезами и на N «столбцов» – вертикальными. Таким образом, пирог должен быть разбит на M × N клеток, правая нижняя из которых «отравлена». Играют двое игроков, ходы делаются по очереди. Каждый ход заключается в том, что игрок выбирает одну из еще не съеденных клеток пирога и съедает все клетки, расположенные левее и выше выбранной (в том числе и выбранную). Проигрывает тот, кто съедает отравленную клетку. Требуется написать программу, которая по заданной игровой позиции определяет все возможные выигрышные ходы для начинающего в этой позиции.

ПРИМЕР

b. in

b. out

3 5
5 4 3

1
3 1

Входные данные. Данные во входном файле расположены в следующем порядке: M, N (1≤M, N≤9), X1, ..., XM. Здесь Xi – число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами и/или символами перевода строки.

Выходные данные. В первую строку выходного файла необходимо вывести количество различных выигрышных ходов К, а в последующие K строк – сами выигрышные ходы. Каждый ход задается парой чисел (i, j), где i – номер (снизу) горизонтального ряда, а j – номер (справа) вертикального ряда, которому принадлежит выбранная клетка (1≤i≤M,1≤j≤N).

Задача C. Имеются три пробирки, вместимостью 100 миллилитров каждая. Первые две пробирки имеют риски, одинаковые на обеих пробирках. Возле каждой риски надписано целое число миллилитров, которое вмещается в часть пробирки от дна до этой риски (см. рисунок). Изначально первая пробирка содержит 100 миллилитров воды, а остальные две пусты. Требуется написать программу, которая выясняет, можно ли отделить в третьей пробирке один миллилитр воды, и если да, то находит минимально необходимое для этого число переливаний. Воду можно переливать из одной пробирки в другую до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какой-либо риски.

ПРИМЕР

с.in

с.out

4
13

YES
8

Входные данные. В первой строке входного файла содержится число рисок N (1≤N≤20), имеющихся на каждой из первых двух пробирок. Затем в порядке возрастания следуют N целых чисел V1 ,...,VN (1≤Vi≤ 100), приписанных рискам. Последняя риска считается сделанной на верхнем крае пробирок (VN = 100).

Выходные данные. В первой строке выходного файла должна содержаться строка «YES», если в третьей пробирке возможно отделить один миллилитр воды, и «NO» – в противном случае. В случае ответа «YES» во вторую строку необходимо вывести искомое количество переливаний.