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

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2024 - Fish 3	100 (p)	2.0s	1G
2	JOI 2024 - Ski 2	100 (p)	2.0s	1G
3	JOI 2024 - Spy 3	100 (p)	1.0s	1G

1. JOI 2024 - Fish 3

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

JOI-kun đang nuôi \(N\) con cá trong một bể lớn. Các con cá được đánh số từ \(1\) đến \(N\).

JOI-kun có hai loại thức ăn \(A\) và \(B\), với số lượng đủ nhiều. Khi thả một viên thức ăn vào bể, đúng một con cá ăn viên đó (bất kỳ con cá nào cũng có thể ăn được). Tùy vào loại thức ăn và con cá đã ăn, độ thông minh của các con cá thay đổi như sau:

Khi cá \(k\) (\(1 \le k \le N\)) ăn một viên thức ăn loại \(A\), độ thông minh của riêng cá \(k\) tăng đúng \(D\).
Khi cá \(k\) (\(1 \le k \le N\)) ăn một viên thức ăn loại \(B\), độ thông minh của tất cả các con cá có số thứ tự từ \(k\) trở lên đều tăng đúng \(1\).

Hiện tại, độ thông minh của mọi con cá đều bằng \(0\). JOI-kun muốn độ thông minh của cá \(i\) (\(1 \le i \le N\)) bằng giá trị lý tưởng \(C_i\), nhưng điều này không phải lúc nào cũng thực hiện được.

Vì vậy, cậu đặt ra \(Q\) câu hỏi. Câu hỏi thứ \(j\) (\(1 \le j \le Q\)) như sau:

Bắt đầu từ trạng thái mà độ thông minh của mọi con cá đều bằng \(0\), có khả năng nào để sau khi thực hiện thao tác thả một viên thức ăn vào bể không hoặc nhiều lần, độ thông minh của tất cả các con cá \(L_j,L_j+1,\ldots,R_j\) đồng thời bằng đúng giá trị lý tưởng tương ứng hay không? Nếu có, số viên thức ăn loại \(A\) ít nhất có thể đã thả vào bể là bao nhiêu?

Hãy viết chương trình trả lời các câu hỏi khi biết thông tin về đàn cá và các câu hỏi của JOI-kun.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N D
C_1 C_2 ... C_N
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dữ liệu ra

In \(Q\) dòng ra đầu ra chuẩn. Trên dòng thứ \(j\) (\(1 \le j \le Q\)), nếu có thể làm cho tất cả các con cá \(L_j,L_j+1,\ldots,R_j\) đạt đúng độ thông minh lý tưởng tương ứng, in số viên thức ăn loại \(A\) ít nhất cần thả vào bể. Nếu không thể, in -1.

Ràng buộc

\(1 \le N \le 300\,000\).
\(1 \le Q \le 300\,000\).
\(1 \le D \le 10^{12}\).
\(0 \le C_i \le 10^{12}\) (\(1 \le i \le N\)).
\(1 \le L_j \le R_j \le N\) (\(1 \le j \le Q\)).
Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

9 điểm: \(N \le 3\,000\), \(Q \le 3\,000\).
7 điểm: \(C_i \le 1\) với mọi \(1 \le i \le N\).
28 điểm: \(D=1\).
20 điểm: \(C_i \ge C_{i+1}\) với mọi \(1 \le i \le N-1\).
36 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Ví dụ, trong trường hợp sau, cuối cùng các con cá \(1,2,3\) đều đạt đúng độ thông minh lý tưởng, và chỉ có \(1\) viên thức ăn loại \(A\) được thả vào bể:

Ban đầu, độ thông minh của các con cá \(1,2,3,4\) lần lượt là \(0,0,0,0\).
JOI-kun thả một viên thức ăn loại \(B\), và cá \(3\) ăn nó. Độ thông minh trở thành \(0,0,1,1\).
JOI-kun thả một viên thức ăn loại \(A\), và cá \(1\) ăn nó. Độ thông minh trở thành \(2,0,1,1\).
Cuối cùng, JOI-kun thả một viên thức ăn loại \(B\), và cá \(1\) ăn nó. Độ thông minh trở thành \(3,1,2,2\).

Không thể làm cho cả ba con cá \(1,2,3\) đạt đúng độ thông minh lý tưởng mà không thả viên thức ăn loại \(A\) nào, nên kết quả là 1.

Ví dụ này thỏa mãn các ràng buộc của bài toán con \(1,5\).

Ví dụ 2

Input

Output

0
-1
0

Giải thích

Ví dụ này thỏa mãn các ràng buộc của bài toán con \(1,2,5\).

Ví dụ 3

Input

Output

5
3
3

Giải thích

Ví dụ này thỏa mãn các ràng buộc của bài toán con \(1,3,5\).

Ví dụ 4

Input

6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6

Output

Giải thích

Ví dụ này thỏa mãn các ràng buộc của bài toán con \(1,4,5\).

Nguồn

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

2. JOI 2024 - Ski 2

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

Ông JOI quản lý một khu trượt tuyết nổi tiếng trên cao nguyên IOI. Để kỷ niệm \(15\) năm ngày khai trương, ông quyết định xây dựng một khu trượt tuyết mới trên cao nguyên KOI nằm liền kề.

Cao nguyên KOI có \(N\) địa điểm, được đánh số từ \(1\) đến \(N\). Hiện tại, địa điểm \(i\) (\(1 \le i \le N\)) có độ cao \(H_i\) mét, và chưa có đường trượt nào nối các địa điểm. Ngoài ra, tại mỗi địa điểm đã có sẵn một thiết bị kết nối chưa được sử dụng.

Mục tiêu của ông JOI là xây khách sạn KOI tại một trong \(N\) địa điểm, sau đó xây các đường trượt sao cho có thể trượt xuống khách sạn từ bất kỳ địa điểm nào. Cụ thể, ông thực hiện các bước theo thứ tự sau:

Thực hiện việc đắp đất dưới đây không hoặc nhiều lần: chọn một địa điểm \(i\) và tăng độ cao của nó thêm \(1\) mét. Chi phí mỗi lần là \(K\).
Chọn một trong \(N\) địa điểm để xây khách sạn KOI.
Thực hiện việc mở rộng dưới đây không hoặc nhiều lần: chọn một địa điểm \(i\) và xây thêm một thiết bị kết nối tại đó. Chi phí mỗi lần là \(C_i\).
Với mỗi địa điểm trong \(N-1\) địa điểm không có khách sạn, thực hiện việc xây dựng sau: gọi số thứ tự của địa điểm này là \(i\). Chọn một địa điểm khác \(j\) có độ cao thấp hơn hẳn địa điểm \(i\), rồi dùng một thiết bị kết nối chưa sử dụng tại địa điểm \(j\) để xây một đường trượt một chiều từ \(i\) đến \(j\). Nếu không tồn tại địa điểm thấp hơn hẳn \(i\) và còn thiết bị kết nối chưa sử dụng, mục tiêu không thể đạt được.

Chi phí xây dựng khu trượt tuyết là tổng chi phí đắp đất và mở rộng đã thực hiện.

Hãy viết chương trình tìm chi phí xây dựng nhỏ nhất khi biết thông tin của mỗi địa điểm và chi phí \(K\) cho một lần đắp đất.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N K
H_1 C_1
H_2 C_2
...
H_N C_N

Dữ liệu ra

In một dòng ra đầu ra chuẩn chứa chi phí nhỏ nhất để xây dựng khu trượt tuyết.

Ràng buộc

\(1 \le N \le 300\).
\(1 \le K \le 10^9\).
\(0 \le H_i \le 10^9\) (\(1 \le i \le N\)).
\(1 \le C_i \le 10^9\) (\(1 \le i \le N\)).
Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

5 điểm: \(K \ge 100\,000\), \(H_i \le 300\) và \(C_i \le 100\) với mọi \(1 \le i \le N\).
12 điểm: \(H_1 \le H_i\), \(C_1 \le C_i\) và \(H_i \le 300\) với mọi \(1 \le i \le N\).
9 điểm: \(N \le 10\) và \(H_i \le 10\) với mọi \(1 \le i \le N\).
33 điểm: \(N \le 40\) và \(H_i \le 40\) với mọi \(1 \le i \le N\).
27 điểm: \(H_i \le 300\) với mọi \(1 \le i \le N\).
14 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Ví dụ, có thể xây khu trượt tuyết như sau:

Đắp đất hai lần tại địa điểm \(1\) và một lần tại địa điểm \(5\), tốn tổng cộng \(2\times(2+1)=6\). Độ cao các địa điểm theo thứ tự từ \(1\) trở đi trở thành \(2,1,0,2,2\) mét.
Xây khách sạn KOI tại địa điểm \(3\).
Mở rộng hai lần tại địa điểm \(2\), tốn tổng cộng \(1\times2=2\). Số thiết bị kết nối tại các địa điểm theo thứ tự từ \(1\) trở đi trở thành \(1,3,1,1,1\).
Xây bốn đường trượt: từ \(1\) đến \(2\), từ \(2\) đến \(3\), từ \(4\) đến \(2\), và từ \(5\) đến \(2\).

Tổng chi phí là \(6+2=8\). Không thể xây khu trượt tuyết với chi phí không quá \(7\), nên kết quả là 8.

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

Ví dụ 2

Input

Output

Giải thích

Ví dụ này chỉ khác ví dụ \(1\) ở giá trị \(K\).

Ví dụ này thỏa mãn các ràng buộc của bài toán con \(1,3,4,5,6\).

Ví dụ 3

Input

Output

Giải thích

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

Nguồn

3. JOI 2024 - Spy 3

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

Aoi và Bitaro là các điệp viên thuộc Cục Thông tin Quốc gia của nước JOI. Nhiệm vụ lần này của họ là bí mật điều tra nước IOI. Bitaro xâm nhập vào nước IOI, còn Aoi ở nước JOI để đưa ra chỉ dẫn.

Trước khi xâm nhập, Aoi và Bitaro đã có được bản đồ nước IOI. Nước IOI có \(N\) thành phố, được đánh số từ \(0\) đến \(N-1\), và \(M\) con đường, được đánh số từ \(0\) đến \(M-1\). Đường \(i\) (\(0 \le i \le M-1\)) nối hai chiều giữa thành phố \(A_i\) và thành phố \(B_i\), có độ dài \(C_i\). Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua một số con đường. Bitaro di chuyển giữa các thành phố bằng những con đường này.

Ngoài ra, có \(Q\) kế hoạch điều tra. Kế hoạch thứ \(j\) (\(0 \le j \le Q-1\)) yêu cầu điều tra thành phố \(T_j\).

Cả Aoi và Bitaro đều được cung cấp toàn bộ thông tin trên trước khi Bitaro xâm nhập vào nước IOI.

Sau khi thoát khỏi nhiều kẻ truy đuổi và đánh bại các sát thủ, Bitaro cuối cùng đã vào được thành phố \(0\). Tuy nhiên, do nhiệm vụ xâm nhập quá khó khăn, cậu đã làm mất một phần thông tin về nước IOI. Cụ thể, cậu mất thông tin về độ dài của \(K\) con đường \(X_0,X_1,\ldots,X_{K-1}\), tức là không còn biết các giá trị \(C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}\). Chỉ Bitaro mất những thông tin này; Aoi vẫn giữ chúng.

Bitaro lập tức báo cho Aoi biết mình đã mất thông tin độ dài của những con đường nào.

Để hoàn thành nhiệm vụ, Bitaro muốn biết một đường đi ngắn nhất từ thành phố \(0\) đến từng thành phố trong \(Q\) kế hoạch điều tra.

Aoi sẽ gửi cho Bitaro một xâu chỉ gồm các ký tự '0' và '1' để giúp cậu. Do có nguy cơ bị chặn bắt thông tin, Aoi muốn lượng thông tin gửi đi càng ít càng tốt.

Hãy viết chương trình thực hiện chiến lược của Aoi để gửi xâu khi biết thông tin về nước IOI, các kế hoạch điều tra và những con đường mà Bitaro mất thông tin. Đồng thời, hãy viết chương trình thực hiện chiến lược của Bitaro để tìm các đường đi ngắn nhất từ những thông tin cậu còn giữ và xâu nhận được từ Aoi.

Nộp bài trên LQDOJ

Trên LQDOJ, bạn nộp một tệp mã nguồn C++, nạp spy3.h, cài đặt cả hai hàm aoi và bitaro với đúng giao diện bên dưới, và không viết hàm main. Đặt các hàm phụ của hai vai trò trong các namespace riêng để tránh trùng tên khi gộp mã nguồn. Bộ chấm chạy hai vai trò trong hai tiến trình riêng biệt; không được dùng biến toàn cục để truyền thông tin giữa chúng.

Phần mô tả hai tệp và lệnh biên dịch bộ chấm mẫu dưới đây là giao diện gốc của cuộc thi, được giữ nguyên để dùng với tệp hỗ trợ chính thức đính kèm. Yêu cầu nộp một tệp ở trên chỉ thay đổi cách đóng gói mã nguồn trên LQDOJ, không thay đổi giao diện hàm, quy tắc giao tiếp hay cách tính điểm.

Chi tiết cài đặt

Bạn phải nộp hai tệp.

Tệp thứ nhất có tên Aoi.cpp, thực hiện chiến lược của Aoi. Tệp này phải nạp Aoi.h bằng chỉ thị #include và cài đặt hàm sau:

C++

std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
                std::vector<int> B, std::vector<long long> C,
                std::vector<int> T, std::vector<int> X)

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

N là số thành phố của nước IOI.
M là số con đường.
Q là số kế hoạch điều tra.
K là số con đường mà Bitaro mất thông tin về độ dài.
A, B, C là các mảng độ dài M. Đường i (\(0 \le i \le M-1\)) nối hai chiều giữa thành phố A[i] và thành phố B[i], có độ dài C[i].
T là mảng độ dài Q. Kế hoạch thứ j (\(0 \le j \le Q-1\)) yêu cầu điều tra thành phố T[j].
X là mảng độ dài K, cho biết Bitaro mất thông tin độ dài của các đường X[0], X[1], ..., X[K-1].
Giá trị trả về là xâu s mà Aoi gửi cho Bitaro.
Mỗi ký tự của s phải là '0' hoặc '1'. Nếu không, chương trình bị chấm Wrong Answer [1].
Độ dài của s phải không quá \(12\,000\). Nếu không, chương trình bị chấm Wrong Answer [2].

Tệp thứ hai có tên Bitaro.cpp, thực hiện chiến lược của Bitaro. Tệp này phải nạp Bitaro.h bằng chỉ thị #include và cài đặt hàm sau:

C++

void bitaro(int N, int M, int Q, int K, std::vector<int> A,
            std::vector<int> B, std::vector<long long> C,
            std::vector<int> T, std::vector<int> X, std::string s)

Hàm này được gọi đúng một lần sau khi hàm aoi được gọi.

N là số thành phố của nước IOI.
M là số con đường.
Q là số kế hoạch điều tra.
K là số con đường mà Bitaro mất thông tin về độ dài.
A, B, C là các mảng độ dài M. Đường i (\(0 \le i \le M-1\)) nối hai chiều giữa thành phố A[i] và thành phố B[i], có độ dài C[i]. Tuy nhiên, các phần tử C[X[0]], C[X[1]], ..., C[X[K-1]] được gán -1 thay cho độ dài thật, vì Bitaro đã mất những thông tin này.
T là mảng độ dài Q. Kế hoạch thứ j (\(0 \le j \le Q-1\)) yêu cầu điều tra thành phố T[j].
X là mảng độ dài K, cho biết Bitaro mất thông tin độ dài của các đường X[0], X[1], ..., X[K-1].
s là xâu chỉ gồm các ký tự '0' và '1' mà Aoi gửi cho Bitaro.

Trong Bitaro.cpp, chương trình có thể gọi hàm sau:

C++

void answer(const std::vector<int> &e)

Ở lần gọi thứ \(j+1\) (\(0 \le j \le Q-1\)), bạn phải đưa ra một đường đi ngắn nhất từ thành phố \(0\) đến thành phố \(T_j\), là mục tiêu của kế hoạch điều tra thứ \(j\).

e là mảng biểu diễn đường đi ngắn nhất đó. Nếu độ dài mảng là \(n\), các phần tử e[0], e[1], ..., e[n-1] là số thứ tự của các con đường trên đường đi, theo đúng thứ tự di chuyển.
Nếu có nhiều đường đi ngắn nhất, bạn có thể trả lời bất kỳ đường nào trong số đó.
Mỗi phần tử của e phải nằm trong đoạn từ \(0\) đến \(M-1\). Nếu không, chương trình bị chấm Wrong Answer [3].
Dãy đường trong e phải tạo thành một đường đi từ thành phố \(0\) đến thành phố \(T_j\). Chính xác hơn, phải tồn tại dãy \(u_0,u_1,\ldots,u_n\) sao cho \(u_0=0\), \(u_n=T_j\), và đường e[k] nối \(u_k\) với \(u_{k+1}\) với mọi \(0 \le k \le n-1\). Nếu không, chương trình bị chấm Wrong Answer [4].
Dãy đường trong e phải là một đường đi ngắn nhất trong tất cả các đường đi từ thành phố \(0\) đến thành phố \(T_j\). Độ dài đường đi là tổng độ dài các con đường được sử dụng. Nếu đường đi không ngắn nhất, chương trình bị chấm Wrong Answer [5].
Phải gọi answer đúng \(Q\) lần. Nếu số lần gọi không bằng \(Q\) khi hàm bitaro kết thúc, chương trình bị chấm Wrong Answer [6].

Lưu ý quan trọng

Bạn có thể cài đặt các hàm nội bộ khác hoặc dùng biến toàn cục. Hai tệp nộp được liên kết cùng chương trình chấm thành một tệp thực thi. Mọi biến toàn cục và hàm nội bộ trong mỗi tệp phải được khai báo trong một namespace không tên để tránh xung đột với các tệp khác. Khi chấm, tệp thực thi chạy thành hai tiến trình riêng, một cho Aoi và một cho Bitaro. Hai tiến trình không thể chia sẻ biến toàn cục.
Chương trình không được sử dụng đầu vào chuẩn hoặc đầu ra chuẩn, cũng không được trao đổi với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, bạn được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Biên dịch và chạy thử

Tệp hỗ trợ chính thức đính kèm chứa chương trình chấm mẫu và các tệp mã nguồn mẫu cần nộp.

Chương trình chấm mẫu là grader.cpp. Để thử chương trình, đặt grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h và Bitaro.h trong cùng thư mục, rồi biên dịch bằng lệnh sau; cũng có thể dùng compile.sh trong tệp hỗ trợ:

Bash

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

Nếu biên dịch thành công, tệp thực thi grader được tạo ra.

Chương trình chấm thật khác 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 từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn cùng đầu ra lỗi chuẩn.

Dữ liệu vào

Chương trình chấm mẫu đọc dữ liệu theo định dạng:

N M
A_0 B_0 C_0
A_1 B_1 C_1
...
A_{M-1} B_{M-1} C_{M-1}
Q
T_0 T_1 ... T_{Q-1}
K
X_0 X_1 ... X_{K-1}

Dữ liệu ra

Chương trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn và đầu ra lỗi chuẩn (không bao gồm dấu ngoặc kép):

Nếu chương trình bị chấm Wrong Answer [1], [2], [3], [4] hoặc [6], chương trình chấm mẫu ghi loại lỗi, chẳng hạn Wrong Answer [1], ra đầu ra lỗi chuẩn. Không có gì được ghi ra đầu ra chuẩn.
Nếu không, độ dài xâu s do aoi trả về được ghi ra đầu ra lỗi chuẩn theo định dạng như Accepted: 2024. Đồng thời, trên dòng thứ \(j+1\) của đầu ra chuẩn (\(0 \le j \le Q-1\)), chương trình chấm mẫu ghi độ dài đường đi trong lần gọi answer thứ \(j+1\). Chương trình chấm mẫu không kiểm tra đường đi có ngắn nhất hay không.

Nếu chương trình vi phạm nhiều điều kiện gây Wrong Answer, chương trình chấm mẫu chỉ báo một loại lỗi trong số đó.

Ràng buộc

\(2 \le N \le 10\,000\).
\(1 \le M \le 20\,000\).
\(1 \le Q \le 16\).
\(1 \le K \le 300\).
\(0 \le A_i < B_i \le N-1\) (\(0 \le i \le M-1\)).
\((A_i,B_i) \ne (A_j,B_j)\) (\(0 \le i < j \le M-1\)).
\(1 \le C_i \le 10^{12}\) (\(0 \le i \le M-1\)).
\(1 \le T_j \le N-1\) (\(0 \le j \le Q-1\)).
\(T_j \ne T_k\) (\(0 \le j < k \le Q-1\)).
\(0 \le X_k \le M-1\) (\(0 \le k \le K-1\)).
\(X_k \ne X_l\) (\(0 \le k < l \le K-1\)).
Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua một số con đường.
Tất cả các giá trị đầu vào đều là số nguyên.

Cách tính điểm

Nếu có bất kỳ bộ dữ liệu nào bị chấm Wrong Answer [1] đến [6], quá giới hạn thời gian, quá giới hạn bộ nhớ hoặc lỗi chạy khác, điểm của bài là \(0\).

Nếu chương trình trả lời đúng mọi bộ dữ liệu, gọi \(L\) là độ dài lớn nhất của xâu s do hàm aoi trả về trên tất cả các bộ dữ liệu của bài. Điểm được tính như sau:

Nếu \(1561 \le L \le 12\,000\), điểm là \(\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor\).
Nếu \(0 \le L \le 1560\), điểm là \(100\).

Ở đâ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à dữ liệu vào mẫu cho chương trình chấm mẫu và các lời gọi hàm tương ứng.

Ví dụ giao tiếp 1

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

Giải thích

Lời gọi đầu tiên:

aoi(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [1, 2, 3], [2, 1], [0, 1])

Giá trị trả về là "101001". Sau đó, hàm sau được gọi:

bitaro(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [-1, -1, 3], [2, 1], [0, 1], "101001")

Trong hàm bitaro, các lời gọi trả lời lần lượt là:

answer([1])
answer([1, 0])

Có hai đường đi ngắn nhất từ thành phố \(0\) đến thành phố \(1\): đi qua đường \(1\) rồi đường \(0\), hoặc chỉ đi qua đường \(2\). Vì vậy, lời gọi answer thứ hai cũng có thể là answer([2]).

Tệp sample-01-in.txt được cung cấp trên trang cuộc thi tương ứng với dữ liệu vào mẫu \(1\). Hai tệp sample-01-in.txt và sample-02-in.txt trong dữ liệu tải về của cuộc thi đều có thể dùng làm đầu vào cho chương trình chấm mẫu.