Задача №112100. Будьте осторожны при купании!_0
Инопланетяне с планеты Пандора продолжают изучать жителей Земли. В этот раз они хотят проверить, влияет ли цвет глаз землянина на его зрение. Запланированное исследование состоит из серии экспериментов, для каждого из которых требуется двое землян с глазами одинакового цвета.
В поисках материала для исследования пандорианцы на своей летающей научной базе прибыли на обыкновенный курортный пляж, до отказа забитый греющимися на солнце туристами. Туристы занимают все доступное место на пляже, образуя, таким образом, прямоугольник размером 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,
т. е. после окончания тура. Тесты в этой группе оцениваются
независимо.
Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
Правильный пример на картинке.
