Becca và Terry là hai nhà vi sinh vật học có một cuộc cạnh tranh thân thiện. Khi cần nghỉ ngơi sau công việc nghiên cứu, họ chơi một trò chơi trên ma trận gồm các ô đơn vị, có \(R\) hàng và \(C\) cột. Ban đầu, mỗi ô hoặc trống, hoặc chứa chất phóng xạ.

Ở lượt của một người chơi, nếu ma trận không còn ô trống thì người đó thua. Nếu vẫn còn, họ chọn một ô trống và đặt vào đó một khuẩn lạc. Có hai loại khuẩn lạc: H (ngang) và V (dọc).

• Khi đặt khuẩn lạc H vào một ô trống, nó chiếm ô ấy (khiến ô không còn trống), rồi cố lan sang ô ngay phía tây (nếu có) và ô ngay phía đông (nếu có).
• Khi đặt khuẩn lạc V vào một ô trống, nó chiếm ô ấy, rồi cố lan sang ô ngay phía nam (nếu có) và ô ngay phía bắc (nếu có).

Mỗi khi khuẩn lạc thuộc bất kỳ loại nào cố lan vào một ô:

• Nếu ô chứa chất phóng xạ, khuẩn lạc bị đột biến và người vừa đặt nó thua cuộc.
• Nếu ô trống, khuẩn lạc chiếm ô đó, rồi quy tắc trên lại được kích hoạt, tức là nó tiếp tục cố lan xa hơn.
• Nếu ô đã chứa vi khuẩn thuộc bất kỳ loại nào, khuẩn lạc không lan vào ô đó.

Có thể mọi nước đi hiện có của một người chơi đều khiến họ thua, nên họ chắc chắn thất bại. Các phần giải thích ví dụ bên dưới minh họa cách trò chơi diễn ra.

Becca đi trước, sau đó hai người luân phiên cho đến khi một người thua. Nếu cả hai chơi tối ưu, ai sẽ thắng? Nếu Becca thắng, cô có bao nhiêu nước mở đầu thắng khác nhau? Hai nước mở đầu khác nhau khi và chỉ khi chúng dùng ô khác nhau, loại khuẩn lạc khác nhau, hoặc cả hai.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(R\) và \(C\), lần lượt là số hàng và số cột của ma trận. Tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) ký tự. Ký tự thứ \(j\) trên dòng thứ \(i\) biểu diễn ô ở hàng \(i\), cột \(j\). Mỗi ký tự là . (ô trống) hoặc # (ô chứa chất phóng xạ).

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), còn y là số nguyên: bằng 0 nếu Becca không thắng; nếu Becca thắng, đó là số nước mở đầu thắng khác nhau mà cô có thể thực hiện như mô tả trên.

Ràng buộc

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

Phân nhóm

• Test Set 1 (hiển thị): \(1 \le R \le 4\), \(1 \le C \le 4\).
• Test Set 2 (ẩn): \(1 \le R \le 15\), \(1 \le C \le 15\).

Đ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.

Ví dụ

5
2 2
..
.#
4 4
.#..
..#.
#...
...#
3 4
#.##
....
#.##
1 1
.
1 2
##

Case #1: 0
Case #2: 0
Case #3: 7
Case #4: 2
Case #5: 0

Nguồn

Google Code Jam 2019, Vòng 1C, bài Bacterial Tactics.

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

Power Arrangers

Đề bài

Tiến lên nào, các Power Arranger! Ai cũng yêu mến đội gồm năm siêu anh hùng đang là học sinh trung học này, mỗi người mang một trong các chữ cái A, B, C, D và E. Khi đứng cạnh nhau để đối đầu với quái vật xấu xa, họ sắp xếp đội hình theo một trong 120 thứ tự từ trái sang phải khác nhau có thể có, qua đó tạo ra nhiều siêu năng lực chiến thuật khác nhau. Họ thậm chí còn nổi tiếng hơn cả các Teenage Permutant Ninja Turtles!

Một số nhà phê bình chương trình cho rằng đội chỉ dùng mánh lới thay đổi đội hình để chủ sở hữu chương trình có thể bán 120 bộ riêng biệt, mỗi bộ gồm 5 mô hình nhân vật hành động. Trong mỗi bộ, cả đội được xếp theo một thứ tự từ trái sang phải khác nhau và được dán vào đế nên không thể sắp xếp lại. Là một người hâm mộ Power Arrangers cuồng nhiệt, bạn đã sưu tập được 119 bộ như vậy, nhưng không nhớ mình còn thiếu bộ nào. 119 bộ được xếp thành một hàng ngang trên kệ, tạo thành tổng cộng \(119 \times 5 = 595\) mô hình theo thứ tự từ trái sang phải. Bạn không nhớ các bộ được sắp xếp theo thứ tự nào, nhưng biết rằng trong mỗi test, hoán vị thứ tự của các bộ được chọn ngẫu nhiên đều trong tất cả các hoán vị có thể có và độc lập với các test khác.

Bạn không muốn tốn thời gian xác định bộ còn thiếu, nên dự định chỉ xem chữ cái trên nhiều nhất F mô hình trên kệ. Chẳng hạn, bạn có thể chọn xem chữ trên mô hình thứ tám từ trái sang; đó chính là mô hình thứ ba từ trái sang trong bộ thứ hai tính từ trái. Khi xem một mô hình, bạn chỉ biết được chữ cái của riêng mô hình đó; các chữ rất khó nhìn, còn ngoài ra các thành viên trong đội trông rất giống nhau!

Sau khi kiểm tra nhiều nhất F mô hình, bạn phải xác định được bộ nào còn thiếu để hoàn thiện bộ sưu tập và sẵn sàng đối mặt với mọi mối đe dọa xấu xa có thể xảy ra!

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là một bài toán tương tác. Hãy bảo đảm rằng bạn đã đọc thông tin trong phần Bài toán tương tác của trang câu hỏi thường gặp.

Ban đầu, chương trình phải đọc một dòng chứa hai số nguyên T — số lượng test — và F — số mô hình được phép kiểm tra trong mỗi test. Sau đó, bạn cần xử lý T test.

Trong mỗi test, bộ mô hình bị thiếu được chọn ngẫu nhiên đều trong tất cả các bộ có thể có; thứ tự của các bộ còn lại cũng được chọn ngẫu nhiên đều trong tất cả các thứ tự có thể có. Mọi lựa chọn đều độc lập với tất cả lựa chọn khác và với dữ liệu mà chương trình của bạn gửi ra.

Trong mỗi test, chương trình sẽ thực hiện nhiều nhất F + 1 lượt trao đổi với bộ chấm. Bạn được thực hiện nhiều nhất F lượt trao đổi theo dạng sau:

• Chương trình in một dòng chứa một số nguyên từ 1 đến 595 (kể cả hai đầu), chỉ ra mô hình mà bạn muốn xem theo thứ tự từ trái sang phải trên kệ. Thêm một ví dụ: 589 biểu thị mô hình thứ tư từ trái sang trong bộ thứ hai tính từ bên phải.
• Bộ chấm trả lời bằng một dòng chứa duy nhất một chữ cái in hoa A, B, C, D hoặc E, cho biết chữ trên mô hình đó. Nếu bạn gửi dữ liệu không hợp lệ (ví dụ: một số nằm ngoài phạm vi hoặc một dòng sai định dạng), thay vào đó bộ chấm sẽ trả lời bằng một dòng chỉ chứa chữ cái in hoa N.

Sau đó, khi đã thực hiện số lượt trao đổi nói trên mà bạn muốn (không vượt quá F), bạn phải thực hiện thêm một lượt trao đổi theo dạng sau:

• Chương trình in một dòng chứa duy nhất một xâu gồm năm chữ cái in hoa: hoán vị tương ứng với bộ bị thiếu (ví dụ: CADBE).
• Bộ chấm trả lời bằng một dòng chứa duy nhất một chữ cái in hoa: Y nếu câu trả lời đúng, và N nếu câu trả lời sai (hoặc nếu bạn gửi một dòng sai định dạng). Nếu nhận được Y, bạn phải bắt đầu test tiếp theo; nếu không còn test nào, hãy ngừng gửi dữ liệu.

Sau khi bộ chấm gửi N vào luồng dữ liệu vào của chương trình (do dữ liệu không hợp lệ hoặc câu trả lời sai), bộ chấm sẽ không gửi thêm bất kỳ dữ liệu nào. Nếu chương trình vẫn tiếp tục chờ bộ chấm sau khi nhận N, chương trình sẽ hết thời gian và nhận phán quyết Time Limit Exceeded. Bạn có trách nhiệm kết thúc chương trình đủ sớm để nhận phán quyết Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu vượt giới hạn bộ nhớ hoặc chương trình gặp lỗi khi chạy, bạn sẽ nhận phán quyết tương ứng.

Ràng buộc

\(1 \leq \mathbf{T} \leq 50\).

Bộ bị thiếu và thứ tự của các bộ còn lại được chọn ngẫu nhiên đều và độc lập với nhau.

Phân nhóm

Test 1 (Công khai)

F = 475.

Test 2 (Ẩn)

F = 150.

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để kiểm tra cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm tra cục bộ, bạn cần chạy công cụ song song với chương trình của mình; bạn có thể dùng trình chạy tương tác của chúng tôi cho việc đó. Để biết thêm thông tin, hãy đọc hướng dẫn trong phần chú thích của tệp ấy, đồng thời xem phần Bài toán tương tác trong trang câu hỏi thường gặp.

Hướng dẫn sử dụng công cụ kiểm thử nằm trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn bổ sung các test của riêng mình. Xin lưu ý rằng dù công cụ kiểm thử được thiết kế để mô phỏng hệ thống chấm, nó KHÔNG PHẢI là hệ thống chấm thật và có thể hoạt động khác. Nếu chương trình vượt qua công cụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy xem phần Lập trình trong trang câu hỏi thường gặp để bảo đảm rằng bạn đang dùng cùng trình biên dịch với chúng tôi.

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

Ví dụ

  t, f = readline_int_list()   // Đọc 50 vào t và 475 vào f
  printline 10 to stdout       // Xem mô hình cuối cùng trong bộ thứ hai
                               // tính từ bên trái
  flush stdout
  n = readline_string()        // Đọc B vào n. Ồ, thành viên B! Có thể họ không có
                               // năng lực lãnh đạo như A hay kỹ năng kỹ thuật như C,
                               // nhưng họ giúp cả đội vui vẻ bằng những câu nói đùa
                               // thông minh!
  printline 11 to stdout       // Xem mô hình đầu tiên trong bộ thứ ba
                               // tính từ bên trái
  flush stdout
  n = readline_string()        // Đọc B vào n. Lưu ý rằng B đứng đầu bộ thứ ba,
                               // trong khi họ đứng cuối bộ thứ hai.
  printline 14 to stdout       // Xem mô hình thứ tư trong bộ thứ ba
                               // tính từ bên trái
  flush stdout
  n = readline_string()        // Đọc D vào n. Tuy ít nói và trầm tư, thành viên D
                               // vẫn chiến đấu quyết liệt để bảo vệ bạn bè...
                               // và cả thế giới!
  printline ABCDE to stdout    // Ta dại dột đoán bừa dù vẫn còn có thể xem thêm
                               // nhiều nhất 472 mô hình nữa.
  flush stdout
  verdict = readline_string()  // Đọc N vào verdict (bộ chấm đã xác định rằng
                               //   lời giải của ta không đúng)
  exit                         // Thoát để tránh lỗi TLE không rõ nguyên nhân

Nguồn

Google Code Jam 2019, Vòng 1C, bài Power Arrangers.

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

Sau nhiều đêm mất ngủ, cuối cùng bạn đã dạy xong một cánh tay robot thực hiện các động tác tay cần thiết cho trò chơi Oẳn tù tì. Giờ bạn chỉ còn phải lập trình cho nó tham gia giải đấu robot sắp tới!

Trong giải đấu này, mỗi robot sử dụng một chương trình là một chuỗi nước đi; mỗi nước phải là một trong các ký tự sau: R ("Rock", Búa), P ("Paper", Bao), hoặc S ("Scissors", Kéo). Bao thắng Búa và thua Kéo; Búa thắng Kéo và thua Bao; Kéo thắng Bao và thua Búa.

Khi hai robot đối đầu trong một trận, robot đầu tiên đánh ra một nước thắng sẽ thắng trận. Ban đầu, mỗi robot đánh nước đầu tiên trong chương trình của mình. Nếu hai nước khác nhau, một nước sẽ thắng nước còn lại, vì vậy một robot sẽ thắng trận. Nếu hai nước giống nhau, mỗi robot đánh nước tiếp theo trong chương trình của mình, rồi cứ tiếp tục như vậy.

Mỗi khi một robot đã đi đến cuối chương trình và cần nước tiếp theo, nó quay lại đầu chương trình. Chẳng hạn, nước thứ năm của một robot có chương trình RSSP sẽ là R. Nếu một trận đấu kéo dài quá một googol (\(10^{100}\)) nước, ban giám khảo sẽ tung một đồng xu cân bằng để quyết định robot thắng cuộc.

Sau khi một trận kết thúc, robot thắng sẽ được đặt lại trạng thái, nên nó không có ký ức về trận đấu đó. Trong trận tiếp theo, nó lại bắt đầu bằng nước đầu tiên trong chương trình của mình, rồi cứ tiếp tục như vậy.

Giải đấu diễn ra trong \(K\) vòng và có cấu trúc loại trực tiếp theo "nhánh đấu". Tổng cộng có \(N = 2^K\) robot, được đánh số từ \(0\) đến \(N - 1\). Ở vòng đầu tiên, robot \(0\) đấu với robot \(1\), robot \(2\) đấu với robot \(3\), và cứ thế cho đến cặp robot \(N - 2\) và \(N - 1\). Các robot thua những trận đó bị loại khỏi giải. Ở vòng thứ hai, robot thắng trận \(0\)-\(1\) đối đầu với robot thắng trận \(2\)-\(3\), và cứ tiếp tục như vậy. Khi đến vòng thứ \(K\), chỉ còn một trận duy nhất và trận đó quyết định nhà vô địch chung cuộc.

Tất cả thí sinh khác đều tự tin đến mức đã công khai chương trình robot của họ trên mạng. Tuy nhiên, các robot chưa được gán số, nên không ai biết trước mình sẽ gặp những đối thủ nào. Khi biết tất cả chương trình còn lại, liệu bạn có thể viết một chương trình chắc chắn vô địch giải đấu, bất kể các số hiệu robot được gán như thế nào không?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\); tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(A\): số đối thủ (các robot khác) trong giải. Sau đó có thêm \(A\) dòng; dòng thứ \(i\) trong số này chứa chuỗi \(C_i\) gồm các chữ cái in hoa, biểu diễn chương trình của robot đối thủ thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y. Nếu tồn tại một chuỗi dài từ \(1\) đến \(500\) ký tự được đảm bảo sẽ vô địch giải đấu như mô tả ở trên, thì y phải là chuỗi chữ cái in hoa biểu diễn chương trình đó. Nếu không, y phải là IMPOSSIBLE, viết bằng chữ in hoa.

Ràng buộc

• \(1 \le T \le 100\).
• Mỗi ký tự trong \(C_i\) là một trong các chữ cái in hoa R, P, hoặc S, với mọi \(i\).
• \(A = 2^K - 1\) với một số nguyên \(K \ge 1\).

Phân nhóm

Test Set 1 (Visible)

• \(1 \le A \le 7\).
• Độ dài của \(C_i\) nằm trong khoảng từ \(1\) đến \(5\) ký tự, với mọi \(i\).

Test Set 2 (Hidden)

• \(1 \le A \le 255\).
• Độ dài của \(C_i\) nằm trong khoảng từ \(1\) đến \(500\) ký tự, 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.

Ví dụ

3
1
RS
3
R
P
S
7
RS
RS
RS
RS
RS
RS
RS

Case #1: RSRSRSP
Case #2: IMPOSSIBLE
Case #3: P

Nguồn

Google Code Jam 2019, Vòng 1C, bài Robot Programming Strategy.

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