Задача 1. "Ход конем" (Областная олимпиада школьников 1998. Задача D)

Входной файл input.txt

Выходной файл output.txt

Ограничение по времени 1 секунда на тест

Ограничение по памяти 16 мегабайт

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

Вход

В первой строке текстового файла INPUT.TXT записан начальный пункт в шахматной нотации, во второй строке - конечный пункт в шахматной нотации.

Выход

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

Примеры входа и выхода

INPUT.TXT	OUTPUT.TXT
a1 h3	5
d6 d5	3
c1 c8	5
a8 h1	6
d3 d3	0

Задача 2. "Три сосуда" (Областная олимпиада школьников 1997. Задача B)

Входной файл input.txt

Выходной файл output.txt

Ограничение по времени 1 секунда на тест

Ограничение по памяти 16 мегабайт

В трех сосудах, ёмкости которых известны, находится некоторое количество жидкости. Требуется за наименьшее количество переливаний отмерить заданное количество жидкости (в любом из трех сосудов). Правило переливания: из сосуда А в сосуд Б переливаем до тех пор, пока не опустеет сосуд А или не заполнится сосуд Б.

Вход

В файле INPUT.TXT содержится 7 целых положительных чисел: емкость 1-го сосуда, емкость 2-го сосуда, емкость 3-го сосуда, количество жидкости в 1-м сосуде, количество жидкости во 2-м сосуде, количество жидкости в 3-м сосуде и заданное количество жидкости, которое необходимо отмерить, разделенные пробелами и, может быть, символами конца строки. Все числа не превосходят 100.

Выход

В файл OUTPUT.TXT необходимо записать минимальное количество переливаний. Если решения не найдено, записать в файл фразу "no solution".

Примеры входа и выхода

INPUT.TXT	OUTPUT.TXT
7 5 3 4 4 1 4	0
7 5 3 4 4 1 5	1
17 46 93 11 35 20 40	2
73 61 59 47 38 44 17	no solution
73 61 59 47 38 44 55	9

Задача 3. "Изношенный механизм"(BSU Programming Contest 2004, 2004)

Входной файл REMOTE.IN

Выходной файл REMOTE.OUT

Ограничение по времени 1 секунда на тест

Ограничение по памяти 16 мегабайт

Пульт управления телевизором имеет N кнопок (3 ≤ N ≤ 20) для включения одного из N принимаемых каналов. Когда пульт был новым, нажатие любой из этих кнопок автоматически приводило к отжатию остальных, так что в каждый момент времени только одна из кнопок переключения каналов была включена. К сожалению, с течением времени механизм пульта износился, и некоторые кнопки не отключаются при нажатии других кнопок. Таким образом, одновременно могут быть включены несколько каналов. Выбор нужной программы становится непростой задачей! С другой стороны, финансовые проблемы не позволяют Вам купить новый телевизор или хотя бы отремонтировать пульт... После долгих манипуляций с пультом Вы определили, какие кнопки отжимаются при нажатии кнопки с номером k (1 ≤ k ≤ N) и приноровились включать нужный канал нажатием последовательности из нескольких кнопок. Вам требуется определить минимальное количество нажатий кнопок переключения каналов, необходимых для включения канала с номером k (т.е. для перевода пульта в такое состояние, при котором кнопка k нажата, а все остальные - отжаты). Следует помнить, что повторное нажатие уже нажатой кнопки не вызывает никакого эффекта.

Входные данные находятся в текстовом файле REMOTE.IN, и содержат N+2 строки. Первая строка этого файла содержит значения N и k. Во второй строке записано текущее состояние пульта в виде последовательности из N нулей и единиц, где 1 соответствует нажатой кнопке, а 0 - отжатой. Наконец, каждая из последующих N строк содержит количество кнопок, отжимающихся при нажатии кнопки с номером k (1 ≤ k ≤ N), и их номера (нумерация кнопок начинается с единицы). Числа в строках входного файла разделяются одним или несколькими пробелами. Тесты подобраны таким образом, что задача всегда имеет хотя бы одно решение.

Выходные данные помещаются в текстовый файл REMOTE.OUT. Единственная строка этого файла содержит искомое число нажатий кнопок.

Примеры входа и выхода

REMOTE.IN	REMOTE.OUT
5 3 1 1 0 0 1 4 2 3 4 5 4 1 3 4 5 2 2 4 0 4 1 2 3 4	3

Задача 4. “Фишки“ (VIP-турнир 2008. А)

Вход: marbles.in

Выход: marbles.out

Ограничение памяти 64M

Ограничение времени 1 секунда

Игра ведётся на квадратной доске размером 3 на 3 клетки. Первоначально все клетки пусты. Есть фишки четырёх видов: синие, красные, зелёные и жёлтые. Фишки оцениваются, соответственно, в w_b, w_r, w_g и w_y очков, причём w_b ≤ w_r ≤ w_g ≤ w_y. На каждом ходе вы можете поставить фишку в одну из клеток. Если на этой клетке уже стоит фишка, её предварительно убирают, снятие фишки не считается отдельным ходом. Вы можете ставить фишки на доску сколько угодно раз (запас фишек каждого цвета неограничен), но при этом должны соблюдаться следующие правила:

1) Синюю фишку можно ставить всегда.

2) Красную фишку можно ставить, если на соседней клетке есть синяя фишка.

3) Зелёную фишку можно ставить, если на соседних клетках есть синяя и красная фишки.

4) Жёлтую фишку можно ставить, если на соседних клетках есть синяя, красная и зелёная фишки.

Соседними считаются клетки, имеющие общую сторону.

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

Формат входа

Во входном файле записаны пять целых неотрицательных чисел w_b, w_r, w_g, w_y, w (1 ≤ w_b ≤ w_r ≤ w_g ≤ w_y ≤ 100, 0 ≤ w ≤ 1000).

Формат выхода

Запишите в выходной файл минимальное количество ходов. Если задача не имеет решения, запишите число -1.

Примеры входа и выхода

marbles.in	marbles.out
1 1 1 1 3	3
1 2 4 8 21	7
1 1 1 100 500	-1
7 20 53 94 395	11

Задача 5. Игра (VIP-тнрнир 2011. D)

Входной файл: game.in

Выходной файл: game.out

Ограничение по времени: 1 секунда на тест

Ограничение по памяти: 64M байт

Всем известна игра 15, где надо выстроить изначально неупорядоченную последовательность чисел, перемещая фишки с нанесёнными числами от 1 до 15 в квадрате 4x4. На основе данной игры была разработана другая – поле в ней имеет размер лишь 4 на 2 клетки, на поле 7 фишек, на фишках изображены буквы латинского алфавита и арабские цифры (на каждой фишке – один символ, но на разных фишках могут быть одинаковые символы). Цель игры прежняя – упорядочить в соответствии с образцом стартовую расстановку фишек за минимальное количество ходов. Свободная клетка обозначается специальным символом # и используется для перемещения фишек по полю. Перемещать фишки на свободную клетку разрешается из соседних клеток, имеющих общую грань со свободной. Например, на рисунке более правый символ 0 можно переместить вниз на свободную клетку, тогда 0 будет в нижней клетке, а пустой станет верхняя клетка, либо в свободную клетку переместить букву C или цифру 2.

M	0	0	A
8	C	#	2

Вход

Входной файл содержит четыре строки: две первые строки содержат стартовую комбинацию символов, следующие две - образец. Каждая строка содержит 4 символа (латинский алфавит и арабские цифры), пустая клетка обозначается символом #.

Выход

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

Примеры входных и выходных данных

game.in	game.out
ACM8 002# ACM# 2008	17
rogp mar# prog ram#	26

Задача 6. "Точки" (Зимний Личный Турнир 2006. Задача I)

Входной файл points.in

Выходной файл points.out

Ограничение по времени 1 секунда на тест

Ограничение по памяти 16 мегабайт

Дано N точек {P_j}_j=1...N на плоскости. Для всех или некоторых пар точек заданы бинарные отношения. Возможны отношения восьми разных типов: N, E, S, W, NE, NW, SE, SW. Отношения означают следующее.

P_i N P_j <=> x_j = x_i, y_j > y_i

P_i E P_j <=> x_j > x_i, y_j = y_i

P_i S P_j <=> x_j = x_i, y_j < y_i

P_i W P_j <=> x_j < x_i, y_j = y_i

P_i NE P_j <=> x_j > x_i, y_j > y_i

P_i NW P_j <=> x_j < x_i, y_j > y_i

P_i SE P_j <=> x_j > x_i, y_j < y_i

P_i SW P_j <=> x_j < x_i, y_j < y_i

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

Вход

В первой строке входного файла записаны два целых числа: N - количество точек и M - количество отношений (2 ≤ N ≤ 500, 1 ≤ M ≤ 10,000). Следующие M строк содержат по одному отношению в формате i r j, где i, j - номера точек, r - отношение (1 ≤ i, j ≤ N, r = N | E | S | W | NE | NW | SE | SW).

Выход

В выходной файл запишите слово "yes", если точки можно расположить так, чтобы выполнялись все отношения, и слово "no" в противном случае.

Примеры входа и выхода

points.in	points.out
3 2 1 N 2 2 N 1	no
6 6 1 E 2 1 E 3 2 N 4 3 NW 5 4 SW 6 6 NE 5	yes

Задача 7. Kids' Play (NEERC 2011 Western Subregional Contest. Problem H)

Input file: kids.In

Output file: kids.out

Time limit: 2 seconds

Memory limit: 256 megabytes

It is not easy to keep the children engaged in the day care. Someone's missing Mommy, someone's finger hurts, someone can't decide what they want to play next... Now Natalya Alexandrovna invented a new game. She prepared a bunch of pairs of cards with pictures. There are N desks in her classroom and Natalya Alexandrovna picks N pairs from her supplies and lays two cards on each desk. Of the two cards, one lies face up and the other face down. Even more, from each pair, exactly one card is face up. In the beginning of the game, the K (K ≤ N) kids in her care on that day sit down at the desks, at most one kid at each desk. In the first minute of the game, each kid has to peek at the card laid on the desk face down and move to the desk where the same picture is face up. After that the kids continue to move according to the same rules every following minute. The best part of the game is that kids can continue playing until the parents come to collect them. And even if some kids are collected before others, the remaining ones can still carry on. There's only one problem: Natalya Alexandrovna is unable to tell the parents the location of their child at any given moment. She agrees to give you the initial positions of the kids and information about all cards (even the ones laid face down) to help her respond fast to the parents looking for their offspring.

Input

The first line of input contains the integers N and K (1 ≤ K ≤ N ≤ 10⁵). The following N lines contain two integers each: the numbers of the pictures on the cards laid face up and face down on the i-th desk (the pictures are numbered 1…N). The following K lines also contain two integers each: the number of the desk (1…N) that was the initial position of the j-th kid and the number of minutes from the start of the game to the moment when the parents come looking for the kid (1…10⁹).

Output

Output K lines, one for each kid. The j-th line must contain a single integer, the number of the desk at which the j-th kid is sitting when his/her parents arrive.

Example

kids.in	kids.out
6 4 1 2 2 3 3 1 5 4 4 5 6 6 1 10 3 3 4 101 6 1000	2 3 5 6

Задача 8. Odd Factor (NEERC 2011 Western Subregional Contest. Problem I)

Input file: oddfactor.In

Output file: oddfactor.out

Time limit: 2 seconds

Memory limit: 64 megabytes

Odd factor of an undirected graph is a spanning subgraph (that is, a subgraph containing all vertices of the original graph) where the local degree of each vertex is odd. Given an undirected graph, either construct any of its odd factors or verify that none exists.

Input

The first line of input contains the number of vertices n (1 ≤ n ≤ 10⁵) and the number of edges m (0 ≤ m ≤ 10⁶) of the graph. The follwing m lines describe the edges, with each edge given on a separate line as two integers a_i and b_i (1 ≤ a_i; b_i ≤ n; a_i ≠ b_i), the numbers of the vertices the edge connects.

Output

If an odd factor can be constructed, the first line of output must contain the number of edges in the factor and the following lines must list the edges. If there's no odd factor, output -1 as the answer.

Examples

oddfactor.in	oddfactor.out
4 4 1 2 2 3 3 4 4 1	2 1 2 3 4
4 3 1 2 1 3 1 4	3 1 2 1 3 1 4
3 3 1 2 1 3 2 3	-1

Задача 9. Kingdom Roadmap (NEERC 2011. Problem K)