Империя обнаружила мятежников на ледяной планете Хот! По сведениям разведки все командование Альянса Повстанцев сейчас скрывается на базе «Эхо», спрятанной в горах на севере этой суровой планеты.
Для того, чтобы окончательно подавить силы восстания, необходимо в ходе стремительной атаки уничтожить эту базу и скрывающихся на ней мятежников. К сожалению, укрытие хорошо укреплено: в частности, его защищает мощное силовое поле, препятствующее бомбардировкам с орбиты. Силовое поле имеет форму выпуклого многоугольника с вершинами в N специальных станциях-ретрансляторах. Никакие три станции не располагаются на одной прямой.
Перед тем как начинать операцию по уничтожению повстанцев, требуется лишить их базу силового поля, уничтожив эти N станций точечным бомбометанием. Однако точные координаты этих станций нам неизвестны. Ваша цель — узнать расположение станций-ретрансляторов, чтобы наши войска смогли начать наступление.
На планете введена система координат, устроенная таким образом, что все станции-ре-транс-ля-торы находятся в точках с целыми координатами, не превосходящими C по модулю.
В вашем распоряжении есть зонд-разведчик, оснащенный специальным оборудованием, позволяющим регистрировать станции-ретрансляторы. Если запустить его по прямой над базой повстанцев, по его информации можно будет узнать, сколько станций-ретрансляторов располагаются слева, и сколько — справа от прямой его движения. Станции, находящиеся на его пути, зонд не регистрирует.
С повстанцами надо расправиться как можно скорее: у вас есть время не более чем на 105 запусков этого зонда. Восстановите по полученной от него информации точные координаты станций-ретрансляторов, чтобы мы могли начать наступление, и Империя вас не забудет!
Это интерактивная задача.
При запуске решения на вход подаются два целых числа N (3 ≤ N ≤ 1 000) и C (5 ≤ C ≤ 1 000 000) — количество станций и ограничение на абсолютную величину их координат.
На каждый запуск зонда-разведчика вводится полученная им информация — два целых числа l и r, разделенных пробелом, — количество станций-ретрансляторов слева и справа от траектории его движения соответственно.
Для запуска зонда выведите строку «? x1 y1 x2 y2», где (x1, y1) и (x2, y2) — две точки с целочисленными координатами, лежащие на прямой, по которой должен лететь зонд. Зонд будет лететь в направлении от первой точки ко второй. Точки не должны совпадать. Координаты точек не должны превосходить 5C по модулю.
Как только вы найдете ответ, выведите строку «Ready!», и в следующих N строках выведите координаты станций в любом порядке. После этого ваша программа должна завершиться.
4 5
0 4
0 3
0 3
0 2
1 1
3 1
3 0
3 0
? -1 3 1 3
? -1 2 1 2
? -1 1 0 2
? -1 0 0 2
? 0 0 0 2
? 1 0 1 2
? 2 0 2 2
? 3 0 1 2
Ready!
0 -1
2 1
0 2
-1 0
В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
Программа не должна делать более 105 запросов запуска зонда. При превышении этого количества, тест будет не пройден с вердиктом «Wrong Answer».
Тесты к этой задаче состоят из четырех групп.
- Тест 1. Тест из условия, оцениваемый в ноль баллов.
- Тесты 2–11. В тестах этой группы N = 3, C ≤ 10. Эта группа оценивается в 30 баллов.
- Тесты 12–24. В тестах этой группы N ≤ 50, C ≤ 100. Эта группа оценивается в 30 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.
- В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения
всех тестов из первой и второй группы.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
4 5 -1 0 0 -1 2 1 0 2
28
Инопланетяне с планеты Пандора продолжают изучать жителей Земли. В этот раз они хотят проверить, влияет ли цвет глаз землянина на его зрение. Запланированное исследование состоит из серии экспериментов, для каждого из которых требуется двое землян с глазами одинакового цвета.
В поисках материала для исследования пандорианцы на своей летающей научной базе прибыли на обыкновенный курортный пляж, до отказа забитый греющимися на солнце туристами. Туристы занимают все доступное место на пляже, образуя, таким образом, прямоугольник размером N × M человек. По пляжу они не перемещаются. То есть, каждый турист однозначно задается своими координатами в этом прямоугольнике: номером ряда, в котором он лежит, и номером в этом ряду.
Научная база пандорианцев оборудована двумя специальными антигравитационными лучами, предназначенными для подъема грузов на базу и для их спуска на поверхность близлежащей планеты. Чтобы база не потеряла равновесия, оба луча следует использовать одновременно. Таким образом, пандорианцы могут либо поднять двух произвольных туристов с пляжа на базу, либо опустить двух туристов обратно на пляж. Исследование должно проходить следующим образом. Оператор антигравитационного луча выбирает на пляже двоих туристов и поднимает их на базу. После этого специальная аппаратура определяет цвет глаз каждого из них. Если полученные цвета совпадают, ученые уводят эту пару туристов для проведения очередного эксперимента, и на пляж они больше не возвращаются. Если же они не совпадают, оператор опускает этих туристов обратно на их места на пляже, после чего процесс повторяется.
Обычно такие исследования не вызывали никаких трудностей, но в этот раз ученые заявили оператору, что после завершения исследования на пляже не должно остаться ни одного землянина. Помогите оператору выбирать туристов в таком порядке, чтобы это требование оказалось выполненным. Гарантируется, что это возможно, то есть туристов можно разбить на пары так, чтобы цвет глаз в каждой паре совпадал.
Это интерактивная задача. В процессе тестирования программа-решение будет взаимодействовать с использованием стандартных потоков ввода/вывода с программой-интерактором, сообщающей в ответ на координаты двух очередных выбранных туристов цвета их глаз.
В первой строке заданы два числа: N и M — размеры прямоугольника, который туристы образуют своими телами, где N — это количество рядов, а M — количество человек в одном ряду пляжа. Гарантируется, что туристов на пляже четное число.
Затем программа-решение начинает взаимодействие с программой-интерактором в соответствии со следующим протоколом:
-
Программа-решение выводит в стандартный поток вывода одну строчку, описывающую, каких туристов оператор поднимает с пляжа в этот раз. Строчка должна содержать четыре целых числа
x
1
,
y
1
,
x
2
,
y
2
, где
x
1
— номер ряда, в котором лежит первый турист,
y
1
— его номер в этом ряду, а
x
2
и
y
2
— координаты второго туриста, заданные аналогично. Ряды нумеруются сверху вниз, начиная с
1
, туристы в них — слева направо, начиная с
1
.
Вывод должен завершаться переводом строки и сбросом буфера потока вывода.
Для последнего используйте
- flush(output) в паскале или Delphi;
- fflush(stdout) или cout.flush() в С/C++;
- sys.stdout.flush() в Python;
- Console.out.flush() в Visual Basic.
- После этого программа должна считать из стандартного потока ввода ответ программы-интерактора. Ответ состоит из двух натуральных чисел, не превышающих 200 000 — цвета глаз первого и второго туриста соответственно. Отправка туристов обратно на пляж или на исследование в соответствии с этими данными происходит автоматически. Если их забирают ученые, больше эти земляне на пляж не возвращаются. Их места на пляже остаются пустыми до конца исследования.
- Программа-решение должна завершить работу, когда на пляже не останется ни одного туриста. Гарантируется, что организовать выбор туристов так, чтобы это условие оказалось выполненным, всегда возможно. Количество запросов не должно превышать 262 144.
Тесты к этой задаче состоят из пяти групп.
-
Тест 1. Тест из условия, оценивается в ноль баллов.
-
Тесты 2–7. В тестах этой группы глаза у всех туристов одного цвета,
1 ≤
N
,
M
≤ 50
. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
-
Тесты 8–13. В тестах этой группы
1 ≤
N
,
M
≤ 50
. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
-
Тесты 14-17. В тестах этой группы
1 ≤
N
,
M
≤ 200
. Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы
offline,
т. е. после окончания тура. Тесты в этой группе оцениваются
независимо.
-
Тесты 18-21. В тестах этой группы
1 ≤
N
,
M
≤ 500
. Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы
offline,
т. е. после окончания тура. Тесты в этой группе оцениваются
независимо.
Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
Правильный пример на картинке.
Да пребудет с тобой лама!
В связи с тем, что верным штурмовикам Империи живётся крайне скучно и одиноко,
Императором Первой Галактической Империи был издан указ о создании клонированных лам,
а также проведении акции под лозунгом
Поскольку Дарт Сидиус и Дарт Вейдер фактически уже помирают со скуки на Звезде Смерти, они взялись самостоятельно разработать костюмы для всех лам. На каждом костюме должно быть натуральное число цветных ленточек, причём, так как штурмовики хотят подчеркнуть свою уникальность, не должно быть трёх костюмов с одинаковым числом цветных ленточек. Также после создания костюма с каким-то количеством ленточек, ни Дарт Сидиус, ни Дарт Вейдер не будут создавать костюм с бо́льшим числом ленточек, считая это излишним расточительством.
Дарт Сидиус и Дарт Вейдер создают костюмы по очереди, начинает, естественно, Император. Дарт Сидиус утверждает, что сможет создавать костюмы для лам вечно, однако у Энакина возникло подозрение, что рано или поздно кто-то из них не сможет сделать очередной костюм. Он обратился к вам с тем, чтобы вы помогли ему добиться того, что последний костюм будет сделан именно им.
При каждом ходе Императора на вход подаётся одно целое число — количество ленточек на новом костюме ламы. Гарантируется, что все ходы корректны и что число ленточек на первом косюме не превосходит \(10^5\).
Для каждого хода Дарта Вейдера выведите одно число —
количество ленточек на костюме ламы, который должен сделать Дарт Вейдер.
Если Император не может сделать ход, он сходит с ума, а на вход подаётся строка
«I am your lama!», после чего ваша программа должна завершиться.
10 4 1 I am your lama!
7 2 1
Контесты помимо неотъемлемой развлекательной части должны также иметь и познавательную часть. Поэтому сообщаем вам, что Дарта Вейдера зовут Энакин Скайуокер, он
был взят в ученики джедаем Оби-Ваном Кеноби, который впоследствии и погиб от рук
перешедшего на тёмную силу бывшего рыцаря-джедая Энакина. Сделал будущий Дарт
Вейдер это под влиянием Тёмного владыки ситхов, будущего Императора Первой Галактической Империи Палпатина, которого также зовут Дарт Сидиус.
Составители контеста приносят свои извинения за возможные спойлеры, содержащиеся
в условии задачи.
В точности соблюдайте формат выходных данных. Вывод каждой строки должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Pascal, fflush(stdout) в С/C++ или cout.flush() в C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
Не превращай людей в героев, Джон, героев нет.
А даже будь они — я из другой оперы
Шерлок
Джим Мориарти решил сыграть с Шерлоком Холмсом в небольшую игру. Накануне он похитил миссис Хадсон и заточил её в одной из лабораторий военной базы «Баскервиль», на которой проводят сверхсекретные эксперименты.
Все лаборатории «Баскервиля» пронумерованы числами от \(1\) до \(N\), причём в каждой лаборатории, номер которой меньше, чем номер лаборатории, в которой заключена миссис Хадсон, злодей-консультант оставил записку, в которой написано «Green beard» («Зелёная борода»). А в каждой лаборатории, номер которой больше, чем номер лаборатории, в которой заключена миссис Хадсон, он оставил записку, в которой написано «A woman» («Та женщина»).
К сожалению, дедукция, внутренняя интуиция и даже везение покинули Шерлока Холмса после совершённого им преступления, поэтому он обратился к вам за помощью. Он просит вас отыскать миссис Хадсон как можно быстрее. Помогите ему, проверив не более 60-ти лабораторий, иначе Лестрейд прибудет на базу «Баскервиль» раньше, чем Шерлок спасёт миссис Хадсон.
При запуске решения на вход подаётся единственное целое число \(N\) — количество лабораторий на военной базе «Баскервиль» \((1 \leq N \leq 10^{18})\).
Для проверки очередной лаборатории выведите единственно число — номер лаборатории, которую вы хотите проверить. Если в этой лаборатории лежит записка, вам будет введён её текст.
Иначе вам удалось найти миссис Хадсон, и вам будет введена строка «Mrs. Hudson is here». После этого ваша программа должна завершиться.
1 Mrs. Hudson is here
1
100 A woman Green beard A woman Mrs. Hudson is here
100 1 99 2
В точности соблюдайте формат выходных данных. Вывод каждой строки должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Pascal, fflush(stdout) в С/C++ или cout.flush() в C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
Гений состоит в умении отличать трудное от невозможного.
О нет! Безрассудный Поналеон Бопанард напал на Екатеринбург, в котором совсем недавно прошла Всероссийская олимпиада школьников по информатике и скоро пройдёт Международная студенческая олимпиада по программированию. Коварный император хочет захватить лучших программистов, чтобы те помогли ему составить расписания выпечки багетов.
Но на помощь программистам уже спешит Химаил Мутузов, готовый сражаться во имя программирования до последнего!
И вот двое соперников встретились на поле брани. Поле представляет из себя прямоугольник размером \(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
2 2 3 2 4 2 0 0
В точности соблюдайте формат выходных данных. Вывод каждой строки должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Pascal, fflush(stdout) в С/C++ или cout.flush() в C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.