Tree Boxes#90079

Фермер Джон планирует построить \(N\) (\(1 \leq N \leq 10^5\)) ферм, которые будут соединены \(N-1\) дорожками, образовывая дерево. Обычно когда на одной из ферм возникает проблема, он получает информацию в виде " имеется проблема на одной из ферм на пути от фермы \(A\) к ферме \(B\).

ФД рассматривает ферму как точку на 2-мерной плоскости. Он хотел бы получать информацию о проблемах на одной из ферм в прямоугольных координатах. А именно он хочет получать информацию в виде не более двух прямоугольников, параллельных осям координат, чьё пересечение пустое, а объединение содержит все фермы на пути от \(A\) к \(B\). Вы должны помочь ФД определить, как расположить его фермы так, чтобы условие выполнялось.

Это интерактивная задача. Вы не должны использовать ввод-вывод. Решения, использующие ввод-вывод будут дисквалифицированы. Но Вам разрешено использовать глобальные и статические переменные. Вы должны разработать следующие функции:

void addRoad(int A, int B): обрабатывает дорогу между фермами \(A\) и \(B\) (\(0 \le A, B \le N - 1\)).
void buildFarms(): Определяет, где ФД должен построить все свои фермы.
void notifyFJ(int A, int B): сообщает ФД один или два прямоугольника, которые удовлетворяют вышеописанным условиям

Ваша реализация указанных выше функций должна вызывать следующие функции, перечисленные ниже. Вы можете полагать, что \(\texttt{notifyFJ}\) будет вызвана \(Q\) раз.

int getN(): получить значение \(N\).
int getQ(): получить значение \(Q\).
void setFarmLocation(int ID, int X, int Y): определяет, что ФД должен построить ферму с номером \(ID\) (\(0 \le ID \le N-1\)) в позиции \((X,Y)\), где \((1 \le X, Y \le 10^5 )\). Она будет вызвана из \(\texttt{buildFarms}\).
void addBox(int X1, int Y1, int X2, int Y2): добавляет прямоугольник для сообщения ФД, \((1 \le X1 \le X2 \le 10^5 )\) и \((1 \le Y1 \le Y2 \le 10^5 )\). Вызывается только из \(\texttt{notifyFJ}\).

Интерактивный протокол работает следующим образом: Сначала \(\texttt{addRoad}\) вызывается \(N-1\) раз, чтобы информировать Вашу программу о системе дорог. Затем, будет вызвана \(\texttt{buildFarms}\) и Вы должны будете определить, где ФД должен построить каждую свою ферму соотвественно. А потом будут \(Q\) вызовов \(\texttt{notifyFJ}\) где Вы должны будете сделать один или два вызова \(\texttt{addBox}\) для нотификации ФД.

Гарантируется, что всегда существует корректный способ нотифицировать ФД одним или двумя прямоугольниками. Ограничение по памяти для данной задачи 512 Мбт (в отличие от обычных 256).

Для C++ решений, используйте такой template:

#include "grader.h"

void addRoad(int a, int b){
	// Fill in code here
}

void buildFarms(){
	// Fill in code here
}

void notifyFJ(int a, int b){
	// Fill in code here
}

Для Java решений, исполозуйте такой template:

import java.io.IOException;
// If you find it necessary, you may import other standard libraries here.
public class boxes extends Grader {

  	// Copy this exactly:
        
Override
  	public static void main(String args[]) throws IOException { new boxes().run(); }

        
Override
  	public void addRoad(int a, int b) {
      // Fill in code here
  	}
        
Override
  	public void buildFarms(){
      // Fill in code here
	  }
  	
Override
  	public void notifyFJ(int a, int b){
      // Fill in code here
  	}
}
}

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

Grader calls \(\texttt{addRoad(0,1)}\)

Grader calls \(\texttt{addRoad(1,2)}\)

Grader calls \(\texttt{buildFarms()}\)

Solution calls \(\texttt{setFarmLocation(0,1,1)}\)

Solution calls \(\texttt{setFarmLocation(1,1,2)}\)

Solution calls \(\texttt{setFarmLocation(2,2,2)}\)

Solution ends \(\texttt{buildFarms()}\)

Grader calls \(\texttt{notifyFJ(0,0)}\)

Solution calls \(\texttt{addBox(1,1,1,1)}\)

Solution ends \(\texttt{notifyFJ(0,0)}\)

Grader calls \(\texttt{notifyFJ(0,2)}\)

Solution calls \(\texttt{addBox(1,1,1,2)}\)

Solution calls \(\texttt{addBox(2,2,2,2)}\)

Solution ends \(\texttt{notifyFJ(0,2)}\)

Грайдер завершает свою работу, решение прошло тест.

Автор: Spencer Compton

—Войти и решать

Робот-курьер#50823

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

На вас возложили ответственную задачу по управлением роботом-курьером. Карта, по которой перемещается робот, представляет из себя поле размера \(n \times m\) (\(n\) строк и \(m\) столбцов). Каждая клетка поля может быть либо тротуаром (‘.’), либо проезжей частью дороги (‘+’).

Ровно \(k\) клеток проезжей части содержат регулируемые пешеходные переходы. Гарантируется, что для любого пешеходного перехода ровно две противоположные относительно него соседние с ним по стороне клетки (то есть верхняя и нижняя или левая и правая) являются клетками тротуара. Соответственно, с обоих концов каждого пешеходного перехода расположен светофор.

Робот может перемещаться только по тротуарам и пешеходным переходам. Для определения цвета светофора робот обладает камерой с разрешением \(h \times w\) (где \(w\) четно). Для управления роботом вы можете передавать ему следующие команды:

<<turn \(c\)>>, где \(c \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\), означает поворот в соответствующую сторону (влево, вверх, вправо или вниз);
<<move>> означает перемещение на одну клетку вперед относительно текущего направления;
<<camera>> означает получение изображения с камеры; в ответ на эту команду вы получаете таблицу из \(h \times w\) символов, каждый из которых описывает преобладающий цвет (‘r’, ‘g’ или ‘b’ — красный, зеленый или синий) в соответствующей области пространства перед роботом;
<<wait \(t\)>> означает ожидание в течение \(t\) секунд.

На поворот или перемещение требуется ровно одна секунда. Получение изображения с камеры времени не требует. Каждый светофор горит одним цветом в течение фиксированного периода времени, после чего моментально переключается и горит другим цветом то же время (и так далее). Этот период времени вам неизвестен и может быть разным у разных светофоров, однако гарантируется, что он не превышает \(10^6\).

Светофоры могут находиться на разной высоте и на разном расстоянии сбоку от соответствующего перехода. Если робот находится около перехода с \(i\)-м светофором и смотрит в его направлении, на изображении с камеры светофор будет занимать две клетки в \(a_i\)-й и \((a_i + 1)\)-й снизу строках в столбце на расстоянии \(b_i\) от центра (слева от центра, если \(b_i < 0\), и справа, если \(b_i > 0\)). Для светофора, горящего красным, нижняя из этих двух клеток равна ‘b’, а верхняя равна ‘r’. Для зеленого светофора нижняя клетка равна ‘g’, а верхняя — ‘b’. Остальные клетки на изображении могут любого из трех цветов.

Требуется переместить робота из клетки \((i_1, j_1)\) (\(i_1\)-я сверху строка, \(j_1\)-й слева столбец) в клетку \((i_2, j_2)\). Начинать пересекать пешеходные переходы можно только если на соответствующем светофоре горит зеленый сигнал. Если движение по переходу начато, когда на светофоре горит зеленый сигнал, можно считать, что как минимум в течение еще двух секунд находиться на переходе безопасно, то есть можно гарантированно переместиться на тротуар на противоположной стороне дороги.

Напишите программу, сообщающую роботу команды, безопасно приводящие его из стартовой клетки в конечную. Минимизировать затраченное в пути время не требуется. В изначальной клетке робот находится в направлении <<вверх>> (‘U’).

Каждый тест состоит из нескольких наборов входных данных. В первой строке ввода дано единственное целое число \(t\) — количество наборов входных данных в тесте (\(1 \le t \le 50\)).

Наборы входных данных поступают вам на ввод последовательно: для каждого набора сначала вводится информация о карте и роботе, а затем сразу запускается протокол взаимодействия с интерактором (см. ниже).

В первой строке описания карты даны два целых числа \(n\) и \(m\) — размеры карты (\(1 \le n, m \le 50\)). Следующие \(n\) строк содержат по \(m\) символов каждая и описывают карту. Символ на \(j\)-й позиции \(i\)-й строки описывает клетку с координатами \((i, j)\) и равен ‘.’, если это клетка тротуара, и ‘+’, если это клетка проезжей части.

В следующей строке даны три целых числа \(k\), \(h\) и \(w\) — количество переходов со светофорами и разрешение камеры, соответственно (\(k \le n \cdot m\); \(2 \le h, w \le 8\); \(w\) четно).

Следующие \(3k\) строк описывают светофоры: по три на каждый из \(k\) переходов. В первой строке для \(i\)-го светофора дано положение соответствующего ему перехода \((r_i, c_i)\) (\(1 \le r_i \le n\); \(1 \le c_i \le m\)). Во второй строке дано описание светофора с одного из двух концов перехода в формате <<\(d_{i,1}\) \(a_{i,1}\) \(b_{i,2}\)>>, где \(d_1\) указывает на направление перехода, соответствующее этому светофору, а \(a_{i,1}\) и \(b_{i,1}\) — его высота и расстояние от центра перехода, соответственно (\(d_{i,1} \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\); \(1 \le a_{i,1} < h\); \(1 \le |b_{i,1}| \le \frac{w}{2}\)). В третьей строке в том же формате описывается светофор с противоположной стороны перехода.

Наконец, в последней строке набора входных данных даны четыре целых числа \(i_1\), \(j_1\), \(i_2\) и \(j_2\) — координаты стартовой и конечной клеток, соответственно (\(1 \le i_1, i_2 \le n\); \(1 \le j_1, j_2 \le m\)).

Гарантируется, что все \((r_i, c_i)\) различны, а описания светофоров корректны: направления \(d_{i,1}\) и \(d_{i,2}\), указанные во вводе, противоположны и соответствуют направлениям, в которых от этого перехода расположен тротуар. Также гарантируется, что конечная клетка достижима из стартовой.

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

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

Чтобы повернуть робота, выведите <<turn \(c\)>>, где \(c \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\). В результате выполнения этого действия робот повернется <<лицом>> в соответствующем направлении, и интерактор выведет <<OK>> на отдельной строке.
Чтобы переместить робота, выведите <<move>>. В таком случае робот переместится на одну клетку вперед в том направлении, в котором он повернут. Если это действие успешно, интерактор выведет <<OK>> на отдельной строке. Если при этом робот достиг конечной клетки \((i_2, j_2)\), интерактор перейдет к рассмотрению следующего набора входных данных и подаст соответствующие входные данные на ввод вашей программе (либо завершится и засчитает ваше решение, если это был последний набор входных данных).

Если же робот при таком перемещении попадает в непроходимую клетку, выходит за пределы карты или выезжает на пешеходный переход на красный свет, интерактор выведет <<FAIL>> и завершится с вердиктом Wrong Answer. Во избежание получения некорректного вердикта, считав <<FAIL>>, ваше решение также должно завершиться.
Чтобы сделать снимок, выведите <<camera>>. В ответ интерактор выведет \(h\) строк по \(w\) символов каждая. Каждый символ равен ‘r’, ‘g’ или ‘b’ и задает цвет соответствующего <<пикселя>>. Если непосредственно перед роботом не находится пешеходный переход, все символы будут случайными. Если же робот стоит у перехода, то два символа, соответствующие положению на <<изображении>> светофора напротив, будут отражать цвет этого светофора как описано в условии.
Чтобы подождать \(t\) секунд (\(1 \le t \le 2 \cdot 10^6\)), выведите <<wait \(t\)>>. В ответ интерактор выведет <<OK>> на отдельной строке и обновит состояние всех светофоров, цвет которых за это время поменяется.

Запрещается делать более \(25\) команд ожидания в одной и той же клетке поля. Если ваше решение совершает хотя бы \(26\) запросов ожидания из одной и той же клетки, интерактор в ответ выведет <<FAIL>> и завершится с вердиктом Wrong Answer.

Вывод каждой команды ваша программа должна завершать выводом символа перевода строки (endl, ‘\n’) и сбросом буфера вывода. Сбросить буфер можно с помощью

<<fflush(stdout)>> в C и C++, или <<cout.flush()>> только в C++,
<<System.out.flush()>> в Java,
<<sys.stdout.flush()>> в Python,
и <<Console.Out.Flush()>> в C#.
В Pascal и Delphi сброс буфера при выводе в стандартный поток вывода происходит автоматически.

Решение, не выполняющее эти действия, может получить произвольный вердикт (скорее всего, Time Limit Exceeded или Idleness Limit Exceeded).

В примере из условия добавлены лишние пустые строки, чтобы проиллюстрировать взаимодействие с интерактором и порядок ввода-вывода при этом взаимодействии. В решении выводить эти пустые строки не надо.

Пояснение к примеру

Во втором наборе входных данных в примере:

В клетке \((3, 2)\) нет перехода, поэтому по ней нельзя перемещаться;
При пересечении перехода в \((1, 2)\) в направлении ‘R’ светофор находится на высоте \(2\) и на расстоянии \(-2\) от центра: соответственно, его клетки на изображении располагаются в первом столбце во второй и третьей снизу строках. Для данного снимка они равны ‘b’ в верхней строке и ‘g’ во второй, поэтому его сразу можно пересекать.
При пересечении перехода в \((2, 3)\) в направлении ‘D’ светофор находится на высоте \(1\) и на расстоянии \(2\) от центра, то есть в четвертом столбце в двух нижних строках. На первом изображении он горит красным, а после ожидания (<<wait 10>>) — зеленым.

Задачи на моделирование Интерактивные задачи реализация

—Войти и решать

Петербург?#38516

– Это что за остановка – Бологое иль Поповка? – А с платформы говорят: – Это город Ленинград.
«Вот какой рассеянный», Самуил Маршак
Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.

Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на n вершинах и m ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине v сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.

Алина неуверена в своих силах, поэтому попросила вас помочь ей определить, попала ли она в Петербург. Так как её поезд скоро продолжит свой путь, задать больше 3n вопросов не получится.

Обратите внимание, что в графе могут присутствовать петли и кратные ребра.

Протокол взаимодействия
В первой строке стандартного потока ввода даны два целых числа n и m (1 ≤ n, m ≤ 100000 ) — число вершин и ребер в графе соответственно.

Для того, чтобы узнать очередное ребро, исходящее из u-й вершины (1 ≤ u ≤ n), нужно вывести « ? u ». После этого ваша программа на вход получит целое число v (−2 ≤ v ≤ −1 или 1 ≤ v ≤ n) — v=a+b−u, если существует ребро ab, которое инцидентно вершине u и ещё не было названо , −1, если такого ребра не существует и −2, если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.

Вам разрешается задать не более 3n вопросов.

Чтобы сообщить, что ответ найден, требуется вывести « ! Yes » или « ! No », в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите \( {m \over 2}\) строк, по два целых числа u_i и v_i в каждой (1 ≤ u_i, v_i ≤ n), обозначающих, что ребро (u_i, v_i) является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).

Запрос на вывод ответа не входит в ограничение на 3n запросов.

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

Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.

В первом примере был загадан граф на трех вершинах с ребрами (1, 2) , (2, 3) и (3, 1) .

Во втором примере была загадан граф на четырех вершинах с ребрами (1, 2) , (2, 3) , (3, 4) и (2, 3) .

Ребро, соединяющее вершины u и v, называется мостом, если после его удаления между вершинами u и v не существует пути.

Примеры

№	Входные данные	Выходные данные
1	3 3 2 2 -1 3 -1 -1	? 3 ? 1 ? 2 ? 1 ? 1 ? 3 ! No
2	4 4 2 3 2 -1 4 -1 -1 -1	? 1 ? 2 ? 3 ? 1 ? 3 ? 3 ? 2 ? 4 ! Yes 1 2 3 4

Алгоритмы на графах Интерактивные задачи Мосты

✓ 0✗ 18—Войти и решать