JOI 2025 - Tuyển chọn mùa xuân - Ngày 2 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2025 - Ambulance	100 (p)	3.0s	1G
2	JOI 2025 - Collecting Stamps 4	100 (p)	3.0s	1G
3	JOI 2025 - Space Thief	100 (p)	2.0s	1G

1. JOI 2025 - Ambulance

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Vương quốc IOI có lãnh thổ được biểu diễn bằng một lưới vuông gồm \(L\) hàng và \(L\) cột. Các hàng được đánh số từ \(1\) đến \(L\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(L\) từ trái sang phải. Ô ở hàng \(i\), cột \(j\) được ký hiệu là \((i,j)\).

Gần đây, dịch bệnh lan rộng khiến nhu cầu chăm sóc y tế trong vương quốc tăng cao. Vì vậy, quốc vương Bitaro quyết định xây bệnh viện tại bốn ô ở góc lưới: \((1,1)\), \((1,L)\), \((L,1)\) và \((L,L)\). Mỗi bệnh viện được trang bị một xe cứu thương.

Bitaro thận trọng nên muốn mô phỏng tình huống có bệnh nhân cần được cứu giúp. Trong kịch bản của ông, tại thời điểm \(0\), có \(N\) bệnh nhân gửi yêu cầu cứu giúp. Bệnh nhân thứ \(k\) (\(1 \le k \le N\)) ở ô \((X_k,Y_k)\). Ông muốn biết liệu có thể đưa tất cả bệnh nhân đến một trong các bệnh viện không muộn hơn thời điểm \(T\) hay không.

Các xe cứu thương vận chuyển bệnh nhân theo những quy tắc sau:

Mỗi xe có thể bắt đầu di chuyển từ thời điểm \(0\) trở đi. Xe lặp lại việc xuất phát từ bệnh viện của mình, đi đến ô có bệnh nhân, đón bệnh nhân, rồi quay về bệnh viện đó để trả bệnh nhân. Xe có thể không thực hiện chuyến nào.
Mỗi xe chở được nhiều nhất một bệnh nhân tại một thời điểm.
Mỗi xe chỉ được đưa bệnh nhân đến bệnh viện nơi xe được bố trí ban đầu. Không được cho bệnh nhân xuống xe tại ô không có bệnh viện.
Mỗi lần di chuyển sang một ô kề trên, dưới, trái hoặc phải mất một đơn vị thời gian. Thời gian đón và trả bệnh nhân có thể bỏ qua.
Các xe thuộc những bệnh viện khác nhau được phép ở cùng một ô tại cùng một thời điểm.

Bitaro không tự xác định được kết quả của kịch bản này nên nhờ bạn giúp. Cho kích thước lãnh thổ và thông tin về kịch bản, hãy xác định có thể đưa tất cả bệnh nhân đến bệnh viện không muộn hơn thời điểm \(T\) hay không.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(L,N,T\).
Trong \(N\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(X_k,Y_k\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In một dòng chứa Yes nếu có thể đưa tất cả bệnh nhân đến bệnh viện không muộn hơn thời điểm \(T\); nếu không, in No.

Ràng buộc

\(3 \le L \le 10000\).
\(1 \le N \le 160\).
\(1 \le T \le 20000\).
\(1 \le X_k \le L\) và \(1 \le Y_k \le L\) với mọi \(1 \le k \le N\).
\((X_k,Y_k)\) không trùng với bất kỳ ô nào trong bốn ô \((1,1)\), \((1,L)\), \((L,1)\), \((L,L)\).
Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

\(4\) điểm: \(T \le 50\).
\(8\) điểm: \(T \le 160\).
\(5\) điểm: \(N \le 10\).
\(18\) điểm: \(N \le 20\).
\(15\) điểm: \(N \le 45\), \(L\) là số lẻ và \(Y_k=\frac{L+1}{2}\) với mọi \(1 \le k \le N\).
\(31\) điểm: \(N \le 45\).
\(19\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Yes

Giải thích

Đưa bệnh nhân thứ \(1\) và thứ \(2\) đến bệnh viện ở ô \((1,1)\), bệnh nhân thứ \(3\) đến bệnh viện ở ô \((1,6)\) và bệnh nhân thứ \(4\) đến bệnh viện ở ô \((6,6)\). Như vậy, tất cả bệnh nhân đều có thể đến bệnh viện không muộn hơn thời điểm \(8\), nên in Yes.

Chẳng hạn, xe cứu thương ở bệnh viện \((1,1)\) có thể di chuyển như sau để đưa bệnh nhân thứ \(1\) và thứ \(2\) về bệnh viện không muộn hơn thời điểm \(8\):

Thời điểm	Trạng thái xe cứu thương
\(0\)	Xuất phát từ ô \((1,1)\).
\(1\)	Đến ô \((2,1)\).
\(2\)	Đến ô \((2,2)\), đón bệnh nhân thứ \(2\) rồi xuất phát.
\(3\)	Đến ô \((1,2)\).
\(4\)	Đến ô \((1,1)\), trả bệnh nhân thứ \(2\) rồi xuất phát.
\(5\)	Đến ô \((1,2)\).
\(6\)	Đến ô \((1,3)\), đón bệnh nhân thứ \(1\) rồi xuất phát.
\(7\)	Đến ô \((1,2)\).
\(8\)	Đến ô \((1,1)\) và trả bệnh nhân thứ \(1\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,3,4,6,7\).

Ví dụ 2

Input

Output

No

Giải thích

Không thể đưa tất cả bệnh nhân đến bệnh viện không muộn hơn thời điểm \(19\), nên in No.

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 3

Input

Output

Yes

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,3,4,6,7\).

Ví dụ 4

Input

Output

No

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(4,6,7\).

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ hai. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

2. JOI 2025 - Collecting Stamps 4

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

JOI sống ở đất nước IOI, nổi tiếng với một hồ nước lớn. Hôm nay, một cuộc thi sưu tập dấu sẽ được tổ chức quanh hồ.

Quanh hồ có \(2N\) địa điểm cách đều nhau, được đánh số từ \(1\) đến \(2N\) theo chiều kim đồng hồ. Có \(2N\) con đường một chiều nối các địa điểm kề nhau: đường \(i\) (\(1 \le i \le 2N-1\)) đi từ địa điểm \(i\) đến địa điểm \(i+1\), còn đường \(2N\) đi từ địa điểm \(2N\) đến địa điểm \(1\). Chính giữa mỗi con đường có một trạm đóng dấu.

Có \(N\) màu dấu, được đánh số từ \(1\) đến \(N\). Trạm trên đường \(i\) có thể đóng dấu màu \(A_i\). Với mỗi màu \(j\) (\(1 \le j \le N\)), có đúng hai trạm có thể đóng dấu màu đó.

JOI mang nhiều thẻ để tham gia cuộc thi. Mỗi thẻ có hai ô để đóng dấu, một ô bên trái và một ô bên phải. Mỗi ô chứa được nhiều nhất một dấu. Ban đầu, tất cả các thẻ đều chưa có dấu.

JOI thực hiện các bước sau theo thứ tự:

Chọn một trong \(2N\) địa điểm làm điểm xuất phát rồi đến đó. Nếu chọn địa điểm \(i\), JOI phải trả phí tham gia là \(C_i\).
Trước khi bắt đầu đi quanh hồ, JOI có thể yêu cầu ban tổ chức hoán đổi hai trạm trên hai con đường kề nhau. Cụ thể, có thể đổi trạm trên đường \(2N\) với trạm trên đường \(1\), hoặc chọn \(i\) (\(2 \le i \le 2N\)) rồi đổi trạm trên đường \(i-1\) với trạm trên đường \(i\). Mỗi yêu cầu tốn chi phí \(X\) và được thực hiện ngay lập tức. JOI được đưa ra tùy ý nhiều yêu cầu, kể cả không đưa ra yêu cầu nào. Tuy nhiên, để ngăn gian lận, không được hoán đổi hai trạm nằm ở hai phía của điểm xuất phát: nếu xuất phát tại địa điểm \(1\), không được đổi trạm trên đường \(2N\) và đường \(1\); nếu xuất phát tại địa điểm \(i\) (\(2 \le i \le 2N\)), không được đổi trạm trên đường \(i-1\) và đường \(i\).
Sau đó, JOI xuất phát, di chuyển theo chiều kim đồng hồ, lần lượt ghé thăm cả \(2N\) trạm và kết thúc khi quay về điểm xuất phát. Tại mỗi trạm, JOI có thể đóng dấu tùy ý nhiều lần lên tùy ý nhiều thẻ. Có thể đóng dấu vào cả hai ô của một thẻ tại cùng một trạm. Tuy nhiên, trên mỗi thẻ, luôn phải đóng dấu vào ô trái trước rồi mới đến ô phải; không được đóng dấu vào ô phải khi ô trái còn trống.

JOI muốn thu thập nhiều loại thẻ đã có dấu ở cả hai ô. Ký hiệu \((a,b)\) là loại thẻ có dấu màu \(a\) ở ô trái và màu \(b\) ở ô phải. Hai thẻ \((a_1,b_1)\) và \((a_2,b_2)\) cùng loại khi và chỉ khi \(a_1=a_2\) và \(b_1=b_2\). Vì có \(N\) màu dấu nên có tất cả \(N^2\) loại thẻ đã được đóng dấu ở cả hai ô.

Để giúp JOI lập chiến lược, bạn cần trả lời \(Q\) câu hỏi độc lập. Với câu hỏi thứ \(q\) (\(1 \le q \le Q\)), hãy tìm tổng chi phí nhỏ nhất, gồm phí tham gia và chi phí hoán đổi, để khi kết thúc cuộc thi JOI có ít nhất \(K_q\) loại thẻ đã được đóng dấu ở cả hai ô. Với các ràng buộc của bài, luôn có thể đạt được yêu cầu nếu trả đủ nhiều chi phí.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N,X\).
Dòng thứ hai chứa \(2N\) số nguyên \(A_1,A_2,\ldots,A_{2N}\).
Dòng thứ ba chứa \(2N\) số nguyên \(C_1,C_2,\ldots,C_{2N}\).
Dòng thứ tư chứa số nguyên \(Q\).
Trong \(Q\) dòng tiếp theo, dòng thứ \(q\) chứa số nguyên \(K_q\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(q\) chứa tổng chi phí nhỏ nhất để JOI thu thập được ít nhất \(K_q\) loại thẻ đã được đóng dấu ở cả hai ô khi kết thúc cuộc thi.

Ràng buộc

\(2 \le N \le 500000\).
\(1 \le X \le 500000\).
\((A_1,A_2,\ldots,A_{2N})\) là một hoán vị của \((1,1,2,2,\ldots,N,N)\).
\(1 \le C_i \le 10^{18}\) với mọi \(1 \le i \le 2N\).
\(1 \le Q \le 500000\).
\(1 \le K_q \le N^2\) với mọi \(1 \le q \le Q\).
Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

\(5\) điểm: \(N \le 4\).
\(20\) điểm: \(N \le 5000\), \(Q=1\), \(K_1=N^2\).
\(20\) điểm: \(N \le 5000\), \(Q=1\).
\(19\) điểm: \(N \le 5000\).
\(21\) điểm: \(Q=1\).
\(15\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

3 2
1 2 2 3 1 3
6 1 4 5 4 7
2
8
9

Output

3
4

Giải thích

Giả sử JOI chọn địa điểm \(2\) làm điểm xuất phát và yêu cầu hoán đổi trạm trên đường \(3\) với trạm trên đường \(4\). Khi đó:

Tổng chi phí là \(C_2+X\times1=3\).
JOI ghé các trạm theo thứ tự các đường \(2,3,4,5,6,1\). Các màu dấu tương ứng là \(2,3,2,1,3,1\).
Có thể thu thập \(8\) loại thẻ đã được đóng dấu ở cả hai ô. Chẳng hạn, để thu thập thẻ \((3,1)\), đóng dấu vào ô trái tại đường \(3\), rồi vào ô phải tại đường \(1\). Chỉ có loại thẻ \((1,2)\) là không thể thu thập được.

Không thể thu thập ít nhất \(8\) loại thẻ với chi phí không quá \(2\), nên dòng thứ nhất in \(3\).

Nếu JOI chọn địa điểm \(3\) làm điểm xuất phát và không yêu cầu hoán đổi trạm nào, có thể thu thập cả \(9\) loại thẻ. Tổng chi phí là \(C_3+X\times0=4\). Không thể thu thập ít nhất \(9\) loại thẻ với chi phí không quá \(3\), nên dòng thứ hai in \(4\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,4,6\).

Ví dụ 2

Input

8 1
1 2 6 1 6 3 8 4 5 5 3 4 7 2 7 8
4 5 3 6 2 9 1 4 6 3 8 5 2 9 4 7
1
64

Output

Giải thích

Chọn địa điểm \(10\) làm điểm xuất phát và lần lượt yêu cầu các hoán đổi sau:

Hoán đổi trạm trên đường \(15\) và đường \(16\).
Hoán đổi trạm trên đường \(2\) và đường \(3\).
Hoán đổi trạm trên đường \(16\) và đường \(1\).
Hoán đổi trạm trên đường \(1\) và đường \(2\).

Khi đó, có thể thu thập \(64\) loại thẻ với tổng chi phí \(C_{10}+X\times4=7\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(2,3,4,5,6\).

Ví dụ 3

Input

9 4
4 3 5 3 8 1 5 8 1 7 6 2 4 9 6 9 2 7
12 9 4 8 7 1 20 5 8 7 4 13 5 9 10 3 7 8
6
39
81
73
79
64
52

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(4,6\).

Giới hạn

Giới hạn thời gian là \(3\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

3. JOI 2025 - Space Thief

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bạn là một siêu trộm đang hoạt động trong thiên hà JOI.

Thiên hà có \(N\) ngôi sao, được đánh số từ \(0\) đến \(N-1\), và \(M\) thiết bị dịch chuyển, được đánh số từ \(0\) đến \(M-1\). Thiết bị \(i\) (\(0 \le i \le M-1\)) nối hai chiều giữa ngôi sao \(U_i\) và ngôi sao \(V_i\). Có thể đi từ bất kỳ ngôi sao nào đến bất kỳ ngôi sao nào khác bằng cách sử dụng các thiết bị dịch chuyển.

Một chiếc chìa khóa được giấu ở một ngôi sao, còn một chiếc rương báu được giấu ở một ngôi sao khác. Nhiệm vụ của bạn là xác định số hiệu ngôi sao \(A\) chứa chìa khóa và ngôi sao \(B\) chứa rương báu. Để thực hiện nhiệm vụ, bạn được đặt không quá \(300\) câu hỏi, mỗi câu hỏi gồm:

Với mỗi thiết bị \(i\), chọn biến nó thành thiết bị một chiều từ \(U_i\) đến \(V_i\) hoặc từ \(V_i\) đến \(U_i\).
Với các hướng vừa chọn, hỏi liệu có thể đi từ ngôi sao chứa chìa khóa đến ngôi sao chứa rương báu bằng các thiết bị dịch chuyển hay không.

Bạn muốn xác định \(A\) và \(B\) bằng các câu hỏi đó. Để được đánh giá cao, bạn cần dùng càng ít câu hỏi càng tốt. Cho thông tin về thiên hà, hãy cài đặt chiến lược xác định hai ngôi sao này.

Giao diện hàm

Bạn phải nộp tệp thief.cpp, nạp thief.h bằng chỉ thị #include và cài đặt hàm sau:

C++

void solve(int N, int M, std::vector<int> U, std::vector<int> V)

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu:

N là số ngôi sao.
M là số thiết bị dịch chuyển.
U và V là hai mảng có độ dài \(M\). Với mỗi \(0 \le i \le M-1\), U[i] và V[i] lần lượt là \(U_i\) và \(V_i\), hai đầu của thiết bị \(i\).

Trong thief.cpp, bạn được gọi các hàm sau:

C++

int query(std::vector<int> x)

Hàm này đặt một câu hỏi. Tham số x phải là mảng có độ dài \(M\). Với mỗi \(0 \le i \le M-1\):

Nếu x[i] bằng \(0\), thiết bị \(i\) chỉ cho phép đi từ \(U_i\) đến \(V_i\).
Nếu x[i] bằng \(1\), thiết bị \(i\) chỉ cho phép đi từ \(V_i\) đến \(U_i\).

Hàm trả về \(1\) nếu có thể đi từ ngôi sao \(A\) đến ngôi sao \(B\) bằng các thiết bị đã được định hướng như trên; nếu không, hàm trả về \(0\).

Nếu độ dài của x không bằng \(M\), chương trình bị chấm Wrong Answer [1].
Nếu một phần tử của x khác \(0\) và \(1\), chương trình bị chấm Wrong Answer [2].
Không được gọi query quá \(300\) lần. Nếu vượt giới hạn này, chương trình bị chấm Wrong Answer [3].

C++

void answer(int A, int B)

Hàm này báo đáp án: ngôi sao A chứa chìa khóa và ngôi sao B chứa rương báu.

A phải là số nguyên trong đoạn từ \(0\) đến \(N-1\). Nếu không, chương trình bị chấm Wrong Answer [4].
B phải là số nguyên trong đoạn từ \(0\) đến \(N-1\). Nếu không, chương trình bị chấm Wrong Answer [5].
Nếu báo sai số hiệu ngôi sao, chương trình bị chấm Wrong Answer [6].
Phải gọi answer đúng một lần. Nếu gọi từ hai lần trở lên, chương trình bị chấm Wrong Answer [7]. Nếu solve kết thúc mà chưa gọi answer, chương trình bị chấm Wrong Answer [8].

Bạn được cài đặt các hàm phụ và khai báo biến toàn cục để sử dụng nội bộ. Chương trình nộp bài không được đọc hay ghi đầu vào chuẩn, đầu ra chuẩn, hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Bộ chấm mẫu

Gói bộ chấm mẫu chứa grader.cpp và mã nguồn mẫu của tệp cần nộp. Đặt grader.cpp, thief.cpp, thief.h trong cùng một thư mục. Lệnh biên dịch bộ chấm mẫu là:

Bash

g++ -std=gnu++20 -O2 -o grader grader.cpp thief.cpp

Cũng có thể chạy ./compile.sh trong gói. Khi biên dịch thành công, tệp thực thi grader được tạo ra.

Bộ chấm thật khác với bộ chấm mẫu. Bộ chấm mẫu 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. Những thao tác nhập xuất này do bộ chấm mẫu thực hiện, không phải chương trình bạn nộp.

Dữ liệu vào của bộ chấm mẫu có dạng:

N M A B
U_0 V_0
U_1 V_1
...
U_{M-1} V_{M-1}

Các giá trị \(A,B\) chỉ được cung cấp cho bộ chấm mẫu; hàm solve chỉ nhận \(N,M,U,V\).

Bộ chấm mẫu xuất thông tin sau, không kèm dấu ngoặc kép:

Nếu trả lời đúng, bộ chấm in số lần gọi query, chẳng hạn Accepted: 25.
Nếu trả lời sai, bộ chấm in loại lỗi, chẳng hạn Wrong Answer [4].

Nếu chương trình đồng thời vi phạm nhiều điều kiện, bộ chấm mẫu chỉ báo một loại lỗi. Bộ chấm mẫu có thể kết thúc chương trình ngay khi phát hiện lỗi.

Cách phản hồi của bộ chấm

Ở một số bộ dữ liệu, bộ chấm thật có tính thích nghi (adaptive). Nghĩa là bộ chấm không cố định đáp án ngay từ đầu, mà đưa ra phản hồi dựa trên các lần gọi query trước đó. Tuy nhiên, luôn bảo đảm tồn tại ít nhất một đáp án không mâu thuẫn với tất cả các phản hồi của bộ chấm.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của những hàm được mô tả ở trên, không đọc đầu vào chuẩn.

Dữ liệu ra

Bài nộp không ghi đầu ra chuẩn. Kết quả được trả qua giá trị trả về của các hàm được mô tả ở trên.

Ràng buộc

\(2 \le N \le 10000\).
\(1 \le M \le 15000\).
\(0 \le A \le N-1\) và \(0 \le B \le N-1\).
\(A \ne B\).
\(0 \le U_i < V_i \le N-1\) với mọi \(0 \le i \le M-1\).
\((U_i,V_i) \ne (U_j,V_j)\) với mọi \(0 \le i < j \le M-1\).
Có thể đi từ bất kỳ ngôi sao nào đến bất kỳ ngôi sao nào khác bằng các thiết bị dịch chuyển hai chiều ban đầu.

Chấm điểm

\(7\) điểm: \(M=N-1\), \(U_i=i\), \(V_i=i+1\) với mọi \(0 \le i \le M-1\).
\(13\) điểm: \(M=N-1\), \(U_i=0\), \(V_i=i+1\) với mọi \(0 \le i \le M-1\).
\(2\) điểm: \(M=N-1\), \(N \le 8\).
\(8\) điểm: \(M=N-1\), \(N \le 50\).
\(5\) điểm: \(M=N-1\), \(N \le 150\).
\(5\) điểm: \(M=N-1\), \(N \le 250\).
\(40\) điểm: \(M=N-1\).
\(20\) điểm: Không có ràng buộc bổ sung.

Với nhóm \(7\), nếu có bất kỳ bộ dữ liệu nào trong nhóm bị trả lời sai, vượt giới hạn thời gian, vượt giới hạn bộ nhớ hoặc gặp lỗi thực thi, điểm của nhóm bằng \(0\). Nếu không, gọi \(T\) là số lần gọi query lớn nhất trên tất cả các bộ dữ liệu của riêng nhóm \(7\). Điểm của nhóm được xác định như sau:

Điều kiện	Điểm nhóm \(7\)
\(120 < T\)	\(20\)
\(70 < T \le 120\)	\(30\)
\(T \le 70\)	\(40\)

Với nhóm \(8\), nếu có bất kỳ bộ dữ liệu nào trong nhóm bị trả lời sai, vượt giới hạn thời gian, vượt giới hạn bộ nhớ hoặc gặp lỗi thực thi, điểm của nhóm bằng \(0\). Nếu không, gọi \(T\) là số lần gọi query lớn nhất trên tất cả các bộ dữ liệu của riêng nhóm \(8\). Điểm của nhóm được xác định như sau:

Điều kiện	Điểm nhóm \(8\)
\(120 < T\)	\(10\)
\(70 < T \le 120\)	\(15\)
\(T \le 70\)	\(20\)

Điểm của các nhóm \(1,2,3,4,5,6\) không phụ thuộc vào số lần gọi query, miễn là không vượt quá \(300\) lần. Tuy nhiên, nếu gọi nhiều hơn \(70\) lần, hệ thống của kỳ thi gốc có thể hiển thị thông báo Output is partially correct dù điều này không làm giảm điểm của các nhóm đó.

Ví dụ giao tiếp

Ví dụ dưới đây gồm dữ liệu vào của bộ chấm mẫu và chuỗi lời gọi hàm tương ứng. Phần Output biểu diễn lời gọi và giá trị trả về, không phải dữ liệu mà chương trình nộp bài ghi ra đầu ra chuẩn.

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

Dữ liệu ra của trình chấm mẫu:

solve(5, 4, [0, 0, 1, 1], [1, 3, 2, 4])
  query([0, 1, 0, 0]) -> 1
  query([1, 1, 1, 0]) -> 0
  query([0, 0, 1, 0]) -> 1
  query([0, 0, 1, 1]) -> 0
  answer(0, 4)

Giải thích

Lần gọi query thứ nhất định hướng các thiết bị như sau:

Thiết bị	Hướng di chuyển
\(0\)	Từ ngôi sao \(0\) đến ngôi sao \(1\).
\(1\)	Từ ngôi sao \(3\) đến ngôi sao \(0\).
\(2\)	Từ ngôi sao \(1\) đến ngôi sao \(2\).
\(3\)	Từ ngôi sao \(1\) đến ngôi sao \(4\).

Có thể đi từ ngôi sao \(0\) đến ngôi sao \(4\) bằng cách lần lượt dùng thiết bị \(0\) và \(3\), nên giá trị trả về là \(1\).

Lần gọi query thứ hai định hướng các thiết bị như sau:

Thiết bị	Hướng di chuyển
\(0\)	Từ ngôi sao \(1\) đến ngôi sao \(0\).
\(1\)	Từ ngôi sao \(3\) đến ngôi sao \(0\).
\(2\)	Từ ngôi sao \(2\) đến ngôi sao \(1\).
\(3\)	Từ ngôi sao \(1\) đến ngôi sao \(4\).

Không thể đi từ ngôi sao \(0\) đến ngôi sao \(4\), nên giá trị trả về là \(0\).

Lần gọi query thứ ba định hướng các thiết bị như sau:

Thiết bị	Hướng di chuyển
\(0\)	Từ ngôi sao \(0\) đến ngôi sao \(1\).
\(1\)	Từ ngôi sao \(0\) đến ngôi sao \(3\).
\(2\)	Từ ngôi sao \(2\) đến ngôi sao \(1\).
\(3\)	Từ ngôi sao \(1\) đến ngôi sao \(4\).

Có thể đi từ ngôi sao \(0\) đến ngôi sao \(4\), nên giá trị trả về là \(1\).

Với các hướng ở lần gọi query thứ tư, không thể đi từ ngôi sao \(0\) đến ngôi sao \(4\), nên giá trị trả về là \(0\).

Lời gọi answer(0, 4) báo rằng chìa khóa ở ngôi sao \(0\) và rương báu ở ngôi sao \(4\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(3,4,5,6,7,8\). Tệp sample-01-in.txt được nhắc đến trong đề gốc tương ứng với dữ liệu vào này. Mã nguồn mẫu đi kèm bộ chấm mẫu thực hiện đúng chuỗi lời gọi ở trên.

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.