Задачи III тура Всероссийской  студенческой олимпиады по информатике 2007
В
1. Прогрессия (10 баллов)
Король Камбузии с детства боится несчастливых арифметических прогрессий с разностью 13. Однажды ему представили список расходов на нужды подданных, состоящий из N чисел. Король потребовал оставить только такую начальную часть списка, в которой не скрывается несчастливая арифметическая прогрессия. Либеральная общественность, считаясь с мнением короля, настаивает, тем не менее, на сохранении как можно большей части списка. Найти максимальное значение K такое, что из первых K чисел списка невозможно выделить M чисел, следующих в порядке их нахождения в списке и образующих последовательные члены несчастливой арифметической прогрессии.
Ввод из файла input.txt. Первая строка содержит два целых положительных числа N и M, разделенных пробелом: N – количество чисел в списке, а  M – недопустимое число членов прогрессии. Вторая строка содержит список расходов в виде целых положительных чисел через пробел.
Ограничения: 2 ≤ N,M ≤ 5000, 1 ≤ Xi ≤ 65000, время 5 СЃ.
Вывод в файл output.txt. Выводится единственное число K- максимальное количество начальных чисел списка, не содержащих в качестве подсписка M последовательных членов несчастливой арифметической прогрессии.
Пример
Р’РІРѕРґ
9 3
5 9 3 22 16 19 35 7 29
Вывод
6
Пояснение: из первых 7 чисел выделяются 3 члена несчастливой прогрессии 9, 22, 35, а из первых 6 чисел можно выделить только 2 таких члена: 9, 22 либо 3, 16.
2. Что в имени твоем (15 баллов)?
В алфавите племени мумба-юмба только три буквы, которые обозначаются как A, B и D. Юношам в день совершеннолетия принято давать взрослые имена, состоящие ровно из N букв. Повторение букв в имени не ограничивается. Если юноша не может представить вождю скальп врага, то в имени присутствует подстрока BAD (возможно, в нескольких экземплярах), иначе такие имена категорически запрещаются. Сколько разных имен может быть в племени мумба-юмба для юношей, запоздавших в развитии (не представивших скальп)?
Ввод из файла input.txt.. Единственная строка содержит целое положительное число N.
Ограничения: 1 ≤ N ≤ 35, время 1 СЃ.
Вывод в файл output.txt. Выводится единственное число - количество имен длины N, содержащих подстроку BAD.
Пример
Р’РІРѕРґ
8
Вывод
1404
3. Даешь квадрат (20 баллов)
Ломаная без самопересечений и самокасаний разделяет четырехугольник на две части, которые не лежат одна внутри другой. Каждая часть представляет собой многоугольник и задается отдельно путем перечисления координат вершин. Определить, является ли исходный четырехугольник квадратом.
Ввод из файла input.txt. Первая строка содержит число тестовых блоков L. Каждый тестовый блок состоит из множества строк. В первой строке находится число M, задающее количество вершин первого многоугольника. Следующие M строк содержат пары целых чисел - координаты точек (Xi, Yi). Если соединить точки в данном порядке, а также первую и последнюю точки, то получится первый многоугольник. Далее аналогично указываются число N – количество вершин второго многоугольника и N строк с координатами его вершин. Таким образом, каждый тестовый блок занимает M + N + 2 строки. Начальная вершина и направление обхода вершин каждого многоугольника могут быть произвольными.
Ограничения: L ≤ 10; 3 ≤ M, N ≤ 1000; В -100 ≤ Xi, Yi ≤ 100; время 1 СЃ.
Вывод в файл output.txt. Для каждого тестового блока выводится единственная строка со значением Yes или No – является четырехугольник квадратом или нет.
Пример
Р’РІРѕРґ
2
6
0 0
0 1
1 1
1 2
2 2
2 0
4
0 2
1 2
1 1
0 1
8
0 0
0 6В В В В
5 5
5 0
3 0
4 1
1 1
2 0
4
1 1
2 0
3 0
4 1
Вывод
Yes
В No
4. Суперробот (25 баллов)
Робот действует по инструкции, написанной на специальном языке. Если инструкция будет не понята (написана не строго по правилам языка), то действия робота непредсказуемы (вплоть до самоуничтожения). Напишите программу, определяющую количество простых команд (слов) правильной инструкции или номер первого ошибочного слова. Правила составления инструкции следующие:
В§ startВ РџР РђР’РЛО1 stop
РџР РђР’РЛО1
В§ РџР РђР’РЛО1 РџР РђР’РЛО4 РџР РђР’РЛО2
В§ РџР РђР’РЛО2
РџР РђР’РЛО2
В§ РџР РђР’РЛО2 РџР РђР’РЛО5 РџР РђР’РЛО3
В§ РџР РђР’РЛО3
РџР РђР’РЛО3
В§ left
В§ right
В§ on45 РџР РђР’РЛО3
В§ hands_upВ РџР РђР’РЛО1 hands_down
РџР РђР’РЛО4
В§ step_ ( РџР РђР’РЛО6 )
РџР РђР’РЛО5
В§ turn_head
РџР РђР’РЛО6
В§ digt
В§ digt РџР РђР’РЛО6
digtВ В В В В В В В В В В В В В В В В
В§ 0|1|2|3|4|5|6|7|8|9
Р’РІРѕРґ РёР· файла input.txt. Слова инструкции разделяются произвольным количеством пробелов.В
Ограничения: длина строки не более 255  символов, время 1 с.
Вывод в файл output.txt. Выводится:
§ в первой строке ОК в случае правильной инструкции, ERR – ошибочной;
§ во второй строке - количество простых команд (слов) правильной инструкции или номер первого ошибочного слова.
Пример 1
Р’РІРѕРґ
startВ on45 left stop
Вывод
OK
В 4
Пример 2
Р’РІРѕРґ
startВ hands_upВ left turn_head on45 left hands_down step_( 19 )В right stop
Вывод
OK
12
Пример 3
Р’РІРѕРґ
В startВ on45 step_( 19 )В left stop
Вывод
ERR
3
5. Шпионские страсти (30 баллов)
Резидент разведки руководит сетью секретных агентов, контактируя только с некоторыми из них. Каждый агент имеет право передавать информацию определенному кругу других агентов. Множество тех партнеров, которым агент передает сведения, не обязано совпадать с множеством принимающих от него информацию агентов. Полученные данные могут распространяться далее и, в конечном счете, доставляются резиденту. Резидент оплачивает каждую передачу сведений от одного агента другому. Величина оплаты зависит от пары агентов и от того, кто из них принимает информацию. Таким образом, общая оплата доставки информации зависит только от цепочки агентов, участвующих в доставке, и действующих расценок.
Стало известно, что определенный агент добыл ценные секретные сведения. В целях надежности резидент решил получить информацию по двум независимым каналам, то есть через разных агентов. Требуется найти минимальный размер затрат резидента для оплаты передачи информации по двум цепочкам агентов, которые начинаются с удачливого агента и заканчиваются резидентом, не пересекаясь друг с другом.
Ввод из файла input.txt.. Первая строка содержит три целых положительных числа N, A и B, разделённых пробелом: N – количество агентов, включая резидента, A – номер начального агента, а  B – номер конечного агента, то есть резидента. Далее следуют N строк, описывающих связи агентов в виде матрицы стоимости Cij. В i-ой строке задаются через пробел стоимости передачи информации от агента с номером i агентам с номерами 1, 2, …, N соответственно в виде целых положительных чисел, то есть значения Ci1, Ci2,…, CiN. Бесплатной передачи информации между агентами не существует. Если i-й агент не связан с j-м, то в соответствующем месте ставится 0. Связи каждого агента с самим собой также заполняются нулями, то есть главная диагональ матрицы стоимостей состоит из нулей.
Ограничения: N ≤ 30, 0 ≤ Cij ≤ 10000,  время 5 СЃ.
Вывод в файл output.txt. В единственной строке выводится минимальная суммарная стоимость передачи информации по двум непересекающимся цепочкам агентов. Если таких цепочек не находится, в файл output.txt выводится строка со словом No.
Пример 1
Р’РІРѕРґ
4 1 4
0 2 3 9
1 0 0 6
1 2 0 5
0 0 0 0
Вывод
16
Пример 2
Р’РІРѕРґ
4 1 3
0 5 2 0
2 0 4 7
0 1 0 0
3 7 0 0
Вывод
No