Maryam và Peiling gần đây đang thực hành một trò ảo thuật với các con số, và họ cần sự giúp đỡ của bạn để thực hiện chính xác. Trò chơi diễn ra như sau: Maryam bắt đầu bằng cách chọn N số nguyên ngẫu nhiên độc lập, mỗi số nằm trong khoảng từ 2 đến M (bao gồm cả hai đầu), xuất hiện với xác suất bằng nhau, và viết chúng lên N tấm thẻ, mỗi thẻ một số. Lưu ý rằng một số con số có thể giống nhau. Sau đó, cô ấy lặp lại các bước sau K lần: lấy một tập con ngẫu nhiên của các tấm thẻ (mỗi tấm thẻ được chọn với xác suất 0.5), và viết ra tích của các con số trên những tấm thẻ đó. Sau khi hoàn thành, cô ấy cho Peiling xem tất cả K tích số đó, và mục tiêu của Peiling là đoán xem N số ban đầu là gì, chỉ dựa vào N, M và các tích số.
Ví dụ về một trò chơi với \(N=3, M=4, K=4\) có thể diễn ra như sau: đầu tiên, Maryam chọn 3 số ngẫu nhiên từ 2 đến 4 — giả sử cô ấy chọn ngẫu nhiên \(A_1=3, A_2=3\) và \(A_3=4\). Sau đó, cô ấy tính bốn tích của các tập con ngẫu nhiên từ ba số đó. Ví dụ, giả sử các tích đó là \(A_1 \times A_2=9\), \(A_3=4\), \(A_1 \times A_2 \times A_3=36\), và \(1=1\) (tích cuối cùng không có số nào, nên nó bằng 1). Peiling nhận được các số 9, 4, 36, 1 từ cô ấy, và cũng được biết rằng \(N=3\) và \(M=4\). Trong trường hợp này, chỉ cần nhìn thấy số 36 là đủ để tìm ra các số ban đầu, vì cách duy nhất để biểu diễn số đó dưới dạng tích của tối đa 3 số, mỗi số tối đa là 4, là \(3 \times 3 \times 4\). Vì vậy, Peiling nói rằng các số ban đầu là 3, 3 và 4, và khán giả rất ấn tượng.
Trong một số trường hợp khác, việc đoán các số ban đầu không đơn giản như vậy. Ví dụ, có thể xảy ra trường hợp tất cả các tích đều bằng 1. Trong trường hợp đó, không có cách nào để biết bất cứ điều gì về các số ẩn, vì vậy Peiling không thể luôn luôn đúng. Tuy nhiên, Peiling biết rằng Maryam tuân thủ quy trình chính xác như mô tả ở trên: cô ấy chọn N số đầu tiên là các số nguyên độc lập phân phối đều từ 2 đến M, sau đó chọn K tập con ngẫu nhiên độc lập, chọn mỗi số vào mỗi tập con một cách độc lập với xác suất 0.5. Hãy giúp Peiling sử dụng kiến thức đó để đưa ra những dự đoán tốt hơn!
Giải quyết bài toán này
Bài toán này hơi bất thường đối với Code Jam. Bạn sẽ được cung cấp R bộ số độc lập, mỗi bộ gồm K số, và bạn nên in ra câu trả lời cho mỗi bộ — phần này giống như bình thường. Tuy nhiên, bạn không cần phải trả lời đúng tất cả các câu hỏi! Giải pháp của bạn sẽ được coi là đúng nếu câu trả lời cho ít nhất X bộ là chính xác, với giá trị X được cho trong phần Ràng buộc cho dữ liệu đầu vào tương ứng bên dưới. Tuy nhiên, bạn phải tuân thủ định dạng đầu ra, ngay cả đối với các bộ mà câu trả lời của bạn không chính xác. Điều duy nhất có thể sai ở bất kỳ bộ nào mà vẫn cho phép bạn được đánh giá là đúng là các chữ số bạn in ra; nhưng vẫn phải có chính xác N chữ số được in cho mỗi trường hợp, và mỗi chữ số phải nằm trong khoảng từ 2 đến M.
Bài toán này có yếu tố ngẫu nhiên, và do đó có thể xảy ra trường hợp ngay cả giải pháp tốt nhất có thể cũng không đưa ra được X dự đoán chính xác (hãy nhớ tình huống khi tất cả các tích đều bằng 1?) cho một dữ liệu đầu vào nhất định. Vì lý do đó, bài toán này không có dữ liệu đầu vào Lớn (Large), mà thay vào đó có hai dữ liệu đầu vào Nhỏ (Small). Điều đó có nghĩa là bạn có thể thử lại nếu bạn nghĩ rằng mình không may mắn. Bạn chỉ có thể thử giải dữ liệu Nhỏ thứ hai sau khi đã giải xong dữ liệu Nhỏ thứ nhất. Nếu không, cả hai dữ liệu Nhỏ đều hoạt động theo cách giống như dữ liệu Nhỏ cho bất kỳ bài toán nào khác: bạn có thể thử nhiều lần và sẽ bị phạt 4 phút cho các lần nộp bài sai nếu sau đó bạn giải được dữ liệu đó, ngay cả khi lý do duy nhất bạn làm sai là do may rủi.
Chúc may mắn!
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T, luôn bằng 1. Dòng thứ hai của tệp đầu vào chứa bốn số nguyên cách nhau bởi dấu cách R, N, M và K, theo thứ tự đó. R dòng tiếp theo mô tả một bộ gồm K tích số mỗi bộ. Mỗi dòng chứa K số nguyên cách nhau bởi dấu cách — các tích mà Maryam đưa cho Peiling. Đảm bảo rằng tất cả các bộ trong dữ liệu đầu vào được tạo ngẫu nhiên độc lập theo quy trình từ mô tả bài toán.
Dữ liệu ra
Trên dòng đầu tiên, in ra "Case #1:". Trên mỗi dòng trong R dòng tiếp theo, in ra N chữ số — dự đoán của bạn cho các số ẩn của Maryam cho bộ tích tương ứng. Bạn có thể in các số cho mỗi bộ theo bất kỳ thứ tự nào, nhưng phải có chính xác N chữ số, mỗi chữ số từ 2 đến M (lưu ý rằng \(M < 10\), vì vậy không có số nào nhiều hơn một chữ số). Không đặt dấu cách giữa các chữ số.
Ràng buộc
Phân nhóm
Dữ liệu Nhỏ thứ nhất (Test set 1 - Visible)
- \(T = 1\).
- \(R = 100\).
- \(N = 3\).
- \(M = 5\).
- \(K = 7\).
- Bạn cần trả lời đúng ít nhất \(X = 50\) bộ.
Dữ liệu Nhỏ thứ hai (Test set 2 - Visible)
- \(T = 1\).
- \(R = 8000\).
- \(N = 12\).
- \(M = 8\).
- \(K = 12\).
- Bạn cần trả lời đúng ít nhất \(X = 1120\) bộ.
Đ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/41 |
24,39% |
| Test Set 2 |
31/41 |
75,61% |
Ví dụ
Ví dụ 1
Input
1
2 3 4 4
9 4 36 1
1 1 1 1
Output
Case #1:
343
222
Note
Dữ liệu mẫu không tuân theo các giới hạn của cả hai bộ dữ liệu. Trong dữ liệu mẫu, bạn cần trả lời đúng ít nhất \(X=1\) bộ.
Trong dữ liệu mẫu, Maryam đã chọn các số 3, 3, 4 lần đầu tiên, và các số 2, 4, 4 lần thứ hai. Trong đầu ra mẫu, Peiling đã đoán đúng lần đầu tiên, nhưng không đúng lần thứ hai.
Nguồn
Google Code Jam 2013, Vòng 1A, bài Good Luck.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
