Задача №1 «Кладотолкатель»

Задача №1 «Кладотолкатель»

Входной файл: INPUT. TXT Время на тест: 4 секунды

Выходной файл: OUTPUT. TXT

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

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

Ограничения

1 ≤ W, H ≤ 30

Формат входного и выходного файлов

Первая строка входного файла содержит числа W H. Следующие H строк состоят из W символов каждая и описывают ячейки лабиринта. Пустая ячейка — «.» (ASCII 46), камень — латинская буква «X», кладоискатель — «Y», клад — латинская буква «B», выход — латинская буква «Т».

Если решения не существует, то выходной файл должен содержать слово «NO», иначе — последовательность латинских букв N, S, W, E, обозначающих передвижение кладоискателя на север, юг, запад и восток соответственно.

Пример входного файла

3 3

..Y

.B.

ТХХ

Пример выходного файла

SWNWS

Разбалловка

Решение для W = 1 или H = 1	4	балла
Решение для лабиринта без стен	5	баллов
Решение для общего случая	38	баллов
Интерфейс	3	балла
Итого	50	баллов

Задача №2 «Палиндромическое вычеркивание»

Входной файл: INPUT. TXT Время на тест: 2 секунды

Выходной файл: OUTPUT. TXT

Непустая строка называется палиндромом, если она одинаково читается слева направо и справа налево. Задана строка, состоящая из N прописных латинских букв. Если вычеркнуть из этой строки некоторые символы, можно получить строку-палиндром.

Например, из строки BLOB можно получить палиндромы семью способами:

BLOB, BLOB, BLOB, BLOB, BLOB, BLOB, BLOB.

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

Ограничения

1 ≤ N ≤ 60

Формат входного и выходного файлов

Входной файл содержит исходную строку.

Выходной файл должен содержать найденное число способов.

Пример входного файла 1

BAOBAB

Пример выходного файла 1

22

Пример входного файла 2

Z

Пример выходного файла 2

1

Разбалловка

Решение для 1 ≤ N ≤ 15	5	балла
Решение для 16 ≤ N ≤ 31	12	баллов
Решение для 32 ≤ N ≤ 60	20	баллов
Интерфейс	3	балла
Итого	40	баллов

Задача №3 «Broken NICs»[1]

Входной файл: INPUT. TXT Время на тест: 2 секунды

Выходной файл: OUTPUT. TXT

Имеется N сетевых карт, часть из которых, возможно, не работает. Работоспособность карт проверяют следующим образом: выбирают пару карт и устанавливают их в два компьютера, затем пытаются установить между ними связь. Если связь установлена, то обе проверяемые сетевые карты работоспособны. В противном случае либо одна, либо обе карты не работают.

Требуется по данным о результатах K проверок определить состояние всех карт, для которых это возможно.

Ограничения

2 ≤ N ≤ 1000, 0 ≤ K ≤ 10000

Формат входного и выходного файлов

Входной файл содержит числа N K, за которыми следует K троек чисел ai bi vi, где ai bi — номера проверяемых сетевых карт, vi равно 1, если установить соединение удалось и 0 в противном случае.

Выходной файл должен содержать N чисел, где i-е число равно 0, если i-я карта неисправна, 1, если исправна, и 2, если исправность карты определить невозможно.

Пример входного файла

4 3

1 2 1

3 1 0

3 4 0

Пример выходного файла

Разбалловка

Решение задачи	7	баллов
Интерфейс	3	балла
Итого	10	баллов

Задача №4 «Фотограф и замок»

Входной файл: INPUT. TXT Время на тест: 2 секунды

Выходной файл: OUTPUT. TXT

Старинный замок имеет в плане форму выпуклого N-угольника. Замок находится внутри прямоугольного участка, имеющего форму выпуклого M-угольника, огороженного высоким забором (замок не соприкасается с забором).

Фотограф желает сделать несколько фотографий замка таким образом, чтобы каждая из стен была видна хотя бы на одной фотографии. Позиция для съёмки определяется точкой, находящейся внутри участка, но снаружи замка. Считается, что стена видна из данной позиции, если отрезок, соединяющий её с любой точкой стены, не пересекает других стен. Позиция не может лежать на прямой, содержащей стену.

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

Ограничения

3 ≤ N, M ≤ 100

Все координаты представляют собой целые числа в диапазоне от 0 до 10000.

Формат входного и выходного файлов

Входной файл содержит числа N M x1 y1 … xN yN u1 w1 … uM wM, где xi yi — координаты вершин замка, ui wi — координаты вершин забора. Вершины перечислены в порядке обхода по часовой стрелке.

Выходной файл должен содержать единственное число — минимальное количество фотографий.

Пример входного файла

7 4

1 52

72

Пример выходного файла

3

Разбалловка

Решение задачи для N = 3	2	балла
Решение задачи для общего случая	55	баллов
Интерфейс	3	балла
Итого	60	баллов

Задача №5 «Игра в жадность»

Входной файл: INPUT. TXT Время на тест: 2 секунды

Выходной файл: OUTPUT. TXT

Два игрока играют в следующую игру: они выложили на столе в ряд слева направо N пачек денег, содержащих А1 … АN рублей. Игроки ходят по очереди. На каждом ходе игрок берет слева несколько пачек (не меньше одной, но не больше, чем перед этим взял его соперник). Первый игрок своим первым ходом берет не более K пачек (K ≤ N). Игра заканчивается, когда все деньги разобраны.

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

Ограничения

1 ≤ N ≤ 180, 1 ≤ K ≤ 80,

сумма каждой пачке — целое число в диапазоне от 1 до 20000.

Формат входного и выходного файлов

Во входном файле содержатся числа N K А1 … АN.

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

Пример

INPUT. TXT	OUTPUT. TXT
	14
	5
	18

Разбалловка

Решение для K = 1	3	балла
Решение для 1 ≤ N ≤ 10	10	баллов
Решение для общего случая	24	балла
Интерфейс	3	балла
Итого	40	баллов

[1] NIC (Network Interface Card) — сетевая карта (англ.)