Google Code Jam 2022 - Qualification Round

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Google Code Jam 2022 - 3D Printing 13 1.0s 1G
2 Google Code Jam 2022 - Chain Reactions 27 1.0s 1G
3 Google Code Jam 2022 - d1000000 20 2.5s 1G
4 Google Code Jam 2022 - Punched Cards 11 1.0s 1G
5 Google Code Jam 2022 - Twisty Little Passages 29 1.0s 1G

1. Google Code Jam 2022 - 3D Printing

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

Bạn là thành viên ban điều hành lễ hội Database Design Day. Bạn phụ trách quảng bá và muốn in ba chữ D để tạo logo cuộc thi. Bạn có thể chọn bất kỳ màu nào, nhưng cả ba chữ phải được in cùng một màu.

Bạn được cấp ba máy in và sẽ dùng mỗi máy để in một chữ D. Mỗi máy in sử dụng mực từ \(4\) hộp riêng biệt có màu khác nhau — cyan, magenta, vàng và đen — để tạo nên bất kỳ màu nào. Với các máy in này, một màu được xác định duy nhất bởi bốn số nguyên không âm \(c,m,y,k\), lần lượt là số đơn vị mực cyan, magenta, vàng và đen cần để tạo màu đó.

Tổng lượng mực cần để in một chữ D chính xác là \(10^6\) đơn vị. Chẳng hạn, in một chữ D màu vàng thuần dùng \(10^6\) đơn vị mực vàng và \(0\) đơn vị của mọi màu khác. In một chữ D màu đỏ Code Jam dùng \(0\) đơn vị cyan, \(500000\) đơn vị magenta, \(450000\) đơn vị vàng và \(50000\) đơn vị đen.

Để in một màu, máy in phải có ít nhất lượng mực được yêu cầu trong từng hộp màu. Cho lượng mực mỗi máy còn có trong mỗi hộp, hãy đưa ra một màu bất kỳ, được biểu diễn bởi bốn số nguyên không âm có tổng bằng \(10^6\), sao cho cả ba máy đều có đủ mực để in màu đó.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ test gồm \(3\) dòng. Dòng thứ \(i\) chứa bốn số nguyên \(C_i,M_i,Y_i,K_i\), lần lượt là số đơn vị mực cyan, magenta, vàng và đen trong các hộp của máy in thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: r, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), và \(r\) là IMPOSSIBLE nếu không có màu nào cả ba máy đều in được. Nếu có, \(r\) phải có dạng c m y k, trong đó \(c,m,y,k\) là các số nguyên không âm có tổng bằng \(10^6\), đồng thời \(c\le C_i\), \(m\le M_i\), \(y\le Y_i\) và \(k\le K_i\) với mọi \(i\).

Nếu có nhiều lời giải, bạn có thể in bất kỳ lời giải nào. Xem mục “What if a test case has multiple correct solutions?” trong phần Competing của FAQ. Thông tin về việc có nhiều lời giải này sẽ không còn được nhắc lại một cách tường minh trong phần còn lại của cuộc thi năm 2022.

Ràng buộc

  • \(0\le C_i\le10^6\) với mọi \(i\).
  • \(0\le M_i\le10^6\) với mọi \(i\).
  • \(0\le Y_i\le10^6\) với mọi \(i\).
  • \(0\le K_i\le10^6\) với mọi \(i\).

Phân nhóm

  • Test Set 1 (phán quyết hiển thị): \(1\le T\le100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 13/13 100%

Ví dụ

Ví dụ 1

Input 
3
300000 200000 300000 500000
300000 200000 500000 300000
300000 500000 300000 200000
1000000 1000000 0 0
0 1000000 1000000 1000000
999999 999999 999999 999999
768763 148041 178147 984173
699508 515362 534729 714381
949704 625054 946212 951187
Output 
Case #1: 300000 200000 300000 200000
Case #2: IMPOSSIBLE
Case #3: 400001 100002 100003 399994
Giải thích

Ví dụ #1 là hình phía trên. Màu được đề xuất dùng hết mực trong các hộp cyan, magenta và vàng của máy in thứ nhất, đồng thời dùng hết mực trong hộp đen của máy in cuối. Không thể dùng thêm một đơn vị nào của cả bốn màu, nên đầu ra mẫu là đầu ra duy nhất có thể cho trường hợp này.

Trong Ví dụ #2, magenta là màu duy nhất mà cả máy in thứ nhất và thứ hai đều có, nên cơ hội duy nhất là dùng \(10^6\) đơn vị magenta. Đáng tiếc, máy in thứ ba thiếu một chút mực, khiến trường hợp này không thể thực hiện.

Trong Ví dụ #3, một số đầu ra đúng khác là 400000 100000 100000 400000, 300000 0 0 700000 và 350000 140000 160000 350000, cùng rất nhiều đáp án khác. Lưu ý rằng 300000 140000 160000 700000 không hợp lệ: dù mọi máy in đều có đủ từng màu, tổng lượng mực bắt buộc phải đúng bằng \(10^6\).

Nguồn

Google Code Jam 2022, Vòng loại, bài 3D Printing.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

2. Google Code Jam 2022 - Chain Reactions

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

Wile sống một mình trong sa mạc, nên tự giải trí bằng cách chế tạo những cỗ máy phức tạp vận hành theo phản ứng dây chuyền. Mỗi máy gồm \(N\) mô-đun được đánh số \(1,2,\ldots,N\). Mỗi mô-đun có thể trỏ đến một mô-đun khác có chỉ số nhỏ hơn; nếu không, nó trỏ vào vực thẳm.

Những mô-đun không bị bất kỳ mô-đun nào khác trỏ đến được gọi là bộ khởi phát. Wile có thể kích hoạt thủ công các bộ khởi phát. Khi một mô-đun được kích hoạt, nó kích hoạt mô-đun mà nó trỏ tới nếu có; mô-đun đó có thể tiếp tục kích hoạt mô-đun thứ ba, và cứ thế cho đến khi chuỗi sắp chạm vực thẳm hoặc một mô-đun đã được kích hoạt. Quá trình này được gọi là một phản ứng dây chuyền.

Mỗi mô-đun \(i\) có hệ số vui \(F_i\). Mức vui Wile nhận được từ một phản ứng dây chuyền là hệ số vui lớn nhất trong số các mô-đun được kích hoạt trong phản ứng đó. Wile sẽ kích hoạt mỗi bộ khởi phát đúng một lần theo một thứ tự nào đó. Tổng mức vui của cả buổi là tổng mức vui từ từng phản ứng dây chuyền.

Ví dụ, giả sử Wile có \(4\) mô-đun với \(F_1=60,F_2=20,F_3=40,F_4=50\); mô-đun \(1\) trỏ vào vực thẳm, các mô-đun \(2\) và \(3\) trỏ đến mô-đun \(1\), còn mô-đun \(4\) trỏ đến mô-đun \(2\). Có hai bộ khởi phát, là \(3\) và \(4\), mà Wile phải kích hoạt theo một thứ tự nào đó.

Như hình trên, nếu Wile kích hoạt thủ công mô-đun \(4\) trước, các mô-đun \(4,2,1\) được kích hoạt trong cùng phản ứng dây chuyền, cho mức vui \(\max(50,20,60)=60\). Sau đó, khi Wile kích hoạt mô-đun \(3\), chỉ riêng mô-đun \(3\) được kích hoạt vì mô-đun \(1\) không thể kích hoạt lại, cho mức vui \(40\). Tổng mức vui là \(60+40=100\).

Tuy nhiên, nếu Wile kích hoạt mô-đun \(3\) trước, các mô-đun \(3\) và \(1\) được kích hoạt trong cùng phản ứng, cho mức vui \(\max(40,60)=60\). Sau đó, khi kích hoạt mô-đun \(4\), các mô-đun \(4\) và \(2\) được kích hoạt trong cùng phản ứng, cho mức vui \(\max(50,20)=50\). Tổng mức vui là \(60+50=110\).

Cho các hệ số vui và cách nối các mô-đun, hãy tính mức vui lớn nhất Wile có thể nhận được nếu kích hoạt các bộ khởi phát theo thứ tự tốt nhất.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Sau đó là \(T\) bộ test, mỗi bộ được mô tả bằng ba dòng. Dòng đầu chứa số nguyên \(N\), số mô-đun của Wile. Dòng thứ hai chứa \(N\) số nguyên \(F_1,F_2,\ldots,F_N\), trong đó \(F_i\) là hệ số vui của mô-đun thứ \(i\).

Dòng thứ ba chứa \(N\) số nguyên \(P_1,P_2,\ldots,P_N\). Nếu \(P_i=0\), mô-đun \(i\) trỏ vào vực thẳm; nếu không, mô-đun \(i\) trỏ đến mô-đun \(P_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), và \(y\) là mức vui lớn nhất Wile có thể nhận được khi kích hoạt thủ công các bộ khởi phát theo thứ tự tốt nhất.

Ràng buộc

  • \(1\le T\le100\).
  • \(1\le F_i\le10^9\).
  • \(0\le P_i\le i-1\) với mọi \(i\).

Phân nhóm

  • Test Set 1 (phán quyết hiển thị): \(1\le N\le10\).
  • Test Set 2 (phán quyết hiển thị): \(1\le N\le1000\).
  • Test Set 3 (phán quyết ẩn): \(1\le N\le100000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 10/27 37,04%
Test Set 2 12/27 44,44%
Test Set 3 5/27 18,52%

Ví dụ

Ví dụ 1

Input 
3
4
60 20 40 50
0 1 1 2
5
3 2 1 4 5
0 1 1 1 0
8
100 100 100 90 80 100 90 100
0 1 2 1 2 3 1 3
Output 
Case #1: 110
Case #2: 14
Case #3: 490
Giải thích

Ví dụ #1 chính là trường hợp được giải thích trong đề bài.

Trong Ví dụ #2, có \(4\) bộ khởi phát, là các mô-đun từ \(2\) đến \(5\), nên có \(4\) phản ứng dây chuyền. Kích hoạt theo thứ tự \(3,5,4,2\) tạo các chuỗi có mức vui lần lượt \(3,5,4,2\), tổng cộng \(14\). Đây là tổng của bốn hệ số vui lớn nhất trong dữ liệu vào nên không thể đạt cao hơn.

Trong Ví dụ #3, một thứ tự kích hoạt tối ưu cho \(5\) bộ khởi phát là \(4,5,7,6,8\).

Nguồn

Google Code Jam 2022, Vòng loại, bài Chain Reactions.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

3. Google Code Jam 2022 - d1000000

Điểm: 20 Thời gian: 2.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Loại xúc xắc phổ biến nhất có \(6\) mặt, mỗi mặt ghi một số nguyên khác nhau từ \(1\) đến \(6\), nhưng nhiều trò chơi dùng các loại khác. Cụ thể, \(dk\) là một xúc xắc có \(k\) mặt, mỗi mặt ghi một số nguyên khác nhau từ \(1\) đến \(k\). Một \(d6\) là xúc xắc thông thường, \(d4\) có bốn mặt, còn \(d1000000\) có một triệu mặt.

Trong bài này, ta bắt đầu với một bộ sưu tập \(N\) xúc xắc. Xúc xắc thứ \(i\) là một \(dS_i\), nghĩa là nó có \(S_i\) mặt mang các số nguyên từ \(1\) đến \(S_i\). Một dãy liên tiếp độ dài \(\ell\) bắt đầu tại \(x\) là danh sách \(x,x+1,\ldots,x+(\ell-1)\). Ta muốn chọn một số xúc xắc, có thể là tất cả, và chọn một số trên mỗi xúc xắc để tạo thành một dãy liên tiếp. Dãy dài nhất có thể tạo theo cách này là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ test được mô tả bằng hai dòng. Dòng đầu chứa số nguyên \(N\), số xúc xắc trong trò chơi. Dòng thứ hai chứa \(N\) số nguyên \(S_1,S_2,\ldots,S_N\), mỗi số là số mặt của một xúc xắc khác nhau.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), và \(y\) là số xúc xắc đầu vào lớn nhất có thể được đưa vào một dãy liên tiếp.

Ràng buộc

  • \(1\le T\le100\).

Phân nhóm

  • Test Set 1 (phán quyết hiển thị): \(1\le N\le10\) và \(4\le S_i\le20\) với mọi \(i\).
  • Test Set 2 (phán quyết hiển thị): \(1\le N\le10^5\) và \(4\le S_i\le10^6\) với mọi \(i\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 9/20 45%
Test Set 2 11/20 55%

Ví dụ

Ví dụ 1

Input 
4
4
6 10 12 8
6
5 4 5 4 4 4
10
10 10 7 6 7 4 4 5 7 4
1
10
Output 
Case #1: 4
Case #2: 5
Case #3: 9
Case #4: 1
Giải thích

Trong Ví dụ #1, có nhiều cách tạo dãy liên tiếp bằng cả \(4\) xúc xắc. Một cách được minh họa trong hình phía trên.

Trong Ví dụ #2, vì không xúc xắc nào có thể cho số nguyên lớn hơn \(5\), không thể tạo dãy dùng hơn \(5\) xúc xắc. Có nhiều cách tạo dãy dùng đúng \(5\) xúc xắc. Chẳng hạn, chọn \(4\) và \(5\) trên hai xúc xắc \(d5\), rồi chọn \(1,2,3\) trên ba trong số các xúc xắc \(d4\) để tạo \(1,2,3,4,5\).

Trong Ví dụ #3, có thể tạo dãy \(1,2,3,4,5,6,7,8,9\) bằng cách bỏ một \(d4\); dùng các \(d4\), \(d5\) và \(d6\) để lấy các số từ \(1\) đến \(4\); dùng các \(d7\) để lấy từ \(5\) đến \(7\); và dùng các \(d10\) để lấy \(8\) và \(9\). Không thể tạo dãy độ dài \(10\), nên đây là kết quả tốt nhất.

Trong Ví dụ #4, chỉ có thể tạo dãy độ dài \(1\), nhưng có thể làm vậy bằng cách chọn bất kỳ số nguyên nào trên xúc xắc \(d10\) đã cho.

Nguồn

Google Code Jam 2022, Vòng loại, bài d1000000.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

4. Google Code Jam 2022 - Punched Cards

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

Một nhóm lập trình viên bí mật đang âm mưu làm đảo lộn thế giới ngôn ngữ lập trình và đưa thẻ đục lỗ trở lại bằng cách giới thiệu một ngôn ngữ mới mang tên Punched Card Python, cho phép mọi người lập trình Python bằng thẻ đục lỗ!

Đúng phong cách của những người thích tạo đột phá, họ sẽ khởi động một chiến dịch lan truyền để quảng bá ngôn ngữ mới ngay cả trước khi có thiết kế cho một nguyên mẫu. Trong chiến dịch, họ muốn vẽ các thẻ đục lỗ với nhiều kích thước khác nhau bằng nghệ thuật ASCII.

Hình ASCII của một thẻ đục lỗ mà họ muốn vẽ giống một ma trận \(R\times C\) nhưng thiếu ô trên cùng bên trái. Vì vậy, nó có tổng cộng \((R\cdot C)-1\) ô. Mỗi ô được vẽ bằng một dấu chấm (.), phía trên và dưới bao bởi dấu gạch ngang (-), bên trái và phải bao bởi dấu gạch đứng (|), còn bốn góc dùng dấu cộng (+). Các ô kề nhau dùng chung những ký tự trên đường biên. Các dấu chấm (.) được dùng để căn chỉnh các ô ở hàng trên cùng.

Ví dụ, dưới đây là một thẻ đục lỗ có \(R=3\) hàng và \(C=4\) cột:

..+-+-+-+
..|.|.|.|
+-+-+-+-+
|.|.|.|.|
+-+-+-+-+
|.|.|.|.|
+-+-+-+-+

Phần ví dụ bên dưới có thêm các kích thước khác. Cho hai số nguyên \(R,C\) mô tả kích thước thẻ đục lỗ, hãy in hình ASCII của nó đúng như mô tả.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Tiếp theo là \(T\) dòng, mỗi dòng mô tả một bộ test bằng hai số nguyên \(R,C\): số hàng và số cột của thẻ đục lỗ cần vẽ.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x:, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)). Sau đó in thêm \((2\cdot R)+1\) dòng chứa hình ASCII của thẻ đục lỗ có \(R\) hàng và \(C\) cột.

Ràng buộc

  • \(1\le T\le81\).
  • \(2\le R\le10\).
  • \(2\le C\le10\).

Phân nhóm

  • Test Set 1 (phán quyết hiển thị): áp dụng toàn bộ các ràng buộc trên.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 11/11 100%

Ví dụ

Ví dụ 1

Input 
3
3 4
2 2
2 3
Output 
Case #1:
..+-+-+-+
..|.|.|.|
+-+-+-+-+
|.|.|.|.|
+-+-+-+-+
|.|.|.|.|
+-+-+-+-+
Case #2:
..+-+
..|.|
+-+-+
|.|.|
+-+-+
Case #3:
..+-+-+
..|.|.|
+-+-+-+
|.|.|.|
+-+-+-+
Giải thích

Ví dụ #1 chính là trường hợp được mô tả trong đề bài. Ví dụ #2 và #3 là các ví dụ bổ sung. Lưu ý rằng đầu ra của mỗi trường hợp chứa chính xác \(R\cdot C+3\) dấu chấm.

Nguồn

Google Code Jam 2022, Vòng loại, bài Punched Cards.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

5. Google Code Jam 2022 - Twisty Little Passages

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

Bạn đang khảo sát một hang động có \(N\) căn phòng. Các lối đi ngầm nối hai chiều một số cặp phòng. Mỗi phòng nối với ít nhất một lối đi. Không lối đi nào nối một phòng với chính nó, và không có hai phòng nào được nối bởi nhiều hơn một lối đi.

Khi ở trong một phòng, bạn xác định được số hiệu phòng và nhìn thấy có bao nhiêu lối đi nối với nó, nhưng không thể phân biệt các lối đi. Bạn muốn ước lượng tổng số lối đi trong hang và được phép thực hiện nhiều nhất \(K\) thao tác. Mỗi thao tác là một trong hai loại:

  • được dịch chuyển tức thời bằng phép thuật đến một phòng do bạn chọn; hoặc
  • đi qua một lối đi ngẫu nhiên nối với phòng hiện tại để đến phòng ở đầu kia.

Khi quyết định đi qua một lối đi, bạn không thể chọn lối nào vì chúng trông giống hệt nhau. Một lối đi được chọn cho bạn với xác suất đều.

Bạn bắt đầu cuộc khảo sát trong một phòng tùy ý. Hãy dùng nhiều nhất \(K\) thao tác để ước lượng số lối đi nối các phòng trong hang.

Nếu \(E\) là ước lượng và \(P\) là số lối đi thực tế, lời giải được coi là đúng cho một bộ test khi và chỉ khi

\[P\cdot\frac{2}{3}\le E\le P\cdot\frac{4}{3}.\]

Để vượt qua một Test Set, lời giải phải đúng ở ít nhất \(90\%\) số bộ test trong Test Set đó.

Dữ liệu vào

Đây là bài tương tác. Hãy bảo đảm bạn đã đọc phần Interactive Problems trong FAQ của Google Code Jam.

Ban đầu, chương trình phải đọc một dòng chứa số nguyên \(T\), là số bộ test. Sau đó phải xử lý lần lượt \(T\) bộ test theo giao thức bên dưới.

Dữ liệu ra

Chương trình gửi các lệnh dịch chuyển, đi bộ và ước lượng tới bộ chấm theo giao thức tương tác bên dưới. Phải flush đầu ra sau mỗi lệnh.

Giao thức tương tác

Với mỗi bộ test, trước tiên chương trình đọc một dòng chứa hai số nguyên \(N,K\): số phòng trong hang và số thao tác phòng tối đa được phép thực hiện. Các phòng được đánh số từ \(1\) đến \(N\). Hang được xác định từ đầu bộ test và không thay đổi trong khi bạn khám phá. Sau đó, chương trình xử lý nhiều nhất \(K+1\) lượt trao đổi.

Lượt trao đổi thứ \(i\) bắt đầu bằng việc đọc một dòng chứa hai số nguyên \(R_i,P_i\), lần lượt là số hiệu phòng hiện tại và số lối đi nối với phòng đó. Sau đó, chương trình phải in đúng một trong các dòng sau:

  • Một chữ hoa W: yêu cầu đi qua một lối đi ngẫu nhiên.
  • Một chữ hoa T và một số nguyên \(S\): yêu cầu dịch chuyển tức thời đến phòng \(S\).
  • Một chữ hoa E và một số nguyên \(E\): kết thúc khảo sát và ước lượng hang có \(E\) lối đi.

Sau một thao tác ước lượng, bộ chấm lập tức bắt đầu bộ test kế tiếp nếu còn, bất kể ước lượng có đúng hay không. Nếu không còn bộ test, bộ chấm chờ chương trình kết thúc và không in thêm gì.

Nếu vào bất kỳ lúc nào bộ chấm nhận từ chương trình một dòng sai định dạng, hoặc nếu lượt trao đổi thứ \(K+1\) của một bộ test không phải thao tác ước lượng, bộ chấm in một số duy nhất -1 rồi không in thêm gì. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận -1, chương trình sẽ hết thời gian và nhận lỗi Time Limit Exceeded. Chương trình có trách nhiệm thoát kịp thời để nhận Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu vượt giới hạn bộ nhớ hoặc gặp lỗi thực thi, chương trình nhận phán quyết tương ứng.

Ràng buộc

  • Mỗi phòng nối với ít nhất một lối đi.

Phân nhóm

  • Test Set 1 (phán quyết hiển thị): \(1\le T\le100\), \(2\le N\le10^5\), và \(K=8000\).
  • Theo quy tắc chấm chính thức, lời giải phải đúng ở ít nhất \(90\%\) số bộ test trong Test Set này để vượt qua Test Set.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử đi kèm để chạy cục bộ hoặc trên nền tảng của Google. Khi kiểm thử cục bộ, cần chạy công cụ song song với chương trình; có thể dùng interactive runner của Google. Hãy đọc hướng dẫn trong phần chú thích của tệp đó và phần Interactive Problems trong FAQ để biết thêm chi tiết.

Hướng dẫn cho công cụ kiểm thử nằm trong các chú thích bên trong công cụ. Bạn được khuyến khích thêm các bộ test của riêng mình. Lưu ý rằng dù công cụ nhằm mô phỏng hệ thống chấm, nó không phải hệ thống chấm thật và có thể hành xử khác. Nếu mã vượt qua công cụ nhưng không vượt qua bộ chấm thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm bạn dùng cùng trình biên dịch với Google.

Tải công cụ kiểm thử

Ví dụ

Ví dụ tương tác

Trao đổi 
Judge  Solution
1
5 3
4 1
       T 5
5 2
       W
4 1
       T 1
1 3
       E 5
Giải thích

Bộ chấm cho biết có \(1\) bộ test. Ở đầu bộ test, bộ chấm cho \(N=5,K=3\).

Ta bắt đầu ở phòng \(4\), phòng này có \(1\) lối đi, rồi dùng T 5 để dịch chuyển đến phòng \(5\). Phòng \(5\) có hai lối đi; ta dùng W để đi qua một lối ngẫu nhiên và quay lại phòng \(4\). Sau đó dùng T 1 để dịch chuyển đến phòng \(1\); phòng này có ba lối đi. Cuối cùng, dùng E 5 để đoán có \(5\) lối đi.

Có thể chứng minh số lối đi thực tế là \(4\) hoặc \(5\). Hai đồ thị có thể xảy ra trong ví dụ này được minh họa dưới đây.

Nguồn

Google Code Jam 2022, Vòng loại, bài Twisty Little Passages.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.