Страница: 1 2 >> Отображать по:
#111236
aliens
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мирко большой фанат различных узоров на полях, в первую очередь странных кругов предположительно инопланетного происхождения. Одной летней ночью он решил создать свой собственный узор на поле своей бабушки. Так как Мирко патриот своей родной Хорватии, то он решил, что узор на поле будет в форме хорватского герба, который, как известно, представляет собой шахматную доску 5 на 5 c 13 красными и 12 белыми квадратами.

Поле бабушки Мирко разделено на \(N\) рядов по \(N\) клеток в каждом. Левый нижний угол поля обозначается координатами \((1, 1)\), правый верхний - координатами \((N, N)\).

Мирко решил выкосить траву только на тех участках, которые соответствуют красным полям на шахматной доске. Он выбрал нечетное число \(M \geq 3\) и так выкосил траву на поле, что каждый квадрат на шахматной доске соответствует квадрату размером \(M \times M\) клеток на поле, и шахматная доска целиком умещается на поле.

На рисунке (см. английскую версию условия) показан пример поля для \(N = 19\) и \(M = 3\). Клетки, на которых трава была выкошена, отмечены серым. Центр узора имеет координаты \((12, 9)\) и отмечен черной точкой

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

Пришельцы нашли одну клетку с выкошенной травой и теперь хотят найти центральную клетку узора Мирко. Они не знают размера узора \(M\).

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

Напишите программу, которая по размеру поля \(N\) (\(1 \leq N \leq 2\,000\,000\,000\)), координатам некоторой клетки с выкошенной травой \((X_0, Y_0)\) и способности взаимодействовать с инопланетным устройством, найдет центральную клетку узора Мирко

На каждом тесте устройство не может быть запущено более 300 раз

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

  • При запуске программы ей будут введены разделенные пробелом числа \(N\), \(X_0\), \(Y_0\).
  • Для того, чтобы узнать есть ли трава в клетке \((X, Y)\) выведите на стандартный поток вывода строку "examine \(X\) \(Y\)". Если координаты \((X, Y)\) не будут находиться внутри поля или вы запустите устройство более 300 раз, то космический корабль потеряет управление и врежется в землю. Вы же в этом случае получите 0 баллов за тест.
  • Устройство поместит в ваш стандартный поток ввода строку "true", если трава в указанной клетке выкошена и "false" в противном случае.
  • Когда программа обнаружит центральную клетку, она должна вывести строку "solution \(X_c\) \(Y_c\)" на стандартный поток вывода. Выполнение вашей программы в этот момент будет автоматически завершено.

      • Для корректной работы вашей программы не забывайте вызывать функцию "flush" после каждого вывода данных. Её заменяет endl в С++, print в Python, writeln в Pascal.

Пример диалога
> 20 4 9
< examine 2 9
> false
< examine 3 9
> true
< examine 6 9
> false
< examine 5 9
> true
< examine 4 3
> true
< examine 2 3
> false
< examine 3 3
> true
< examine 3 1
> false
< examine 3 2
> true
< solution 10 9
#111644
Морской бой
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В рамках Чемпионата Урала планируется проведение турнира стратегий по игре «Морской бой 1D».

Игра проходит на поле, которое представляет собой прямоугольник размером 1 × N клеток. На поле расставляются T кораблей, каждый из которых имеет вид прямоугольника размером 1 × K клеток. Расстановка кораблей на поле является допустимой, если различные корабли не имеют общих клеток и разделены хотя бы одной пустой клеткой. Игровая программа осуществляет выстрелы в клетки поля, а сервер сообщает, является ли выстрел промахом или попаданием в корабль.

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

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

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

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

Задача является интерактивной. После каждого вывода требуется сбросить буфер вывода.

Роль игровой программы исполняет программа жюри. Программа-решение исполняет роль сервера.

Первая строка стандартного ввода программы-решения содержит параметры игры — три числа: N — размер игрового поля, T — число кораблей и K — длина каждого корабля (1 ≤ N ≤ 100 000, 1 ≤ T, 1 ≤ K). Гарантируется, что на поле длины N можно по описанным правилам разместить T кораблей длины K.

После считывания параметров игры программа-решение должна определить и вывести в стандартный поток вывода количество заведомо занятых клеток.

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

  1. Считать из стандартного потока ввода одно число q — номер клетки, в которую игровая программа осуществляет выстрел (1 ≤ q ≤ N). Игровая программа никогда не делает два выстрела в одну и ту же клетку.
  2. Если клетка q является заведомо занятой, вывести в стандартный поток вывода число 1 и завершить работу.
  3. Если клетка q не является заведомо занятой, вывести в стандартный поток два числа, разделенных пробелом: 0 и количество заведомо занятых клеток после этого выстрела. После этого программа-решение переходит к пункту 1 и продолжает взаимодействие с игровой программой.

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

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.
  2. N ≤ 15. Подзадача оценивается в 30 баллов.

  3. N ≤ 3000. Подзадача оценивается в 30 баллов.

  4. N ≤ 100 000. Подзадача оценивается в 40 баллов.

Примеры
Входные данные
8 2 3
4
1
Выходные данные
4
0 5
1
#112035
Силовое поле
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Империя обнаружила мятежников на ледяной планете Хот! По сведениям разведки все командование Альянса Повстанцев сейчас скрывается на базе «Эхо», спрятанной в горах на севере этой суровой планеты.

Для того, чтобы окончательно подавить силы восстания, необходимо в ходе стремительной атаки уничтожить эту базу и скрывающихся на ней мятежников. К сожалению, укрытие хорошо укреплено: в частности, его защищает мощное силовое поле, препятствующее бомбардировкам с орбиты. Силовое поле имеет форму выпуклого многоугольника с вершинами в 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
#112100
Будьте осторожны при купании!_0
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.

Правильный пример на картинке.

#113544
Программирование квадрокоптеров
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

Школьники готовятся к участию в соревновании по программированию квадрокоптеров. Квадрокоптер, который используется в соревновании, может выполнять две команды: подняться вверх на 1 метр и опуститься вниз на 1 метр. Команда подъёма обозначается символом «(», а команда спуска — символом «)».

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

Например, следующие программы являются корректными: «()(())», «((()))». Программа«(((» не является корректной, поскольку квадрокоптер завершает ее выполнение на высоте 3 метра над уровнем земли, программа «())(» также не является корректной, поскольку при выполнении третьей команды квадрокоптер пытается опуститься ниже уровня земли.

Участник соревнования написал корректную программу для квадрокоптера, состоящую из n команд, пронумерованных от 1 до n. Он загрузил её в память квадрокоптера для демонстрации во время соревнования. К сожалению, после загрузки программы в память квадрокоптера участник случайно удалил её на своём компьютере, а квадрокоптер не позволяет выгрузить программу из своей памяти.

К счастью, квадрокоптер поддерживает специальный режим отладки программы. В этом режиме квадрокоптер с загруженной в него программой может отвечать на специальные запросы. Каждый запрос представляет собой два целых числа: l и r, 1 ≤ l ≤ r ≤ n. В ответ на запрос квадрокоптер сообщает, является ли фрагмент загруженной в него программы, состоящий из команд с l-й по r-ю включительно, корректной программой для квадрокоптера, либо нет. Участник хочет с помощью режима отладки восстановить загруженную в квадрокоптер программу.

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

Протокол взаимодействия

Это интерактивная задача.

Сначала на вход подаётся целое число n — количество команд в программе квадрокоптера (2 ≤ n ≤ 50 000).

Для каждого теста жюри зафиксировано число k — максимальное количество запросов. Гарантируется, что k запросов достаточно, чтобы решить задачу. Это число не сообщается программе-решению. Ограничения k в различных подзадачах приведены в таблице системы оценивания. Если программа-решение делает более k запросов к программе жюри, то на этом тесте она получает в качестве результата тестирования «Неверный ответ».

Чтобы сделать запрос, программа-решение должна вывести строку вида «? l r», где l и r — целые положительные числа, задающие фрагмент программы квадрокоптера (1 ≤ l ≤ r ≤ n).

В ответ на запрос программы-решения программа жюри подаёт ей на вход либо строку «Yes», либо строку «No», в зависимости от того, является ли запрошенный фрагмент программы квадрокоптера корректной программой.

Если программа-решение определила ответ на задачу, то она должна вывести строку «! c1c2... cn», где символ ci задаёт i-ю команду в программе квадрокоптера и равен либо «(», либо «)».

После этого программа-решение должна завершиться.

Гарантируется, что в каждом тесте программа в памяти квадрокоптера является фиксированной корректной программой, которая не меняется в зависимости от запросов, произведённых программой-решением.

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

В первом примере n = 4. Единственная возможная корректная программа из двух команд это «()», поэтому из результатов третьего и четвёртого запросов можно сделать вывод, что программа в памяти квадрокоптера — «()()». Поэтому, в частности, ответ на второй запрос действительно «No», так как фрагмент программы «()(» не является корректной программой: если квадрокоптер исполнит именно эти три команды, он останется на уровне одного метра над землёй.

В втором примере n = 6, и произведённых запросов достаточно, чтобы однозначно определить, что программа в памяти квадрокоптера — «((()))».

В тестах из условия k = 150, то есть, разрешается произвести не более 150 запросов.

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест