#1135

Гипер-каналы

Темы: [Обход в ширину]

Источники: [ Командные олимпиады, Кировские командные турниры, 2001, Задача H ]

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

«Не плюй в телепорт: вылетит — не поймаешь!»

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

К сожалению, гипер-каналы платные — каждый проход через гипер-канал стоит 10 у.е.

Перемещаться по поверхности планеты из одной точки в другую, не используя гипер-каналы, чревато для здоровья (радиация, однако!).

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

Входные данные

Во входном файле записаны сначала два числа — начальные координаты расположения путешественника, затем еще два числа — координаты точки, куда ему надо попасть. Затем записано число N — количество гипер-каналов на планете (0N500). Затем идет N описаний гипер-каналов. Каждый гипер-канал описывается четверкой чисел. Первые два задают координаты одной из соединяемых гипер-каналом точек, последние два — координаты другой. Все координаты — целые числа, не превышающие по модулю 1000000.

Выходные данные

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

Примеры

Входные данные

10 10
-10 -10
3
-10 -10 -10 -10
-10 -10 1 1
10 10 1 1

Выходные данные

#1136

Азбука для слепых

Темы: [Разные комбинаторные структуры]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2000, Задача A ]

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

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

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

Рисунок 1.

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

Требуется подсчитать количество различных букв, которые можно представить таким способом, если прямоугольник имеет размер M∙N.

В качестве примера, все буквы размера 2∙2 приведены на рисунке 2. (Среди комбинаций, отвечающих одной букве, приведена только одна)

Рисунок 2.

Входные данные

Входной файл содержит числа M и N, разделенный пробелом. Поскольку человек одновременно не может воспринимать слишком много информации, M∙N ≤ 30.

Выходные данные

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

Примеры

Входные данные

2 3

Выходные данные

#1137

Каждому по компьютеру!

Темы: [Жадный алгоритм] [Квадратичные сортировки]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2000, Задача B ]

В новом учебном году на занятия в компьютерные классы Дворца Творчества Юных пришли учащиеся, которые были разбиты на N групп. В i-й группе оказалось X_i человек. Тут же перед директором встала серьезная проблема: как распределить группы по аудиториям. Во дворце имеется M ≥ N аудиторий, в j-й аудитории имеется Y_jкомпьютеров. Для занятий необходимо, чтобы у каждого учащегося был компьютер и еще один компьютер был у преподавателя. Переносить компьютеры из одной аудитории в другую запрещается. Помогите директору!

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

Входные данные

На первой строке входного файла расположены числа N и M (1 ≤ N ≤ M ≤ 1000). На второй строке расположено N чисел — X₁, …, X_N(1 ≤ X_i ≤ 1000 для всех 1 ≤ i ≤ N). На третьей строке расположено M чисел Y₁, ..., Y_M (1 ≤ Y_i ≤ 1000 для всех 1 ≤ i ≤ M).

Выходные данные

Выведите на первой строке число P - количество групп, которые удастся распределить по аудиториям. На второй строке выведите распределение групп по аудиториям – N чисел, i-е число должно соответствовать номеру аудитории, в которой должна заниматься i-я группа. (Нумерация как групп, так и аудиторий, начинается с 1). Если i-я группа осталась без аудитории, i-е число должно быть равно 0. Если допустимых распределений несколько, выведите любое из них.

Примеры

Входные данные

3 3
1 2 3
3 4 2

Выходные данные

3
3 1 2

#1141

Нечестная игра

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

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2000, Задача F ]

Есть число N. Играют два игрока, первый может отнять от числа любое число от 1 до K. На каждом следующем ходу можно отнять любое число от 1 до <предыдущий ход>+1. Проигрывает тот, кто возьмет последнюю спичку. Требуется вывести все первые ходы, приводящие к победе.

Петя придумал новую игру. На стол кладется кучка из N спичек, и затем Петя с Ваней по очереди берут спички из кучки. Первым берет Петя, ему разрешается взять от 1 до K спичек. Затем игрок может взять любое количество спичек, не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Например, если N = 10, K = 5, то на первом ходу Петя может взять 1, 2, 3, 4 или 5 спичек, если Петя возьмет 3, то на следующем ходу Ваня может взять 1, 2, 3 или 4, и если Ваня возьмет 1, то Петя затем может взять 1 или 2, и т. д. Проигрывает тот, кто возьмет последнюю спичку.

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

Входные данные

На первой строке входного файла находятся числа N и K, разделенные пробелом. (1 ≤ K ≤ N ≤ 200).

Выходные данные

Выведите в выходной файл все такие X, что, взяв на первом ходу X спичек, Петя выиграет. Если таких X не существует, выведите в выходной файл единственное число - 0. Числа следует разделять пробелами и выводить в порядке возрастания.

Примеры

Входные данные

2 2

Выходные данные

Входные данные

5 4

Выходные данные

1 4

#1184

Найдите последовательность

Темы: [Линейный поиск]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2007, Лига А, Задача B ]

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

Напомним, что если мы сравниваем две последовательности, и у них первые K символов совпадают, а (K+1)-е символы отличаются, то раньше будет идти по алфавиту та, в которой (K+1)-й символ идет раньше по алфавиту. Если же одна последовательность является началом другой, то раньше по алфавиту идет более короткая из них.

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

Входные данные

В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.

Выходные данные

В выходной файл выведите выигрышную последовательность.

Примеры

Входные данные	Выходные данные	Комментарии
4 MAMA	A	Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A
4 ALLO	ALLO	Выигрышной является исходная строка
5 BBABB	ABB