#112447

Темы: [Интерактивные задачи]

Гений состоит в умении отличать трудное от невозможного.

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

Но на помощь программистам уже спешит Химаил Мутузов, готовый сражаться во имя программирования до последнего!

И вот двое соперников встретились на поле брани. Поле представляет из себя прямоугольник размером $N \times M$, разбитый на клеточки. Теперь каждому полководцу нужно выставить на поле как можно больше своих войск. Для честности Бопанард и Химаил договорились ставить войска по очереди.

Неожиданно выяснилось, что полководцы могут ставить свои войска не во все клетки. Поналеон не вышел ростом, поэтому может ставить войска только на строки, не бо́льшие $K$-ой. Мутузов же был ранен в одном из сражений и потерял левый глаз, поэтому он может ставить войска только на правую половину поля (столбцы нумеруются от $1$ до $M$ слева направо).

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

Вам предстоит помочь Химаилу Мутузову расставить войска. Да и что греха таить, он просто переложил вам на плечи всю расстановку войск, и теперь это — ваша головная боль.

Формат взаимодействия с тестирующей системой

При запуске решения на вход подаются три строки.
Первая из них содержит два целых числа $N$ и $M$ — размеры поля, на котором будет происходить сражение ($1 \leq N, M \leq 100$). Гарантируется, что $M$ чётное. В следующей строке содержится единственное целое число $K$ — номер наибольшей строки, в которую Поналеон может ставить войска ($0 \leq K \leq N$). В следующей строке вводится слово «Mutuzov», если первым войско на поле будет ставить Мутузов, и «Ponaleon», если первым войско на поле будет ставить Поналеон.

Для каждого хода Мутузова выполните следующие действия:

Для занятия клетки с координатами $(i, j)$ выведите через пробел числа $i$ и $j$. Занимаемая клетка обязательно должна быть пустой, то есть в ней не должно быть ни войска Мутузова, ни войска Поналеона.

Для каждого хода Поналеона на вход подаётся:

Слово amour, если Поналеон вынужден пропустить этот ход.
Слово guerre, если Поналеон ставит войско. В этом случае после слова в этой же строке на вход подаются два целых числа $i$ и $j$ — координаты занимаемой войском Поналеона клетки. Гарантируется, что $1 \leq i \leq K$, $1 \leq j \leq M$, и что клетка $(i, j)$ ещё не занималась ни одним войском.

Если после какого-то хода вы считаете, что больше ни одно войско Мутузов поставить не сможет, выведите строку 0 0. После этого ваша программа должна завершиться.

Примеры

Ввод

1 2
1
Mutuzov

Вывод

1 2
0 0

Ввод

2 2
2
Ponaleon
guerre 2 1
guerre 1 1

Вывод

2 2
1 2
0 0

Ввод

4 2
1
Ponaleon
guerre 1 2
amour
guerre 1 1

Вывод

Примечания

В точности соблюдайте формат выходных данных. Вывод каждой строки должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Pascal, fflush(stdout) в С/C++ или cout.flush() в C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

#112448

Побег

Темы: [Интерактивные задачи]

Шрам хочет остаться единственным претендентом на титул короля Саванны. Ради этого он коварно расправился с Муфасой, после чего приказал своим приспешникам-гиенам уничтожить Симбу. К счастью, Симбе улыбнулась удача, и ему предоставился шанс спастись от стаи разъяренных гиен.

Гиены преследуют Симбу на квадратном клетчатом поле, длина и ширина которого равны $k$ клеткам. Как столбцы, так и строки этого поля пронумерованы числами от одного до $k$. Симба находится в одной из клеток поля, находящейся в первой строке. Стая гиен находится в некоторой клетке поля, не совпадающей с той, в которой находится Симба.

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

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

Формат взаимодействия с тестирующей системой

В первой строке программа жюри передает вашей программе одно целое число $k$ ($3 \le k \le 100$) — размер поля, которое необходимо пересечь Симбе. В следующей строке программа жюри передает одно целое число $b$ ($1 \le b \le k$) — номер столбца, в котором находится клетка с Симбой. В следующей строке программа жюри передает два целых числа $x$ и $y$ ($1 \le x, y \le k$) — номера строки и столбца клетки, в которой находится стая гиен. Гарантируется, что эта клетка не является клеткой с Симбой. После этого несколько раз повторяются следующие действия.

Ваша программа передает два целых положительных числа, не превышающих $k$ — номера строки и столбца клетки, в которую необходимо переместиться Симбе. После этого программа жюри передает вашей программе два целых положительных числа, не превышающих $k$ — номера строки и столбца клетки, в которую перемещается стая гиен.

В случае, если после очередного хода Симбы он оказался в клетке строки с номером $k$, в которой нет гиен, завершите программу — это будет означать успешный побег Симбы. За все время работы программы Симба должен сделать не более 1000 ходов.

Пример

Ввод

Вывод

2 1
3 2
4 2

Примечания

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

В языке Pascal: flush(output)
В C/C++: fflush(stdout)
В Java: System.out.flush()
В Python: sys.stdout.flush()

Кроме этого, не забывайте после каждой выведенной строки ставить перевод строки.

#112449

Мощь вампира

Темы: [Интерактивные задачи]

Джейкоб думает очень громко.

Эдвард

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

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

Эдварду срочно необходима ваша помощь, иначе Беллу съедят вампиры из клана Вольтури.

Формат взаимодействия с тестирующей системой

Программа жюри выводит число $n$ в отдельной строке ($1 \le n \le 100$). После этого не более чем $n$ раз повторяются следующие действия.

Ваша программа выводит в отдельной строке строку, состоящую из символов $a_i$ ($a_i = $ + или $a_i = $ -), разделенных пробелами, где $i$-й символ означает, с каким знаком мы просуммируем мощь $i$-го вампира $p_i$ ($-100 \le p_i \le 100$).

Когда вы найдете мощь каждого вампира, вашей программе необходимо вывести в строчку их все по порядку:

answer: $a_1~a_2~...~a_n$,
где $a_i$ — мощь i-го вампира.

Пример

Ввод

2
3
-1

Вывод

+ +
+ -
answer: 1 2

Примечания

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

В языке Pascal: flush(output)
В C/C++: fflush(stdout)
В Java: System.out.flush()
В Python: sys.stdout.flush()

Кроме этого, не забывайте после каждой выведенной строки ставить перевод строки.

#112516

The dog task

Темы: [Паросочетания]

Охотник Боб часто гуляет со своей собакой Ральфом. Боб гуляет с постоянной скоростью и его путь – ломаная (возможно, самопересекающаяся), каждая вершина которой задается двумя целыми числами ( X _i , Y _i ) – декартовыми координатами.

Ральф бегает сам по себе, но обязательно должен встречаться с хозяином в указанных N точках. Собака начинает свой путь одновременно с хозяином в точке ( X ₁ , Y ₁ ) и завешает его вместе с хозяином в точке ( X _N , Y _N ) .

Ральф может бегать с любой скоростью, не превышающей в два раза скорость Боба. Пока Боб идет по прямой из точки в точку, собака ищет деревья, кусты, холмики и прочие интересные места, которые заданы парами целых чисел ( X ^' _j , Y ^' _j ) . Всего таких мест M. Тем не менее, покидая своего хозяина в точке ( X _i , Y _i ) (где 1 ≤ i ≤ N ), Ральф посещает не более одного интересного места перед тем, как опять встретить хозяина в точке ( X _{i

+ 1} , Y _{i

+ 1} ) .

Ваша задача – найти маршрут, удовлетворяющий указанным выше условиям, с максимальным количеством посещаемых интересных мест. Он представляется ломаной, по которой бегает Ральф. Ее вершинами должны быть все точки ( X _i , Y _i ) и посещенные интересные места ( X ^' _j , Y ^' _j ) . Последние должны быть посещены (то есть встречаться в описании пути) не более одного раза.

Пример пути Боба (сплошная линия), набора интересных мест (точки) и одного из лучших путей Ральфа представлены на рисунке:

$\text{[math]}$

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

На первой строке через пробел записаны два числа N и M (2 ≤ N ≤ 100, 0 ≤ M ≤ 100) . Вторая строка содержит N пар целых чисел X ₁ , Y ₁ , ..., X _N , Y _N , разделенных пробелом, описывающих путь Боба. В третьей строке записано M пар целых чисел, ( X ^' ₁ , Y ^' ₁ ) , ... ( X ^' _M , Y ^' _M ) , разделенных пробелом, описывающих интересные места.

Все точки в условии различны и координаты по модулю не превосходят 1000 .

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

В выходном файле должно быть единственное число K – количество вершин в оптимальном маршруте Ральфа.

Примеры

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

4 5
1 4 5 7 5 2 -2 4
-4 -2 3 9 1 2 -1 3 8 -3

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

#112519

Артемида

Темы: [Сканирующая прямая]

Зевс подарил Артемиде, богине охоты, прямоугольный участок земли, чтобы вырастить лес. Левая сторона этого участка — это отрезок неотрицательного луча оси ординат, нижняя сторона — отрезок неотрицательного луча оси абсцисс, а (0, 0) — левый нижний угол участка. Зевс сказал Артемиде выращивать деревья только в точках с целыми координатами.

Артемида любит, когда лес выглядит естественно, и поэтому в её лесу любая прямая, проходящая через два дерева, не параллельна ни оси абсцисс, ни оси ординат.

Иногда Зевс хочет, чтобы Артемида вырубила для него деревья. Деревья должны быть вырублены так, чтобы выполнялись следующие условия:

Зевс хочет, чтобы для него было вырублено хотя бы T деревьев.
Чтобы потом построить прямоугольное футбольное поле для будущих футбольных успехов, Артемида должна вырубить все деревья внутри и на границе некоторой прямоугольной площадки, и ни одно дерево вне этой площадки.
Стороны этой площадки должны быть параллельны осям координат.
В двух противоположных углах площадки должны быть расположены деревья (которые будут вырублены).

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

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

Первая строка ввода содержит единственное число N — количество деревьев в лесу ( 1 < N ≤ 20 000 ). Вторая строка содержит единственное число T — минимальное количество деревьев, которые должны быть вырублены ( 1 < T ≤ N ). Следующие N строк описывают расположение деревьев. Каждая из этих строк содержит по два целых числа X и Y — координаты дерева ( 0 ≤ X , Y ≤ 64 000 ). Решения, работающие только для N < 5000 , будут оцениваться из 50 баллов.

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

Вывод должен содержать единственную строку, в которой записано два целых числа I и J , разделённых пробелом: Артемида должна вырубить деревья на площадке, углами которой будут деревья с номерами I и J (это те деревья, которые описаны в строках входного файла с номерами I + 2 и J + 2 ). Эти числа можно выводить в любом порядке. Возможно, есть несколько способов выбрать эти деревья, и в этом случае вы должны вывести любую из подходящих пар. Гарантируется, что во всех тестах жюри существует хотя бы одно решение.

Примеры

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

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

1 2