Overrandomized

Đề bài

Lưu ý: Mỗi khi đề bài nói một thứ được chọn ngẫu nhiên, điều đó có nghĩa là thứ ấy được chọn theo phân phối đều trên tất cả các khả năng hợp lệ và độc lập với mọi lựa chọn khác.

Công ty Banana Rocks Inc. vừa viết một dịch vụ sinh số ngẫu nhiên cao cấp trên nền tảng đám mây, được kỳ vọng sẽ trở thành tiêu chuẩn vàng mới về tính ngẫu nhiên.

Thiết kế ban đầu là một nhóm máy chủ sẽ nhận yêu cầu dưới dạng một số nguyên dương duy nhất \(M\) có không quá U chữ số thập phân, rồi trả về một số nguyên được chọn ngẫu nhiên trong đoạn từ \(1\) đến \(M\), kể cả hai đầu mút. Tuy nhiên, thay vì viết kết quả bằng các chữ số từ \(0\) đến \(9\) như thông thường, các máy chủ đã bị "ngẫu nhiên hóa quá mức". Mỗi máy chủ có một tập ngẫu nhiên gồm \(10\) chữ cái tiếng Anh in hoa đôi một khác nhau để dùng làm chữ số, cùng một ánh xạ ngẫu nhiên từ các chữ cái ấy tới các giá trị phân biệt trong khoảng từ \(0\) đến \(9\).

Mô tả chính thức của tình huống hiện tại như sau: mỗi máy chủ có một chuỗi chữ số \(D\) gồm đúng \(10\) chữ cái tiếng Anh in hoa khác nhau. Chuỗi chữ số xác định ánh xạ giữa các chữ cái và các chữ số hệ cơ số 10: ký tự thứ \(j\) tính từ trái sang của \(D\) (đánh số từ \(0\)) là chữ số hệ cơ số 10 có giá trị \(j\). Ví dụ, nếu \(D\) là CODEJAMFUN thì C biểu diễn chữ số \(0\), O biểu diễn chữ số \(1\) và N biểu diễn chữ số \(9\). Khi dùng chuỗi chữ số đó, số \(379009\) sẽ được mã hóa thành EFNCCN.

Khi nhận truy vấn thứ \(i\) với tham số nguyên \(M_i\), máy chủ:

• chọn ngẫu nhiên một số nguyên \(N_i\) trong đoạn từ \(1\) đến \(M_i\), kể cả hai đầu mút;
• viết số đó thành một chuỗi trong hệ cơ số 10 không có chữ số \(0\) ở đầu, dùng ký tự thứ \(j\) của \(D\) (đánh số từ \(0\)) làm chữ số có giá trị \(j\); và
• trả về chuỗi thu được làm phản hồi \(R_i\).

Chúng tôi đã thu thập một số dữ liệu mà chúng tôi tin rằng có thể dùng để khôi phục chuỗi chữ số bí mật \(D\) của từng máy chủ. Chúng tôi gửi \(10^4\) truy vấn đến mỗi máy chủ. Với mỗi truy vấn, chúng tôi chọn ngẫu nhiên một giá trị \(M_i\) trong đoạn từ \(1\) đến \(10^{\mathbf{U}}-1\), kể cả hai đầu mút, và nhận phản hồi \(R_i\), là một chuỗi có không quá U chữ cái tiếng Anh in hoa. Chúng tôi ghi lại các cặp \((M_i, \mathbf{R_i})\). Trong lúc chuyển các bản ghi này sang một thiết bị lưu trữ dữ liệu mới, giá trị của tất cả các số nguyên \(M_i\) trong bản ghi của một số máy chủ đã bị hỏng và không thể đọc được.

Bạn có thể giúp chúng tôi tìm chuỗi chữ số \(D\) của từng máy chủ không?

Dữ liệu vào

Dòng đầu tiên cho biết số lượng bộ test T. Sau đó là T bộ test. Mỗi bộ test chứa các bản ghi của một máy chủ và bắt đầu bằng một dòng chứa số nguyên duy nhất U, biểu thị rằng \(10^{\mathbf{U}}-1\) là cận trên (có tính cả cận) của miền mà từ đó chúng tôi chọn các số nguyên \(M_i\) để truy vấn máy chủ ấy. Tiếp theo là đúng \(10^4\) dòng. Mỗi dòng chứa một số nguyên \(Q_i\) (trong hệ cơ số 10, dùng các chữ số từ \(0\) đến \(9\) như thông thường) và một chuỗi \(R_i\), lần lượt biểu diễn truy vấn và phản hồi thứ \(i\). Nếu \(Q_i\) \(= -1\) thì số nguyên \(M_i\) được dùng cho truy vấn thứ \(i\) là không xác định. Nếu không, \(Q_i\) \(= M_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)) và y là chuỗi chữ số \(D\) của máy chủ được xét trong bộ test x.

Ràng buộc

• \(1 \le \mathbf{T} \le 10\).
• \(D\) là một chuỗi gồm đúng \(10\) chữ cái tiếng Anh in hoa khác nhau, được chọn độc lập và theo phân phối đều từ tập tất cả các chuỗi như vậy.
• Với mọi \(i\), \(M_i\) được chọn độc lập và theo phân phối đều trong đoạn từ \(1\) đến \(10^{\mathbf{U}}-1\), kể cả hai đầu mút.
• Với mọi \(i\), \(N_i\) được chọn độc lập và theo phân phối đều trong đoạn từ \(1\) đến \(M_i\), kể cả hai đầu mút.
• Với mọi \(i\), \(R_i\) là biểu diễn trong hệ cơ số 10 của \(N_i\), dùng ký tự thứ \(j\) tính từ trái sang của \(D\) (đánh số từ \(0\)) làm chữ số có giá trị \(j\).

Phân nhóm

Test Set 1 (Hiển thị kết quả chấm)

• \(Q_i\) \(= M_i\) với mọi \(i\).
• U \(= 2\).

Test Set 2 (Hiển thị kết quả chấm)

• \(Q_i\) \(= M_i\) với mọi \(i\).
• U \(= 16\).

Test Set 3 (Hiển thị kết quả chấm)

• \(Q_i\) \(= -1\) với mọi \(i\).
• U \(= 16\).

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

1
2
20 P
-------------------------------
Đã lược bỏ 9999 dòng dữ liệu vào.
Hãy dùng nút tải xuống ở phía trên
để xem toàn bộ dữ liệu vào mẫu.
-------------------------------

Case #1: TPFOXLUSHB

Nguồn

Google Code Jam 2020, Vòng 1C, bài Overrandomized.

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