Anna và Bruno sắp làm bài kiểm tra chữ Hán ở trường. Hai bạn biết \(N\) chữ Hán, được đánh số từ \(0\) đến \(N-1\), và \(M\) từ, được đánh số từ \(0\) đến \(M-1\). Các từ đều được tạo thành từ những chữ Hán mà hai bạn biết. Từ \(i\) có chữ đầu tiên là chữ Hán \(A_i\) và chữ cuối cùng là chữ Hán \(B_i\). Với mọi từ, \(A_i \ne B_i\). Các cặp \((A_i,B_i)\) đôi một khác nhau, nghĩa là nếu \(i \ne j\) thì \((A_i,B_i) \ne (A_j,B_j)\). Mỗi từ còn có một thời gian viết \(C_i\) xác định.
Bài kiểm tra gồm \(Q\) câu hỏi có dạng sau:
Câu hỏi \(j\): Hãy đưa ra một chuỗi nối từ bằng chữ Hán bắt đầu bằng chữ Hán \(S_j\) và kết thúc bằng chữ Hán \(T_j\).
Với mọi câu hỏi, \(S_j \ne T_j\). Các cặp \((S_j,T_j)\) cũng đôi một khác nhau, nghĩa là nếu \(i \ne j\) thì \((S_i,T_i) \ne (S_j,T_j)\).
Một chuỗi nối từ bằng chữ Hán là một dãy từ trong đó chữ cuối của mỗi từ trùng với chữ đầu của từ ngay sau nó, như trong Hình 1. Chuỗi bắt đầu bằng chữ Hán \(S_j\) và kết thúc bằng chữ Hán \(T_j\) có chữ đầu của từ đầu tiên là \(S_j\), và chữ cuối của từ cuối cùng là \(T_j\).
Hình 1: Một chuỗi nối từ bằng chữ Hán bắt đầu bằng \(S_j = \text{「報」}\) và kết thúc bằng \(T_j = \text{「情」}\).
Có thể có nhiều chuỗi trả lời được một câu hỏi. Tuy nhiên, vì thời gian làm bài ngắn, hai bạn phải đưa ra một chuỗi có tổng thời gian viết nhỏ nhất. Nếu có nhiều chuỗi cùng đạt thời gian nhỏ nhất thì có thể chọn bất kỳ chuỗi nào trong số đó. Thời gian viết một chuỗi là tổng thời gian viết của tất cả các từ trong chuỗi.
Ngay trước giờ kiểm tra, Bruno quên mất thời gian viết \(C_{U_0},C_{U_1},\ldots,C_{U_{K-1}}\) của các từ \(U_0,U_1,\ldots,U_{K-1}\). Tình cờ, cả \(K\) từ này đều có cùng chữ đầu tiên. Bruno đã báo cho Anna biết việc này, nhưng không còn đủ thời gian trước khi bài kiểm tra bắt đầu, nên Anna quyết định truyền thông tin cho Bruno trong lúc làm bài. Anna có thể gõ lên bàn để gửi cho Bruno một giá trị \(0\) hoặc \(1\) mỗi lần. Anna muốn số lần gửi ít nhất có thể.
Liệu Bruno có thể đạt điểm tối đa trong bài kiểm tra hay không?
Yêu cầu
Cả Anna và Bruno đều được cung cấp số chữ Hán \(N\); số từ \(M\) cùng chữ đầu và chữ cuối của mỗi từ; số câu hỏi \(Q\) cùng thông tin của từng câu hỏi; số từ \(K\) mà Bruno quên thời gian viết cùng số hiệu của các từ đó. Ngoài ra, Anna được cung cấp thời gian viết của cả \(M\) từ, còn Bruno chỉ được cung cấp thời gian viết của \(M-K\) từ mà cậu không quên.
Hãy viết chương trình để Anna truyền thông tin cho Bruno và Bruno trả lời đúng mọi câu hỏi trong bài kiểm tra.
Chi tiết cài đặt
Bạn phải nộp hai tệp viết bằng cùng một ngôn ngữ lập trình.
Phía Anna
Tệp thứ nhất có tên Anna.c hoặc Anna.cpp, cài đặt chiến lược của Anna. Tệp này phải cài đặt hàm sau:
C++void Anna(int N, int M, int A[], int B[], long long C[],
int Q, int S[], int T[], int K, int U[]);
Hàm này được gọi đúng một lần, ở đầu quá trình thực hiện.
| Tham số |
Ý nghĩa |
N |
Số chữ Hán \(N\). |
M |
Số từ \(M\). |
A |
Mảng độ dài \(M\); A[i] là số hiệu \(A_i\) của chữ đầu tiên của từ \(i\). |
B |
Mảng độ dài \(M\); B[i] là số hiệu \(B_i\) của chữ cuối cùng của từ \(i\). |
C |
Mảng độ dài \(M\); C[i] là thời gian \(C_i\) để viết từ \(i\). |
Q |
Số câu hỏi \(Q\). |
S |
Mảng độ dài \(Q\); S[j] là số hiệu \(S_j\) của chữ đầu tiên trong đáp án cho câu hỏi \(j\). |
T |
Mảng độ dài \(Q\); T[j] là số hiệu \(T_j\) của chữ cuối cùng trong đáp án cho câu hỏi \(j\). |
K |
Số từ \(K\) mà Bruno quên thời gian viết. |
U |
Mảng độ dài \(K\); U[0], U[1], …, U[K-1] là số hiệu \(U_0,U_1,\ldots,U_{K-1}\) của những từ mà Bruno quên thời gian viết. |
Trong chương trình của Anna, bạn có thể gọi hàm sau để gửi một giá trị \(0\) hoặc \(1\) cho Bruno:
Tham số x là giá trị gửi cho Bruno. Hàm này được khai báo trong Annalib.h.
x phải bằng \(0\) hoặc \(1\). Nếu không, kết quả là Wrong Answer [1].- Nếu số lần gọi
Tap vượt quá \(1\,000\), kết quả là Wrong Answer [2].
Nếu một lời gọi Tap bị kết luận là sai, chương trình sẽ bị kết thúc ngay tại thời điểm đó.
Phía Bruno
Tệp thứ hai có tên Bruno.c hoặc Bruno.cpp, cài đặt chiến lược của Bruno. Tệp này phải cài đặt hàm sau:
C++void Bruno(int N, int M, int A[], int B[], long long C[],
int Q, int S[], int T[], int K, int U[], int L, int X[]);
Hàm này được gọi đúng một lần, sau khi hàm Anna đã được gọi.
- Các tham số
N, M, A, B, Q, S, T, K, U giống như khi gọi Anna.
C là mảng chứa thời gian viết của \(M\) từ. Với \(0 \le i < M\), C[i] là thời gian \(C_i\) để viết từ \(i\), nhưng bằng \(-1\) nếu \(i\) là một trong các số hiệu \(U_0,U_1,\ldots,U_{K-1}\).L là số giá trị \(0\) hoặc \(1\) mà Anna đã gửi.X là mảng độ dài \(L\), cho biết Anna đã gửi các giá trị theo thứ tự X[0], X[1], …, X[L-1].
Trong chương trình của Bruno, bạn có thể gọi hàm sau, được khai báo trong Brunolib.h:
w phải là một số nguyên từ \(0\) đến \(M-1\), hoặc bằng \(-1\). Nếu không, kết quả là Wrong Answer [3].- Nếu gọi hàm này sau khi đã gọi
Answer(-1) đủ \(Q\) lần, kết quả là Wrong Answer [4].
Nếu một lời gọi Answer bị kết luận là sai, chương trình sẽ bị kết thúc ngay tại thời điểm đó.
Chương trình phải sử dụng hàm này để lần lượt trả lời đủ \(Q\) câu hỏi. Ở lần trả lời thứ \(j+1\) (\(0 \le j \le Q-1\)), thực hiện các bước sau:
- Với dãy từ dùng để trả lời câu hỏi \(j\), lần lượt gọi
Answer(w) với w là số hiệu từng từ, theo thứ tự từ đầu dãy đến cuối dãy.
- Sau đó gọi
Answer(-1) để kết thúc đáp án của câu hỏi này.
Sau khi hàm Bruno thực hiện xong, các đáp án được kiểm tra như sau:
- Nếu số lần gọi
Answer(-1) nhỏ hơn \(Q\), kết quả là Wrong Answer [5].
- Nếu đáp án của một câu hỏi là dãy có độ dài \(0\), kết quả là Wrong Answer [6].
- Nếu trong đáp án của một câu hỏi, chữ cuối của một từ khác chữ đầu của từ ngay sau nó, kết quả là Wrong Answer [7].
- Nếu trong đáp án của một câu hỏi \(j\), chữ đầu của từ đầu tiên khác \(S_j\) hoặc chữ cuối của từ cuối cùng khác \(T_j\), kết quả là Wrong Answer [8].
- Nếu thời gian viết đáp án của một câu hỏi không phải là nhỏ nhất, kết quả là Wrong Answer [9].
Các quy định khác
Bạn được phép cài đặt thêm các hàm nội bộ và khai báo biến toàn cục. Tuy nhiên, hai tệp nộp sẽ được liên kết cùng chương trình chấm thành một tệp thực thi, nên tất cả các biến toàn cục và hàm nội bộ trong mỗi tệp phải được khai báo static để tránh xung đột với các tệp khác.
Khi chấm chính thức, chương trình được chạy thành hai tiến trình, một cho phía Anna và một cho phía Bruno. Vì vậy, Anna và Bruno không thể chia sẻ các biến toàn cục trong chương trình.
Chương trình nộp của bạn không được tương tác với đầu vào chuẩn, đầu ra chuẩn hay bất kỳ tệp nào khác bằng bất kỳ cách nào.
Biên dịch và chạy thử
Archive tải từ trang cuộc thi có chứa chương trình chấm mẫu để kiểm thử chương trình của bạn, cùng các tệp mẫu tương ứng với những tệp phải nộp. Chương trình chấm mẫu gồm một tệp grader.c hoặc grader.cpp.
Để kiểm thử chương trình C, chạy lệnh:
Bashgcc -O2 -lm grader.c Anna.c Bruno.c -o grader
Để kiểm thử chương trình C++, chạy lệnh:
Bashg++ -O2 grader.cpp Anna.cpp Bruno.cpp -o grader
Nếu biên dịch thành công, tệp thực thi grader sẽ được tạo ra.
Chương trình chấm chính thức khác với chương trình chấm mẫu. Chương trình chấm mẫu chỉ chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.
Dữ liệu vào
Chương trình chấm mẫu đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:
- Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(Q\), \(K\), cách nhau bởi dấu cách: lần lượt là số chữ Hán, số từ, số câu hỏi và số từ mà Bruno quên thời gian viết.
- Dòng thứ \(i+1\) trong \(M\) dòng tiếp theo (\(0 \le i < M\)) chứa ba số nguyên \(A_i\), \(B_i\), \(C_i\), cách nhau bởi dấu cách: từ \(i\) có chữ đầu là \(A_i\), chữ cuối là \(B_i\) và thời gian viết là \(C_i\).
- Dòng thứ \(j+1\) trong \(Q\) dòng tiếp theo (\(0 \le j < Q\)) chứa ba số nguyên \(S_j\), \(T_j\), \(Z_j\), cách nhau bởi dấu cách: đáp án cho câu hỏi \(j\) phải bắt đầu bằng \(S_j\), kết thúc bằng \(T_j\) và có thời gian viết nhỏ nhất là \(Z_j\).
- Dòng thứ \(k+1\) trong \(K\) dòng tiếp theo (\(0 \le k < K\)) chứa một số nguyên \(U_k\). Các từ mà Bruno quên thời gian viết là \(U_0,U_1,\ldots,U_{K-1}\).
Dữ liệu ra
Khi việc thực hiện chương trình kết thúc bình thường, chương trình chấm mẫu in một dòng ra đầu ra chuẩn theo một trong các dạng sau; dấu ngoặc kép không được in ra:
- Nếu đáp án đúng, in số lần gọi
Tap, chẳng hạn Accepted : L = 100.
- Nếu đáp án sai, in loại lỗi, chẳng hạn
Wrong Answer [1].
Ràng buộc
Mọi dữ liệu vào đều thỏa mãn:
- \(2 \le N \le 300\).
- \(1 \le M \le N \times (N-1)\).
- \(0 \le A_i < N\) với mọi \(0 \le i < M\).
- \(0 \le B_i < N\) với mọi \(0 \le i < M\).
- \(A_i \ne B_i\) với mọi \(0 \le i < M\).
- \((A_i,B_i) \ne (A_j,B_j)\) với mọi \(0 \le i < j < M\).
- \(1 \le C_i \le 10^{16} < 2^{54}\) với mọi \(0 \le i < M\).
- \(1 \le Q \le 60\).
- \(0 \le S_j < N\) với mọi \(0 \le j < Q\).
- \(0 \le T_j < N\) với mọi \(0 \le j < Q\).
- \(S_j \ne T_j\) với mọi \(0 \le j < Q\).
- \((S_i,T_i) \ne (S_j,T_j)\) với mọi \(0 \le i < j < Q\).
- Với mọi \(0 \le j < Q\), tồn tại một chuỗi nối từ bằng chữ Hán bắt đầu bằng \(S_j\) và kết thúc bằng \(T_j\).
- \(1 \le K \le 5\).
- \(0 \le U_k < M\) với mọi \(0 \le k < K\).
- \(U_i \ne U_j\) với mọi \(0 \le i < j < K\).
- Các từ mà Bruno quên thời gian viết đều có cùng chữ đầu tiên, nghĩa là:
\[
A_{U_0}=A_{U_1}=\cdots=A_{U_{K-1}}.
\]
Phân nhóm
-
Nhóm 1 — 10 điểm
-
\(Q \le 10\).
- Với mỗi câu hỏi, tồn tại một đáp án có thời gian viết nhỏ nhất sử dụng không quá \(10\) từ.
-
Anna được gọi Tap nhiều nhất \(1\,000\) lần.
-
Nhóm 2 — 22 điểm
-
Anna được gọi Tap nhiều nhất \(180\) lần.
-
Nhóm 3 — 8 điểm
-
Anna được gọi Tap nhiều nhất \(160\) lần.
-
Nhóm 4 — 40 điểm
-
Anna được gọi Tap nhiều nhất \(90\) lần.
-
Nhóm 5 — 20 điểm
Gọi \(L\) là số lần gọi Tap lớn nhất trong tất cả các test của subtask này. Điểm của subtask được tính như sau:
\[
\begin{cases}
20, & L \le 64, \\
\left\lfloor \left(\dfrac{90-L}{90-64}\right)^2 \times 20 \right\rfloor, & 64 < L < 90, \\
0, & L \ge 90.
\end{cases}
\]
Ở đây, \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\).
Ví dụ giao tiếp
Dưới đây là một ví dụ dữ liệu vào của chương trình chấm mẫu và một trình tự gọi hàm tương ứng.
4 5 3 2
2 1 10
0 2 20
3 1 30
0 1 40
3 0 50
3 0 50
3 1 30
0 1 30
1
3
Trình tự gọi hàm
Các lời gọi trong bảng được thực hiện theo thứ tự từ trên xuống dưới.
| Phía Anna |
Phía Bruno |
Anna(...) |
|
Tap(0) |
|
Tap(0) |
|
Tap(1) |
|
Tap(0) |
|
|
Bruno(...) |
|
Answer(4) |
|
Answer(-1) |
|
Answer(2) |
|
Answer(-1) |
|
Answer(1) |
|
Answer(0) |
|
Answer(-1) |
Các lời gọi Tap trong ví dụ này không nhất thiết mang thông tin có ý nghĩa. Các tham số được truyền cho Anna(...) và Bruno(...) như sau:
| Tham số |
Anna(...) |
Bruno(...) |
N |
4 |
4 |
M |
5 |
5 |
A |
{2, 0, 3, 0, 3} |
{2, 0, 3, 0, 3} |
B |
{1, 2, 1, 1, 0} |
{1, 2, 1, 1, 0} |
C |
{10, 20, 30, 40, 50} |
{10, -1, 30, -1, 50} |
Q |
3 |
3 |
S |
{3, 3, 0} |
{3, 3, 0} |
T |
{0, 1, 1} |
{0, 1, 1} |
K |
2 |
2 |
U |
{1, 3} |
{1, 3} |
L |
— |
4 |
X |
— |
{0, 0, 1, 0} |
Hãy chú ý đến hai phần tử C[1] và C[3] của mảng C.
