Олимпиады

Примеры заданий

Задача 1. Кролик Акопяна

У известного фокусника Амаяка Акопяна есть волшебный цилиндр, в котором лежат разноцветные платки. Всего цветов C (C - натуральное число, не большее 1000). Каждый цвет имеет номер, представляющий собой натуральное число 1..C. Количество платков цвета i равно Ki, не превышающее 10000 (i=1..C). Общее количество платков не превосходит 100000.

Кроме платков в цилиндре имеется волшебный кролик, который и является главным реквизитом. Во время демонстрации фокуса кролик связывает платки уголками так, что получается “цепь”, а Амаяку остается только вытягивать эту “цепь” из цилиндра. Зрители будут очень разочарованы, если в разноцветной цепочке два соседних звена будут одинакового цвета. Поэтому кролику нужно быть бдительным.

Требуется написать программу, вырабатывающую стратегию поведения кролика.

Во входном файле INPUT.TXT записаны числа в следующем порядке:

C

K1

K2

...

KC

Каждое число записано в отдельной строке. В конце файла может быть сколько угодно пустых строк.

В выходной файл OUTPUT.TXT нужно записать последовательность номеров в цепочке так, чтобы соседние звенья были разного цвета и процессе прохода цепочки было выбрано максимально возможное количество платков. Каждое число располагается на отдельной строке, последовательность завершается числом 0.

Пример 1:

INPUT.TXT

3

3

2

1

 

 

OUTPUT.TXT

1

2

1

3

2

1

0

 

Пример 2:

INPUT.TXT

2

1

3

 

 

 

OUTPUT.TXT

2

1

2

0

 

Задача 2A. Ключи

 

На заводе изготавливают замки и ключи к ним. Ключ имеет от 1 до N мест для зубцов (N - натуральное число, не превосходящее 16). На каждом из мест может либо быть, либо не быть зубец.

Для изготовления ключей используется метод отливки с помощью специально подготовленной формы следующего вида:

 

 

 

 

 

Пазы формы обозначены последовательными заглавными латинскими буквами A, B, C, ... Также имеется N прутов, которые без зазора входят в пазы формы. Процесс отливки заключается в том, чтобы поместить в некоторые из пазов пруты и залить в форму материал.

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

Во входном файле INPUT.TXT записано одно число N.

Для выходного файла действие кодируется символом, соответствующим пазу. Например, символ ‘B’ обозначает действие “вынуть прут из второго паза формы”, если во второй паз вставлен прут, или действие “поместить прут во второй паз”, если второй паз свободен. В каждой строке выходного файла OUTPUT.TXT должна быть записана в виде цепочки символов последовательность действий перед очередной отливкой ключа. Первый ключ, содержащий все зубцы, считается уже отлитым. Примеры строк: ‘ABD’, ‘B’, ‘CB’. Все варианты ключей должны быть отлиты в результате выполнения действий, указанных в выходном файле.

 

Пример 1:

 

INPUT.TXT

2

 

 

OUTPUT.TXT

A

BA

A

 

 

 

Пример 2:

 

INPUT.TXT

1

 

 

OUTPUT.TXT

A

 

Задача 2B. Ключи

 

Задача аналогична задаче 2A (Ключи), но имеет дополнительное требование: общее количество действий по помещению прутов в пазы и извлечению их оттуда, записанных в выходном файле OUTPUT.TXT, должно быть минимально возможным.

 

Пример 1:

INPUT.TXT

1

 

 

OUTPUT.TXT

A

 

Пример 2:

INPUT.TXT

2

 

 

OUTPUT.TXT

A

B

A

 

 

Задача 3. Игра со спичками

 

Играют двое: игрок 1 и игрок 2. У каждого из игроков есть непустой набор различных натуральных чисел. Игрок 1 имеет набор k1, k2, ..., kn. Игрок 2 имеет набор l1, l2, ..., lm. Все вышеуказанные числа, а также числа n и m не превосходят 30. Имеется S кучек со спичками. В i-й кучке лежит ti спичек (1

<=ti<=30, i=1..S). Число S - натуральное и не превосходит 5.

Игроки ходят по очереди. Ход игрока 1 заключается в том, что он забирает из любой кучки количество спичек, равное одному из чисел k1, k2, ..., kn. Ход игрока 2 заключается в том, что он забирает из любой кучки количество спичек, равное одному из чисел l1, l2, ..., lm. Первым ходит игрок 1. Игра заканчивается, когда какой-либо из игроков не сможет сделать очередной ход. Если при этом в какой-нибудь из кучек остались спички, то объявляется ничья. Если же спичек не осталось совсем, то проигравшим считается тот, кто сделал последний ход. Другой игрок, соответственно, считается выигравшим.

Назовем игровой ситуацией числовой вектор (a1;a2;...;aS), где ai - количество спичек в кучке i, i=1..S. Поведением игрока назовем правило, по которому каждой игровой ситуации сопоставлен некоторый возможный в этой ситуации ход или число 0, если никакой ход не возможен. Следовать поведению - значит в любой игровой ситуации делать сопоставленный этой ситуации ход или останавливать игру, если ситуации сопоставлено число 0.

Пусть один из игроков - игрок X, а другой - игрок Y. Ситуация называется выигрышной для игрока X (проигрышной для игрока Y), если существует поведение игрока X, следуя которому он выигрывает игру, начавшуюся из этой ситуации, независимо от того, какие ходы делает игрок Y. Если ситуация не является выигрышной ни для игрока 1, ни для игрока 2, она называется ничейной.

Требуется написать программу, которая бы для заданной начальной игровой ситуации определяла, является ли она выигрышной для игрока 1, для игрока 2 или ничейной.

Входной файл INPUT.TXT содержит исходные данные в следующем порядке:

n

k1 k2 ... kn

m

l1 l2 ... lm

S

t1 t2 ... tS

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

В выходной файл OUTPUT.TXT необходимо вывести одно число: 1, 2 или 0. 1 соответствует тому, что приведенная ситуация является выигрышной для игрока 1. 2 соответствует тому, что приведенная ситуация является выигрышной для игрока 2. 0 соответствует ничейной ситуации.

 

Пример 1:

INPUT.TXT

1

2

1

3

2

4 6

 

 

OUTPUT.TXT

1

 

Пример 2:

INPUT.TXT

2

1 3

2

2 4

1

1

 

 

OUTPUT.TXT

2

 

 

Задача 4. Покрытие треугольника

 

Рассмотрим плоскость с системой прямоугольных декартовых координат. На этой плоскости проведены 2 бесконечных набора параллельных прямых, имеющих уравнения , kI Z и , lI Z (Z - множество целых чисел). Эти прямые разбивают всю плоскость на квадраты со стороной 1. Будем называть клетками замкнутые множества

Hk,l = [;]? [;] = {(x,y)|? x? и ? y? } (знак '? ' обозначает декартовое произведение множеств).

Пусть имеются три точки на плоскости: A(xA,yA), B(xB,yB) и C(xC,yC). Назовем треугольником с вершинами A, B и C множество точек, образованное вершинами A, B, C, сторонами AB, BC и AC, а также внутренней областью, ограниченной сторонами треугольника.

Требуется написать программу, которая бы определяла мощность минимального подмножества множества всех клеток {Hk,l}, необходимого для покрытия треугольника.

Во входном файле INPUT.TXT записаны координаты трех вершин треугольника в следующем порядке:

xA yA

xB yB

xC yC

Каждое из чисел целое в интервале от -32767 до 32768 включительно. Числа в строке разделены пробелами. В конце файла может быть сколько угодно пустых строк.

В выходной файл OUTPUT.TXT нужно записать одно число, равное мощности минимального подмножества множества {Hk,l}, покрывающего указанный треугольник.

 

Пример 1:

INPUT.TXT

0 4

0 0

4 0

 

 

OUTPUT.TXT

15

 

Пример 2:

INPUT.TXT

1 1

2 2

3 1

 

 

OUTPUT.TXT

4

 

 

 

 

Задача 5. Водолей

 

Имеется бочка, содержащая неограниченное количество воды ("бездонная"), а также два пустых ведра. Объем первого ведра L1 литров, второго - L2 литров. Разрешены следующие операции:

1. Наполнить первое ведро водой из бочки. Обозначение '+1'.

2. Наполнить второе ведро водой из бочки. Обозначение '+2'.

3. Вылить всю воду из первого ведра в бочку. Обозначение '-1'.

4. Вылить всю воду из второго ведра в бочку. Обозначение '-2'.

5. Перелить максимально возможное количество воды из первого ведра во второе. Обозначение '12'.

6. Перелить максимально возможное количество воды из второго ведра в первое. Обозначение '21'.

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

Во входном файле INPUT.TXT записаны числа в следующем порядке:

L1 L2 L

Все числа натуральные и не превосходят 256. В конце файла может быть сколько угодно пустых строк.

В выходной файл OUTPUT.TXT нужно записать последовательность действий, приводящих к получению требуемого количества воды, если это возможно, или строку 'NO SOLUTION' в противном случае. Последовательность действий начинается с числа, обозначающего количество действий. Это число записывается в отдельной строке. Затем записываются обозначения действий из последовательности, по одному в каждой строке. После выполнения записанных в выходном файле действий в одном из ведер должно получиться требуемое количество воды, а другое ведро должно быть пустым. Последовательность должна быть минимально возможной длины.

 

Пример 1:

INPUT.TXT

3 5 4

 

 

OUTPUT.TXT

7

+2

21

-1

21

+2

21

-1

 

Пример 2:

INPUT.TXT

2 4 3

 

 

OUTPUT.TXT

NO SOLUTION