Это интерактивная задача.
Предыстория
Спустя полгода магазин I 君 наконец перестал держаться на плаву. Он решил передать магазин другому владельцу и стать исследователем, чтобы отправиться в широкий неизведанный мир.
Следуя древней книге, в глубине огромной пустыни он нашёл подземный дворец, созданный неизвестной цивилизацией. Дворец состоит из $N$ больших пещер и $M$ двусторонних проходов между ними. Книга позволяет I 君 узнавать пещеру, в которой он находится, но расположение $M$ проходов в ней не записано. Поэтому ему трудно искать бесконечные сокровища, которые, по преданию, скрыты во дворце.
Однако теперь I 君 обнаружил таинственный механизм, позволяющий получать сведения о дворце. Он решил с его помощью восстановить расположение проходов. Помогите ему.
Условие задачи
Подземный дворец можно представить как неориентированный простой граф с $N$ вершинами и $M$ рёбрами (в простом графе любые две вершины соединяет не более одного непосредственного ребра). Пещеры пронумерованы от $0$ до $n-1$. Сейчас вы не знаете, какие рёбра существуют.
В каждой пещере есть источник света с двумя состояниями: включён и выключен. Пещера освещена только тогда, когда её источник включён. Изначально все источники выключены, а изменить их состояние можно только найденным I 君 механизмом. Он позволяет выполнять четыре операции:
- Передать номер $x$: механизм переключит источники света в пещере $x$ и во всех пещерах, непосредственно соединённых с ней проходом. Включённые источники выключатся, выключенные включатся.
- Передать номер $x$: механизм покажет текущее состояние источника света в пещере $x$.
- Передать два номера $x,y$, сообщив, что вы уверены в существовании прохода между пещерами $x$ и $y$, и записать этот проход с помощью механизма.
- Передать номер $x$: механизм проверит, записаны ли уже все проходы, соединённые с пещерой $x$.
Следующая операция возможна только после завершения предыдущей. Механизм нельзя использовать без ограничений: число применений этих четырёх операций ограничено соответственно $L_m,L_q,M,L_c$. Напишите программу, которая поможет I 君 разумно использовать механизм и правильно найти все $M$ проходов.
Детали реализации
Вам не нужно и не следует реализовывать главную функцию. Реализуйте только функцию explore(N, M), где $N$ и $M$ — число пещер и проходов. Для взаимодействия с библиотекой можно вызывать четыре функции:
modify(x)выполняет операцию 1 с номером $x$. Требуется $0\le x<N$. Возвращаемого значения нет.query(x)выполняет операцию 2 с номером $x$. Требуется $0\le x<N$. Возвращает0или1: источник света в пещере $x$ сейчас выключен (0) или включён (1).report(x, y)выполняет операцию 3 с номерами $x,y$. Требуется $0\le x,y<N$ и $x\ne y$. Возвращаемого значения нет.check(x)выполняет операцию 4 с номером $x$. Требуется $0\le x<N$. Возвращает0или1, причём1возвращается тогда и только тогда, когда все проходы, соединённые с пещерой $x$, уже записаны с помощью операции 3.
При проверке библиотека вызовет explore ровно один раз.
Граф полностью определён до начала взаимодействия и не строится динамически в зависимости от взаимодействия с вашей программой. Поэтому все операции детерминированы, и вам не нужно знать детали их реализации в библиотеке.
Гарантируется, что при соблюдении ограничений на число вызовов время работы библиотеки не превышает 1 секунды. Объём используемой ею памяти постоянен и не превышает 128 МБ.
Способ реализации
В рабочем каталоге предоставлен файл template_explore.cpp/c/pas. Скопируйте его, переименуйте копию в explore.cpp/c/pas и пишите решение на его основе.
Для C++ / C
Убедитесь, что в начале программы есть #include "explore.h".
Интерфейс реализуемой функции:
void explore(int N, int M);Интерфейсы доступных функций взаимодействия:
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);Для Pascal
Синтаксис реализации интерфейса в Pascal достаточно сложен. Пишите решение непосредственно на основе выданного template_explore.pas, а не с нуля.
Интерфейс реализуемой функции:
procedure _explore(N, M : longint);Обратите внимание: функция называется _explore, а не explore. Имя explore приведёт к ошибке компиляции.
Интерфейсы доступных функций взаимодействия:
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;Как тестировать программу
Файлы grader.cpp/c и graderhelperlib.pas в каталоге задачи — предоставленная нами эталонная реализация библиотеки взаимодействия. Реализация, используемая при окончательной проверке, отличается от неё, поэтому решение не должно зависеть от реализации библиотеки.
- Для C/C++ выполните в каталоге задачи соответствующую команду, чтобы получить исполняемую программу:
gcc grader.c explore.c -o explore -O2 -lm
g++ grader.cpp explore.cpp -o explore -O2 -lm- Для Pascal выполните в каталоге задачи:
fpc grader.pas -o"explore" -O2- Полученный исполняемый файл читает из стандартного ввода данные следующего формата. Первая строка содержит три целых числа $L_m,L_q,L_c$, вторая — два целых числа $N,M$ со значениями из условия. Следующие $M$ строк содержат по два целых числа $x,y$, описывающих проход между пещерами $x$ и $y$.
После чтения библиотека ровно один раз вызовет explore, чтобы проверить функцию на введённых данных. После правильного возврата из вашей функции библиотека проверит результат: если он верен, выведет Correct и сведения о числе вызовов функций взаимодействия, иначе — соответствующее сообщение об ошибке.
Примеры
Входные данные 1
100 200 300
3 2
0 1
1 2Примечание
Предположим, исполняемая программа прочитала эти данные. Три числа первой строки задают ограничения: не более 100 вызовов modify(x), 200 вызовов query(x) и 300 вызовов check(x). Два числа второй строки задают число пещер и проходов: $N=3$, $M=2$. Число вызовов report(x, y) не должно превышать $M$, то есть в этом примере 2.
Ниже приведён корректный процесс взаимодействия:
| Программа участника | Библиотека | Пояснение |
|---|---|---|
Вызывает explore(3, 2) |
Начало проверки | |
Вызывает modify(0) |
Операция 1 для пещеры $0$ | |
Вызывает query(2) |
Возвращает 0 |
Источник света в пещере $2$ сейчас выключен |
Вызывает report(0, 1) |
Найден и записан проход $(0,1)$ | |
Вызывает check(0) |
Возвращает 1 |
Все проходы, связанные с пещерой $0$, записаны |
Вызывает report(2, 1) |
Найден и записан проход $(2,1)$ | |
| Завершает работу и возвращает управление | Печатает на экран Correct |
Взаимодействие завершено, результат верен |
Предоставленные файлы
В каталоге задачи:
grader.cpp/cиgraderhelperlib.pas— эталонная реализация библиотеки взаимодействия.explore.hиgrader.pas— заголовочные файлы, детали их содержимого участникам не нужны.template_explore.cpp/c/pas— предоставленные заготовки исходного кода решения.explore1.in,explore2.in,explore3.in— примеры входных данных для тестирования.
Сделайте резервные копии всех предоставленных файлов. При проверке принимается только explore.c/cpp/pas из каталога задачи; изменения других файлов не действуют.
Подзадачи
При окончательной проверке принимается только explore.cpp/c/pas. Изменения остальных файлов в каталоге участника не действуют.
Сначала применяются те же ограничения, что и в обычных задачах. Например, ошибка компиляции даёт 0 баллов за всю задачу; ошибка выполнения, превышение времени или памяти дают 0 баллов за соответствующий тест. Разрешено обращаться только к переменным, определённым вами или предоставленным библиотекой, и соответствующим областям памяти. Попытки обращения к другим областям могут привести к ошибке компиляции или выполнения.
При выполнении этих условий полный балл за тест начисляется тогда и только тогда, когда:
- Каждый вызов функции допустим, а число вызовов
modify,query,checkне превышает соответственно $L_m,L_q,L_c$. - Поскольку число вызовов
reportограничено $M$, каждый такой вызов записывает новое существующее ребро. При вызовеreport(x, y)должен существовать проход между пещерами $x$ и $y$, и ранее не должен был вызываться ниreport(x, y), ниreport(y, x). - Реализованная вами функция
exploreнормально возвращает управление. - К моменту возврата из
exploreвызовамиreportзаписаны все $M$ проходов.
Ограничения
Всего 25 тестов, каждый по 4 балла. Размеры и ограничения каждого теста приведены в таблице.
| Тест | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | Особое свойство |
|---|---|---|---|---|---|---|
| 1 | $3$ | $2$ | $100$ | $100$ | $100$ | Нет |
| 2 | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | Нет |
| 3 | $200$ | $10N$ | $200$ | $4\times10^4$ | $2M$ | Нет |
| 4 | $300$ | $10N$ | $299$ | $9\times10^4$ | $2M$ | Нет |
| 5 | $500$ | $10N$ | $499$ | $1.5\times10^5$ | $2M$ | Нет |
| 6 | $59998$ | $N/2$ | $17N$ | $17N$ | $0$ | A |
| 7 | $99998$ | $N/2$ | $18N$ | $18N$ | $0$ | A |
| 8 | $199998$ | $N/2$ | $19N$ | $19N$ | $0$ | A |
| 9 | $199998$ | $N-1$ | $19N$ | $19N$ | $0$ | A |
| 10 | $99997$ | $N-1$ | $18N$ | $18N$ | $0$ | B |
| 11 | $199997$ | $N-1$ | $19N$ | $19N$ | $0$ | B |
| 12 | $99996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| 13 | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| 14 | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| 15 | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| 16 | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| 17 | $199995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| 18 | $1004$ | $2000$ | $10^7$ | $5\times10^4$ | $2M$ | Нет |
| 19 | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | Нет |
| 20 | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | Нет |
| 21 | $50000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Нет |
| 22 | $100000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Нет |
| 23 | $150000$ | $200000$ | $10^7$ | $10^7$ | $2M$ | Нет |
| 24 | $200000$ | $250000$ | $10^7$ | $10^7$ | $2M$ | Нет |
| 25 | $200000$ | $300000$ | $10^7$ | $10^7$ | $2M$ | Нет |
Ещё раз напоминаем: граф полностью определён до начала взаимодействия и не строится динамически в зависимости от взаимодействия с вашей программой.
Обозначения особых свойств:
- A: степень каждой вершины в точности равна $1$.
- B: для каждого $x>0$ существует ровно одно $y<x$, такое что пещеры $x$ и $y$ непосредственно соединены проходом.
- C: существует перестановка $p_0,p_1,\ldots,p_{N-1}$ чисел от $0$ до $N-1$, такая что для каждого $1\le i<N$ существует проход между пещерами $p_{i-1}$ и $p_i$.
- D: граф связен.
Подсказка: программа может различать перечисленные типы данных по последней цифре переданного $N$.