Đây là bài tương tác.
Bối cảnh
Sau nửa năm, cửa hàng của I cuối cùng không thể tiếp tục kinh doanh. Anh quyết định sang nhượng cửa hàng và trở thành nhà thám hiểm để khám phá thế giới rộng lớn chưa biết.
Theo ghi chép trong sách cổ, anh tìm thấy một cung điện ngầm do một nền văn minh chưa biết tạo ra, nằm sâu trong một sa mạc lớn. Cung điện gồm $N$ hang động lớn và $M$ lối đi hai chiều nối chúng. I có thể nhờ sách cổ xác định hang mình đang đứng, nhưng sách không ghi cấu trúc kết nối của $M$ lối đi, nên anh khó tìm kho báu vô tận được đồn rằng ẩn trong cung điện.
Giờ đây I tìm thấy một cơ quan bí ẩn giúp biết thông tin về cung điện. Anh quyết định dùng nó để xác định cấu trúc kết nối, và nhờ bạn giúp đỡ.
Mô tả bài toán
Cung điện ngầm có thể được biểu diễn bằng một đồ thị đơn vô hướng có $N$ đỉnh và $M$ cạnh (đồ thị đơn có nhiều nhất một cạnh nối trực tiếp giữa hai đỉnh bất kỳ). Các hang được đánh số từ $0$ đến $n-1$. Hiện tại, bạn không biết các cạnh là những cạnh nào.
Mỗi hang có một nguồn sáng với hai trạng thái bật và tắt; hang chỉ sáng khi nguồn sáng được bật. Ban đầu, tất cả nguồn sáng đều tắt, và chỉ cơ quan bí ẩn mà I tìm thấy mới có thể thay đổi trạng thái. Cụ thể, có bốn thao tác:
- Cho cơ quan số hiệu $x$, nó đảo trạng thái nguồn sáng của hang $x$ và các hang có lối đi nối trực tiếp với hang $x$: nguồn đang bật sẽ tắt, nguồn đang tắt sẽ bật.
- Cho cơ quan số hiệu $x$, nó hiển thị trạng thái hiện tại của nguồn sáng trong hang $x$.
- Cho cơ quan hai số hiệu $x,y$, xác nhận rằng có một lối đi nối hang $x$ với hang $y$ và yêu cầu cơ quan ghi lại.
- Cho cơ quan số hiệu $x$, nó kiểm tra xem tất cả lối đi nối với hang $x$ đã được ghi lại hay chưa.
Chỉ sau khi hoàn thành thao tác trước mới có thể thực hiện thao tác tiếp theo. Không thể tùy ý sử dụng cơ quan, nên số lần dùng từng thao tác bị giới hạn, lần lượt là $L_m,L_q,M,L_c$. Nhiệm vụ của bạn là viết chương trình giúp I sử dụng cơ quan hợp lý để tìm đúng $M$ lối đi.
Chi tiết cài đặt
Bạn không cần và cũng không được cài đặt hàm chính. Bạn chỉ cần cài đặt explore(N, M), trong đó $N,M$ lần lượt là số hang và số lối đi. Bạn có thể tương tác với thư viện qua bốn hàm sau:
modify(x)
- Hàm này yêu cầu cơ quan thực hiện thao tác 1 với số hiệu $x$.
- Phải đảm bảo $0\le x<N$. Hàm không trả về giá trị.
query(x)
- Hàm này yêu cầu cơ quan thực hiện thao tác 2 với số hiệu $x$.
- Phải đảm bảo $0\le x<N$. Hàm trả về $0$ hoặc $1$, biểu thị nguồn sáng ở hang $x$ hiện đang tắt ($0$) hoặc bật ($1$).
report(x, y)
- Hàm này yêu cầu cơ quan thực hiện thao tác 3 với các số hiệu $x,y$.
- Phải đảm bảo $0\le x,y<N$ và $x\ne y$. Hàm không trả về giá trị.
check(x)
- Hàm này yêu cầu cơ quan thực hiện thao tác 4 với số hiệu $x$.
- Phải đảm bảo $0\le x<N$. Hàm trả về $0$ hoặc $1$, trong đó trả về $1$ khi và chỉ khi tất cả lối đi nối với hang $x$ đều đã được ghi lại bằng thao tác 3.
Khi chấm, thư viện tương tác gọi explore đúng một lần.
Đồ thị được đảm bảo đã được xác định hoàn toàn trước khi bắt đầu tương tác, không được dựng động theo quá trình tương tác với chương trình của bạn. Vì thế, các thao tác tương tác là xác định; bạn không cần quan tâm cách chúng được cài đặt trong thư viện.
Với các giới hạn số lần gọi, thời gian chạy của thư viện tương tác được đảm bảo không quá $1$ giây; bộ nhớ thư viện sử dụng là cố định và không quá $128$ MB.
Cách cài đặt
Trong thư mục làm việc của thí sinh có tệp template_explore.cpp/c/pas. Hãy sao chép tệp này, đổi tên thành explore.cpp/c/pas, rồi xây dựng lời giải dựa trên đó.
Với C++ / C
- Đảm bảo chương trình bắt đầu bằng
#include "explore.h". - Giao diện hàm
explorecần cài đặt:
void explore(int N, int M);- Giao diện các hàm tương tác có thể gọi:
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);Với Pascal
- Lưu ý: Cú pháp cài đặt giao diện trong Pascal khá phức tạp. Hãy xây dựng lời giải trực tiếp từ tệp
template_explore.pasđược cung cấp, thay vì tự viết mã từ đầu. - Giao diện hàm
explorecần cài đặt:
procedure _explore(N, M : longint);- Lưu ý: Tên hàm ở đây là
_explore, không phảiexplore; dùngexploresẽ gây lỗi biên dịch. - Giao diện các hàm tương tác có thể gọi:
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;Cách kiểm tra chương trình
Các tệp grader.cpp/c và graderhelperlib.pas trong thư mục đề bài là bản cài đặt tham khảo của thư viện tương tác. Bản thư viện dùng khi chấm cuối cùng khác bản tham khảo, vì vậy lời giải không được phụ thuộc vào cách cài đặt thư viện.
Với C/C++
Dùng các lệnh sau trong thư mục bài này để biên dịch thành chương trình thực thi:
Với C:
gcc grader.c explore.c -o explore -O2 -lm
Với C++:
g++ grader.cpp explore.cpp -o explore -O2 -lm
Với Pascal
Dùng lệnh sau trong thư mục bài này để biên dịch thành chương trình thực thi:
fpc grader.pas -o"explore" -O2
Với chương trình thực thi đã biên dịch
Chương trình đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:
Dòng đầu chứa ba số nguyên $L_m,L_q,L_c$; dòng thứ hai chứa hai số nguyên $N,M$, có ý nghĩa như mô tả trong đề.
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x,y$, mô tả một lối đi nối hang $x$ với hang $y$.
Sau khi đọc xong, thư viện gọi explore đúng một lần để kiểm tra hàm của bạn với dữ liệu đã đọc. Sau khi hàm trả về bình thường, thư viện kiểm tra kết quả: nếu đúng, in Correct và thông tin về số lần gọi các hàm tương tác; nếu không, in thông báo lỗi tương ứng.
Ví dụ
Giả sử chương trình thực thi đọc dữ liệu sau:
Dữ liệu vào
100 200 300 3 2 0 1 1 2
Ghi chú
Ba số ở dòng đầu lần lượt là giới hạn số lần gọi ba thao tác: không được gọi modify(x) quá $100$ lần, query(x) quá $200$ lần và check(x) quá $300$ lần.
Hai số ở dòng thứ hai lần lượt là số hang và số lối đi: $N=3,M=2$.
Không được gọi report(x, y) quá $M$ lần, tức là không quá $2$ lần trong ví dụ này.
Sau đây là một quá trình tương tác đúng:
| Chương trình thí sinh | Thư viện tương tác | Giải thích |
|---|---|---|
Gọi explore(3, 2) |
Bắt đầu kiểm tra. | |
Gọi modify(0) |
Thực hiện thao tác 1 với hang $0$. | |
Gọi query(2) |
Trả về $0$ | Nguồn sáng trong hang $2$ hiện đang tắt. |
Gọi report(0, 1) |
Phát hiện và ghi lại lối đi $(0,1)$. | |
Gọi check(0) |
Trả về $1$ | Tất cả lối đi liên quan đến hang $0$ đã được ghi lại. |
Gọi report(2, 1) |
Phát hiện và ghi lại lối đi $(2,1)$. | |
| Kết thúc chạy và trả về | In Correct lên màn hình |
Tương tác kết thúc, kết quả đúng. |
Các tệp được cung cấp
Trong thư mục bài này:
grader.cpp/cvàgraderhelperlib.paslà bản cài đặt tham khảo của thư viện tương tác.explore.hvàgrader.paslà các tệp tiêu đề; thí sinh không cần quan tâm nội dung cụ thể.template_explore.cpp/c/paslà mã nguồn mẫu cho lời giải được cung cấp.explore1.in,explore2.in,explore3.inlà các đầu vào mẫu để kiểm tra.
Hãy sao lưu tất cả các tệp được cung cấp. Bộ chấm chỉ thu tệp explore.c/cpp/pas trong thư mục bài này; sửa các tệp khác không có tác dụng.
Nhiệm vụ con
Khi chấm cuối cùng, chỉ thu explore.cpp/c/pas; sửa các tệp khác trong thư mục thí sinh không có tác dụng.
Bài này trước hết chịu các giới hạn giống bài thông thường. Ví dụ, lỗi biên dịch khiến cả bài được $0$ điểm; lỗi chạy, vượt thời gian hoặc bộ nhớ khiến điểm kiểm tra tương ứng được $0$ điểm. Bạn chỉ được truy cập các biến do mình định nghĩa hoặc do thư viện cung cấp, cùng vùng nhớ tương ứng; cố truy cập vùng nhớ khác có thể gây lỗi biên dịch hoặc lỗi chạy.
Với các điều kiện trên, tại một điểm kiểm tra, bạn được điểm tối đa khi và chỉ khi:
- Mọi lời gọi hàm đều hợp lệ, và số lần gọi
modify,query,checklần lượt không vượt quá $L_m,L_q,L_c$. - Do
reportchỉ được gọi tối đa $M$ lần, mỗi lời gọi phải ghi lại một cạnh mới và thực sự tồn tại. Tức là khi gọireport(x, y), phải có lối đi nối hang $x$ với hang $y$, và trước đó chưa từng gọireport(x, y)hayreport(y, x). - Hàm
explorecủa bạn trả về bình thường. - Khi
exploretrả về, bạn đã gọireportđể ghi lại tất cả $M$ lối đi.
Giới hạn
Bài có $25$ điểm kiểm tra, mỗi điểm kiểm tra $4$ điểm. Quy mô dữ liệu và các giới hạn được cho trong bảng sau.
| Điểm kiểm tra | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | Tính chất đặc biệt |
|---|---|---|---|---|---|---|
| $1$ | $3$ | $2$ | $100$ | $100$ | $100$ | Không có |
| $2$ | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | Không có |
| $3$ | $200$ | $10N$ | $200$ | $4\times10^4$ | $2M$ | Không có |
| $4$ | $300$ | $10N$ | $299$ | $9\times10^4$ | $2M$ | Không có |
| $5$ | $500$ | $10N$ | $499$ | $1.5\times10^5$ | $2M$ | Không có |
| $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$ | $10^7$ | $2M$ | Không có |
| $19$ | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | Không có |
| $20$ | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | Không có |
| $21$ | $50000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Không có |
| $22$ | $100000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Không có |
| $23$ | $150000$ | $200000$ | $10^7$ | $10^7$ | $2M$ | Không có |
| $24$ | $200000$ | $250000$ | $10^7$ | $10^7$ | $2M$ | Không có |
| $25$ | $200000$ | $300000$ | $10^7$ | $10^7$ | $2M$ | Không có |
Nhắc lại: đồ thị dùng để kiểm tra được đảm bảo đã được xác định hoàn toàn trước khi bắt đầu tương tác, không được dựng động theo tương tác với chương trình của bạn.
Ý nghĩa các ký hiệu trong cột tính chất đặc biệt:
A: Mỗi đỉnh có bậc đúng bằng $1$.
B: Với mỗi $x>0$, có đúng một $y<x$ sao cho hang $x$ và hang $y$ có lối đi nối trực tiếp.
C: Tồn tại một hoán vị $p_0,p_1,\ldots,p_{N-1}$ của các số từ $0$ đến $N-1$ sao cho với mọi $1\le i<N$, có một lối đi nối hai hang có số hiệu $p_{i-1}$ và $p_i$.
D: Đồ thị liên thông.
- Gợi ý: Chương trình có thể phân biệt các loại dữ liệu trên bằng chữ số hàng đơn vị của $N$ được truyền vào.