Це інтерактивна задача.
Передісторія
Минуло пів року, і крамниця I 君 нарешті збанкрутувала. Він вирішив передати її іншому власнику й стати мандрівником, щоб досліджувати широкий невідомий світ.
За записами стародавньої книги він знайшов у глибині великої пустелі підземний палац невідомої цивілізації. Палац складається з $N$ великих печер і $M$ двосторонніх проходів між ними. Книга дозволяє I 君 упізнавати печеру, у якій він перебуває, але не містить схеми проходів, тому шукати легендарні незліченні скарби складно.
Тепер 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++
У каталозі задачі скомпілюйте виконуваний файл такою командою:
Для C:
gcc grader.c explore.c -o explore -O2 -lm- Для C++:
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та інформацію про кількість викликів функцій взаємодії; інакше — відповідне повідомлення про помилку.
Приклад взаємодії
Нехай виконуваний файл прочитав такі дані:
100 200 300 3 2 0 1 1 2
Три числа першого рядка задають обмеження кількості викликів: modify(x) можна викликати не більше 100 разів, query(x) — не більше 200, check(x) — не більше 300.
Два числа другого рядка задають кількість печер і проходів: $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усі $M$ проходів уже записані викликамиreport.
Обмеження та примітки
У задачі 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/2$ | $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$ | C |
| 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$.