Э
то
интерактивная задача.
Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту.
Лабиринт состоит из N на M (1 ≤ N, M ≤ 30) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в свободной клетке, он может переместится на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетке сработает сенсор и робот останется в той же клетке.
Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.
Протокол интерактивного взаимодействия
Программа должна выводить на стандартный вывод одну строку с действием робота и ждать строки в стандартном вводе с ответом, затем выводить очередную строку с действием и считывать ответ и так далее до тех пор, пока все проходимые клетки лабиринта не будут посещены. Программа должна завершать работу только когда все проходимые клетки будут посещены. Проходимые клетки могут быть посещены несколько раз. Допустимо передвигаться даже если все проходимые клетки уже посещены.
Каждая строка выходных данных должна представлять собой команду для робота. Это должна быть одна из пяти возможных строк: SOUTH, WEST, NORTH, EAST, или DONE. Строка DONE должна быть напечатана после посещения роботом всех проходимых клеток. После вывода DONE программа должна завершать свою работу. Необходимо очищать выходной буфер после вывода каждой команды (flush).
Каждая строка входных данных представляет собой ответ на действие робота. Это может быть строка EMPTY если робот успешно переместился в заданном направлении или строка BLOCKED если робот не смог переместиться из-за того, что клетка, в которую он хотел попасть, непроходима.
Примеры
|
Входные данные |
Выходные данные |
|
NORTH |
BLOCKED |
Это интерактивная задача.
Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту. Лабиринт состоит из N на M (1 ≤ N, M ≤ 30) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в свободной клетке, он может переместится на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетке сработает сенсор и робот останется в той же клетке. Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.
Протокол интерактивного взаимодействия
Программа должна выводить на стандартный вывод одну строку с действием робота и ждать строки в стандартном вводе с ответом, затем выводить очередную строку с действием и считывать ответ и так далее до тех пор, пока все проходимые клетки лабиринта не будут посещены. Программа должна завершать работу только когда все проходимые клетки будут посещены. Проходимые клетки могут быть посещены несколько раз. Допустимо передвигаться даже если все проходимые клетки уже посещены.
Каждая строка выходных данных должна представлять собой команду для робота. Это должна быть одна из пяти возможных строк: SOUTH, WEST, NORTH, EAST, или DONE. Строка DONE должна быть напечатана после посещения роботом всех проходимых клеток. После вывода DONE программа должна завершать свою работу. Необходимо очищать выходной буфер после вывода каждой команды (flush).
Каждая строка входных данных представляет собой ответ на действие робота. Это может быть строка EMPTY если робот успешно переместился в заданном направлении или строка BLOCKED если робот не смог переместиться из-за того, что клетка, в которую он хотел попасть, непроходима.
Пример
| Выходные данные | Входные данные |
| NORTH | BLOCKED |
Мирко большой фанат различных узоров на полях, в первую очередь странных кругов предположительно инопланетного происхождения. Одной летней ночью он решил создать свой собственный узор на поле своей бабушки. Так как Мирко патриот своей родной Хорватии, то он решил, что узор на поле будет в форме хорватского герба, который, как известно, представляет собой шахматную доску 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
Максим и Лёша поехали на сборы в Петрозаводск. После тура они решили не ходить на дорешивание, а поиграть в шахматы. Игра проходит на бесконечной доске, и в какой-то момент у Максима осталось только две ладьи и король, а у Алексея — один король. А на бесконечной доске в такой ситуации победить затруднительно. Тогда Максим заменил своего короля на припасённую ещё одну ладью и ситуация изменилась.
Помогите Максиму поставить мат тремя ладьями на бесконечной доске.
Это интерактивная задача. При запуске решения на стандартный поток ввода поступают 8 чисел — координаты короля и трёх ладей на поле. Координаты не превосходят по модулю 100. Гарантируется, что в начальный момент никакие две фигуры не стоят на одной клетке, и король не находится под боем ни одной из ладей. Первый ход делает Максим.
На каждый ход Максима вводится ответный ход Алексея — перемещение короля dx, dy относительно текущей позиции (0 ≤ |dx|, |dy| ≤ 1). В случае, если |dx| = |dy| = 0, программа должна немедленно завершиться (это означает, что был поставлен мат, пат или сделан некорректный ход).
Для каждого хода выводите на стандартный поток вывода три числа — номер ладьи (1, 2 или 3) и перемещение ладьи lx, ly (|lx| + |ly| > 0;|lx|·|ly| = 0). Ход должен быть корректным, т. е. ладья не может пойти в занятую клетку, перепрыгнуть через другую фигуру. Перемещение ладьи не должно быть больше, чем на 1 000 клеток.
2 0 1 2 0 4 4 1
1 0
-1 -1
0 0
1 0 -1
2 3 0
3 -2 0
Вывод должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в С/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
Программа не должна делать более 40 ходов. Если после хода программы мат не поставлен, а король сделать ход не может, то считается, что тест не пройден.
Ладья может ходить на произвольное количество клеток по горизонтали или по вертикали. Король же может ходить в любую соседнюю клетку, которая не находится под боем ладьи, в том числе, он может «съесть» ладью, если клетка, в которой ладья стоит, не находится под боем другой ладьи. Обратите внимание, что в случае, если король съест ладью, то выигрыш станет невозможным, и тест не будет пройден.
Мат — ситуация в шахматах, когда король находится под ударом ладьи, а игрок не может сделать ни одного хода, чтобы его избежать. Пат — ситуация в шахматах, когда король не находится под ударом ладьи, но при этом игрок не может сделать ни одного хода.
Обратите внимание, что тестирующая система сообщает подробный протокол взаимодействия вашей программы и программы жюри. Гарантируется, что существует программа, которая на всех тестах жюри умеет ставить мат.
Пример ответа тестирующей системы для примера из условия.
Starting position: king on (2 0), rooks on (1 2) (0 4) (4 1)
Turn 1
Max moves 1st rook to (1 1)... OK.
Alex moved king to (3 0)
King on (3 0), rooks on (1 1) (0 4) (4 1)
Turn 2
Max moves 2nd rook to (3 4)... OK.
Alex moved king to (2 0)
King on (2 0), rooks on (1 1) (3 4) (4 1)
Turn 3
Max moves 3rd rook to (2 1)... OK.
It's nowhere for king to go :-(
Game over! Checkmate - Max wins!
Положение фигур по ходу игры.
В рамках Чемпионата Урала планируется проведение турнира стратегий по игре «Морской бой 1D».
Игра проходит на поле, которое представляет собой прямоугольник размером 1 × N клеток. На поле расставляются T кораблей, каждый из которых имеет вид прямоугольника размером 1 × K клеток. Расстановка кораблей на поле является допустимой, если различные корабли не имеют общих клеток и разделены хотя бы одной пустой клеткой. Игровая программа осуществляет выстрелы в клетки поля, а сервер сообщает, является ли выстрел промахом или попаданием в корабль.
В процессе игры про некоторые клетки становится известно, что при любой допустимой расстановке кораблей они принадлежат какому-либо из кораблей. Назовём такие клетки заведомо занятыми.
Игра заканчивается после первого попадания в корабль. Сервер пытается добиться того, чтобы игра продолжалась как можно дольше. Для этого он не фиксирует расстановку кораблей в начале игры, а рассматривает все возможные допустимые расстановки и сообщает о попадании, только если клетка, в которую осуществляется выстрел, является заведомо занятой.
Требуется написать программу, исполняющую роль сервера для этой игры. Сервер сначала загружает параметры игры, а затем взаимодействует с игровой программой, сообщая после каждого выстрела информацию о промахе или попадании, а также количество заведомо занятых клеток.
Задача является интерактивной. После каждого вывода требуется сбросить буфер вывода.
Роль игровой программы исполняет программа жюри. Программа-решение исполняет роль сервера.
Первая строка стандартного ввода программы-решения содержит параметры игры — три числа: N — размер игрового поля, T — число кораблей и K — длина каждого корабля (1 ≤ N ≤ 100 000, 1 ≤ T, 1 ≤ K). Гарантируется, что на поле длины N можно по описанным правилам разместить T кораблей длины K.
После считывания параметров игры программа-решение должна определить и вывести в стандартный поток вывода количество заведомо занятых клеток.
Затем начинается игра. Программа-решение должна последовательно считывать ходы игровой программы из стандартного потока ввода и обрабатывать их следующим образом:
- Считать из стандартного потока ввода одно число q — номер клетки, в которую игровая программа осуществляет выстрел (1 ≤ q ≤ N). Игровая программа никогда не делает два выстрела в одну и ту же клетку.
- Если клетка q является заведомо занятой, вывести в стандартный поток вывода число 1 и завершить работу.
- Если клетка q не является заведомо занятой, вывести в стандартный поток два числа, разделенных пробелом: 0 и количество заведомо занятых клеток после этого выстрела. После этого программа-решение переходит к пункту 1 и продолжает взаимодействие с игровой программой.
Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы успешно пройдены.
8 2 3 4 1
4 0 5 1