Google Code Jam 2022 - Schrödinger and Pavlov - LQDOJ: Le Quy Don Online Judge

Google Code Jam 2022 - Schrödinger and Pavlov

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

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

Câu chuyện, mọi tên gọi, nhân vật và sự việc được miêu tả trong đề bài này đều là hư cấu. Không có ý định ám chỉ bất kỳ người thật nào và cũng không nên suy diễn như vậy.

Năm 1935, một cuộc gặp giữa hai người đoạt giải Nobel đang tạo ra những kết quả đáng kinh ngạc. Schrödinger, một nhà vật lý nổi tiếng, mời Pavlov, một nhà sinh lý học nổi tiếng, đến xem các thí nghiệm của ông với những con mèo trong hộp. Pavlov dẫn theo chó của mình để tiếp tục nghiên cứu riêng, và sự kết hợp ấy đã tạo ra một tình huống hết sức thú vị.

Schrödinger có một hàng gồm \(N\) chiếc hộp. Một số hộp chắc chắn có mèo, một số hộp chắc chắn không có mèo, còn một số hộp có thể có hoặc không có mèo. Mỗi hộp chỉ đủ chỗ cho đúng một con mèo. Mỗi hộp cũng được trang bị một đường hầm lượng tử đặc biệt, cho phép con mèo trong hộp đi tới một hộp cụ thể khác nếu hộp đích đang trống. Các đường hầm chỉ hoạt động theo một chiều.

Mèo thường điềm tĩnh, im lặng và không dùng đường hầm trừ khi bị giật mình. Khi một vị khách thứ ba không báo trước bấm chuông, chó của Pavlov lập tức phấn khích rồi bắt đầu chạy và sủa. Chó xuất phát tại hộp \(1\) và chạy về phía hộp \(N\). Trên đường chạy, nó lần lượt đi sát từng hộp. Khi chó đi sát một hộp có mèo, con mèo trong hộp đó bị giật mình. Nó kiểm tra đường hầm hiện có và, nếu hộp đích trống, dùng đường hầm để chạy thoát. Nếu hộp đích đã bị chiếm, mèo ở nguyên trong hộp hiện tại. Cùng một con mèo có thể bị giật mình nhiều lần nếu nó chuyển tới một hộp mà chó sẽ đi qua sau đó; mỗi lần bị giật mình, nó lại hành động theo đúng cách trên (và ở mỗi lần sau chỉ dùng đường hầm mới hiện có tại hộp đang đứng).

Sau khi chó của Pavlov cuối cùng dừng ngay cạnh hộp cuối cùng, Pavlov hỏi Schrödinger trong hộp cuối có mèo hay không. Đúng với danh tiếng của mình, Schrödinger trả lời rằng ông không biết. Pavlov nhận thấy đáp án có thể phụ thuộc vào việc ban đầu các hộp chưa biết có mèo hay không. Hơn nữa, vì có \(k\) hộp chưa biết nên có \(2^k\) cấu hình ban đầu khả dĩ, mỗi cấu hình ứng với một cách kết hợp trạng thái của các hộp chưa biết. Pavlov nói với Schrödinger rằng họ nên tính xem có bao nhiêu trong số \(2^k\) cấu hình ban đầu ấy dẫn tới việc hộp cuối cùng có mèo. Bạn hãy thực hiện lại phép tính đó. Vì kết quả có thể rất lớn, chỉ cần in phần dư khi chia kết quả cho số nguyên tố \(10^9+7\) (\(1000000007\)).

Không có mèo, chó hay người đoạt giải Nobel nào bị tổn hại trong quá trình xây dựng đề bài này.

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 đúng ba dòng. Dòng đầu của một bộ test chứa số nguyên \(N\), số hộp trong thí nghiệm của Schrödinger. Các hộp được đánh số từ \(1\) đến \(N\) theo thứ tự mà chó của Pavlov đi qua. Dòng thứ hai chứa một chuỗi \(S\) gồm \(N\) ký tự. Ký tự thứ \(i\) của \(S\) (tính từ trái sang phải) biểu diễn nội dung hộp \(i\): chữ hoa C nếu hộp có mèo, dấu chấm . nếu hộp không có mèo, và dấu hỏi ? nếu chưa biết hộp có mèo hay không. Dòng thứ ba chứa \(N\) số nguyên \(B_1,B_2,\ldots,B_N\); với mọi \(i\), có một đường hầm đi ra từ hộp \(i\) và đi vào hộp \(B_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là số cấu hình ban đầu khiến cuối cùng có một con mèo trong hộp cuối và con mèo ấy không thể thoát dù nghe tiếng sủa, lấy modulo số nguyên tố \(10^9+7\) (\(1000000007\)).

Ràng buộc

\(1\le T\le1234\).
Độ dài của \(S\) bằng \(N\).
Mỗi ký tự của \(S\) là chữ hoa C, dấu chấm ., hoặc dấu hỏi ?.
\(1\le B_i\le N\) với mọi \(i\).
\(B_i\ne i\) với mọi \(i\).

Phân nhóm

Phân nhóm 1 (phản hồi hiện)

\(1\le N\le100\).
\(i-5\le B_i\le i+5\) với mọi \(i\) (mọi đường hầm đều nối tới một hộp ở gần).

Phân nhóm 2 (phản hồi ẩn)

\(1\le N\le5000\).

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

Phân nhóm	Điểm Google Code Jam	Tỷ lệ điểm của bài
Phân nhóm 1	8/50	16%
Phân nhóm 2	42/50	84%

Ví dụ

Ví dụ 1

Input

4
4
??.C
2 3 1 3
4
????
2 3 1 3
6
?.????
6 6 6 6 6 5
34
????????????????????????????????CC
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 33

Output

Case #1: 1
Case #2: 2
Case #3: 15
Case #4: 294967268

Giải thích

Test mẫu #1 được minh họa trong đề bài. Có \(4\) cấu hình khả dĩ:

...C: chó chạy qua ba hộp đầu mà không làm thay đổi gì vì không có mèo ở đó. Khi nó tới hộp cuối, mèo nghe thấy và chạy sang hộp 3. Vì vậy cuối cùng hộp cuối không có mèo.
C..C: khi chó sủa gần hộp 1, mèo bị giật mình và đi qua đường hầm tới hộp 2 đang trống. Cùng con mèo ấy lại bị giật mình khi chó sủa gần hộp 2 và đi tới hộp 3. Khi chó sủa cạnh hộp 3, mèo nghe thấy rồi quay về hộp 1. Vì thế, khi chó tới hộp 4 và con mèo còn lại nghe thấy, hộp 3 đang trống nên nó chạy thoát; cuối cùng hộp cuối trống.
.C.C: trường hợp này rất giống trường hợp trước. Sau khi chó đi qua hộp đầu mà không có gì xảy ra, trạng thái giống như ở trường hợp trên, nên kết quả cuối cùng cũng vậy: hộp cuối trống.
CC.C: mèo ở hộp đầu không thể thoát khi nghe tiếng chó nên vẫn ở hộp 1. Sau đó, mèo hộp 2 bị giật mình và chạy sang hộp 3, tạo trạng thái C.CC. Khi chó tới hộp 3, mèo ở đó không thể chạy sang hộp 1 nên trạng thái giữ nguyên. Cuối cùng, khi chó tới hộp cuối, mèo ở đó không thể thoát vì lần này hộp 3 đã bị chiếm. Do đó, sau khi chó kết thúc hành trình, hộp cuối vẫn có mèo.

Trong \(4\) khả năng, chỉ có \(1\) khả năng (khả năng cuối) kết thúc với một con mèo ở hộp cuối, nên đáp án là \(1\).

Trong Test mẫu #2, các đường hầm được bố trí giống Test mẫu #1. Vì không có đường hầm nào đi vào hộp cuối, những cấu hình ban đầu không có mèo ở hộp cuối cũng không thể kết thúc với mèo ở đó, nên không cần đếm chúng. Ta còn \(8\) cấu hình: \(4\) cấu hình đã xét ở Test mẫu #1, trong đó chỉ \(1\) cấu hình kết thúc với mèo ở hộp cuối; và \(4\) cấu hình còn lại là ..CC, C.CC, .CCC, CCCC. Trong bốn cấu hình bổ sung này, chỉ cấu hình cuối cùng để lại mèo ở hộp cuối. Tổng cộng có \(2\) cấu hình.

Trong Test mẫu #3, để một con mèo vẫn ở hộp cuối sau khi chó sủa gần nó, lúc ấy cả hộp cuối lẫn hộp 5 đều phải bị chiếm (nếu không thì hoặc hộp cuối không có mèo, hoặc mèo sẽ chạy sang hộp 5). Vì không có đường hầm nào đi vào hộp 5 nên một con mèo phải ở đó từ đầu. Chỉ cần có thêm một con mèo ở bất kỳ hộp nào khác, hộp 6 sẽ được chiếm (hoặc vẫn bị chiếm) trước khi mèo ở hộp 5 có cơ hội thoát, nên mọi cấu hình như vậy đều kết thúc với mèo ở hộp cuối. Như đã lập luận, chỉ một con mèo là chưa đủ. Vậy cần đếm số cấu hình có mèo ở hộp 5 và có ít nhất một con mèo khác. Có \(2^4\) cấu hình có mèo ở hộp 5, trong đó chỉ \(1\) cấu hình không có mèo nào khác, nên đáp án là \(2^4-1=15\).

Trong Test mẫu #4, với cả \(2^k\) cách mà \(k\) hộp chưa biết có thể tồn tại mèo, cuối cùng đều còn một con mèo ở hộp cuối.

Nguồn

Google Code Jam 2022, Chung kết thế giới, bài Schrödinger and Pavlov.

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

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

Google Code Jam 2022 - World Finals (5 Tháng 8., 2022)