Google Code Jam 2010 - Round 3

Tôi muốn tạo một trang web chơi poker trực tuyến. Một thành phần rất quan trọng của hệ thống như vậy là bộ tạo số ngẫu nhiên. Nó cần phải nhanh và đủ ngẫu nhiên. Đây là một phương án thỏa hiệp mà tôi đã nghĩ ra. Tôi cần một cách để tạo các số ngẫu nhiên có độ dài tối đa là \(D\). Kế hoạch của tôi là chọn một số nguyên tố \(P \le 10^D\). Tôi cũng sẽ chọn các số nguyên không âm \(A\) và \(B\). Cuối cùng, tôi sẽ chọn một hạt giống (seed) là số nguyên \(S\) nằm trong khoảng từ \(0\) đến \(P-1\), bao gồm cả hai đầu.

Để xuất ra chuỗi các số giả ngẫu nhiên của mình, đầu tiên tôi sẽ xuất ra \(S\) và sau đó tính giá trị mới của \(S\) như sau:
S := (A*S + B) mod P.

Sau đó, tôi sẽ xuất giá trị mới của \(S\) là số tiếp theo trong chuỗi và cập nhật \(S\) một lần nữa bằng cách sử dụng cùng một công thức. Tôi có thể lặp lại việc này bao nhiêu lần tùy ý.

Bạn có nghĩ rằng đây là một bộ tạo số ngẫu nhiên tốt không? Bạn có thể viết một chương trình nhận vào \(K\) phần tử liên tiếp của một chuỗi được tạo bởi bộ tạo số ngẫu nhiên của tôi và in ra phần tử tiếp theo của chuỗi đó không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa \(D\) và \(K\). Dòng tiếp theo chứa \(K\) phần tử liên tiếp được tạo bởi bộ tạo số ngẫu nhiên loại được mô tả ở trên.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự của bộ thử nghiệm (bắt đầu từ 1) và y là số tiếp theo trong chuỗi, hoặc chuỗi "I don't know." nếu câu trả lời không duy nhất.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le K \le 10\).
• \(K\) số nguyên sẽ là các phần tử liên tiếp của một chuỗi được tạo bởi bộ tạo số ngẫu nhiên thuộc loại mô tả ở trên.

Phân nhóm

• Small dataset (Test set 1 - Visible): \(1 \le D \le 4\).
• Large dataset (Test set 2 - Hidden): \(1 \le D \le 6\).

Đ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
2 10
0 1 2 3 4 5 6 7 8 9
3 1
13
1 5
6 6 6 6 6

Case #1: 10
Case #2: I don't know.
Case #3: 6

Nguồn

Google Code Jam 2010, Vòng 3, bài De-RNG-ed.

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

Chúng tôi đã nghĩ ra một bài toán tuyệt vời cho Google Code Jam 2010 liên quan đến việc các thí sinh giải một phép toán ẩn chữ (cryptarithm). Nhưng chúng tôi cần sự giúp đỡ của bạn trong việc tạo các bộ test cho bài toán; chính xác hơn, chúng tôi quan tâm đến các phương trình cộng đủ tốt (theo nghĩa được định nghĩa dưới đây) để chuyển đổi thành các phép toán ẩn chữ.

Bạn không cần biết phép toán ẩn chữ là gì để giải bài toán này, vì chúng tôi sẽ cung cấp tất cả các định nghĩa cần thiết. Chúng tôi định nghĩa một phương trình ẩn chữ là một phương trình cộng được viết sao cho tất cả các số hạng (các số được cộng) và tổng được căn lề phải trên cùng một biên như thế này:

124
 31
 25
---
180

Ngoài ra, đối với mỗi cột của phương trình ẩn chữ, tất cả các chữ số của các số hạng trong cột đó phải khác nhau. Lưu ý rằng chúng tôi không bao gồm tổng trong ràng buộc này. Ví dụ, trong phương trình trên, cột thứ nhất chỉ chứa chữ số 1, cột thứ hai chứa các chữ số 2, 3 và 2, và cột thứ ba chứa các chữ số 4, 1 và 5. Phương trình này không phải là một phương trình ẩn chữ vì cột thứ hai chứa hai chữ số 2. Tuy nhiên, nó sẽ là một phương trình ẩn chữ nếu chúng ta thay số hạng cuối cùng bằng 15 (và tổng bằng 170).

Lưu ý rằng các số hạng trong một phương trình ẩn chữ luôn là số dương và được viết không có chữ số 0 ở đầu. Thứ tự của các số hạng không quan trọng (nói cách khác, hai phương trình chỉ khác nhau về thứ tự của các số hạng được coi là giống nhau).

Ví dụ trên là ở hệ cơ số 10, nhưng chúng tôi cũng quan tâm đến các phương trình ẩn chữ ở các hệ cơ số khác. Lưu ý rằng một "chữ số" trong hệ cơ số \(b\) có thể là bất kỳ số nguyên nào từ \(0\) đến \(b-1\). Dưới đây là một phương trình ẩn chữ trong hệ cơ số 23:

 I7B
 JJJ
----
1F47

Trong ví dụ này, "I" đại diện cho chữ số 18, "B" đại diện cho chữ số 11, "J" đại diện cho chữ số 19, và "F" đại diện cho chữ số 15. Trong hệ thập phân, hai số hạng là \(18 \cdot 23^2 + 7 \cdot 23 + 11 = 9694\) và \(19 \cdot 23^2 + 19 \cdot 23 + 19 = 10507\), và tổng là \(1 \cdot 23^3 + 15 \cdot 23^2 + 4 \cdot 23 + 7 = 20201\). Xin lưu ý rằng việc ký hiệu các chữ số từ 10 trở lên bằng các chữ cái chỉ nhằm mục đích làm rõ ví dụ; việc chúng ta ký hiệu các chữ số đó như thế nào trong thực tế không quan trọng trong bài toán này.

Có bao nhiêu phương trình ẩn chữ có tổng N cho trước trong hệ cơ số B cho trước?

Vì câu trả lời có thể rất lớn, hãy đưa ra kết quả theo modulo 1000000007.

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. T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương N và B. Tất cả các số đầu vào được cho ở hệ cơ số 10.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng phương trình ẩn chữ khác nhau có tổng đã cho. Vì số này có thể rất lớn, hãy xuất kết quả theo modulo 1000000007. Tất nhiên, bản thân kết quả đầu ra phải ở hệ cơ số 10.

Ràng buộc

• \(1 \le \mathbf{T} \le 20\).

Phân nhóm

• Test set 1 (Visible):

• \(1 \le \mathbf{N} \le 100\).

• \(2 \le \mathbf{B} \le 10\).

• Test set 2 (Hidden):

• \(1 \le \mathbf{N} \le 10^{18}\).

• \(2 \le \mathbf{B} \le 70\).

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

2
6 10
8 4

Case #1: 4
Case #2: 4

6   1   2   1

-   5   4   2
6   -   -   3
    6   6   -
            6

20   11   13   10
--    3    1    3
20   --   --    1
     20   20   --
               20

Nguồn

Google Code Jam 2010, Vòng 3, bài Different Sum.

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

Chúng ta đang lên kế hoạch xây dựng một hàng rào rất dài. Chúng ta đã tìm được một địa điểm lý tưởng để xây dựng, và việc còn lại là thu thập vật liệu.

Từ các cửa hàng vật liệu xây dựng tại địa phương, chúng ta có thể mua số lượng không giới hạn các tấm ván gỗ, mỗi tấm có thể có nhiều độ dài khác nhau. Để tránh lãng phí, chúng ta muốn đảm bảo rằng tổng độ dài của các tấm ván này chính xác bằng độ dài của hàng rào mà chúng ta định xây dựng.

Cho biết độ dài của hàng rào và các độ dài tấm ván có thể sử dụng, số lượng tấm ván tối thiểu cần mua để có được độ dài chính xác là bao nhiêu?

Lưu ý: hàng rào sẽ rất dài!

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ test, T. T bộ test tiếp theo sẽ được đưa ra.

Mỗi bộ test gồm hai dòng. Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách L và N. Chúng đại diện cho tổng độ dài của hàng rào và số lượng các độ dài tấm ván khác nhau có thể mua. Dòng thứ hai chứa N số nguyên cách nhau bởi dấu cách B₁, B₂, ..., Bₙ, đại diện cho tất cả các độ dài tấm ván có thể có.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: M", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và M được xác định như sau:

• Nếu có thể mua một hoặc nhiều tấm ván sao cho tổng độ dài của chúng chính xác bằng L, thì M là số lượng tấm ván tối thiểu cần thiết để thực hiện việc này.
• Ngược lại, M là chuỗi "IMPOSSIBLE".

Ràng buộc

• 1 ≤ T ≤ 50.
• 10¹⁰ ≤ L ≤ 10¹⁸.
• 1 ≤ N ≤ 100.

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): 1 ≤ Bᵢ ≤ 100.
• Tập dữ liệu lớn (Test set 2 - Hidden): 1 ≤ Bᵢ ≤ 100000.

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

2
10000000001 3
23 51 100
10000000001 3
100 52 22

Case #1: 100000004
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2010, Vòng 3, bài Fence.

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

Một số người bán xúc xích đã bắt đầu kinh doanh tại các góc đường (giao lộ) dọc theo một con phố rất dài theo hướng Đông - Tây. Vấn đề là có thể có nhiều người cùng bán tại một góc đường, và khi đó họ sẽ cạnh tranh lẫn nhau. Tuy nhiên, mọi chuyện không hẳn là bế tắc! Những người bán xúc xích đã có một kế hoạch.

Nếu có từ hai người bán trở lên tại cùng một góc đường, thì đúng hai người trong số họ có thể thực hiện một bước di chuyển, nghĩa là:

• Một người di chuyển đến góc đường tiếp theo về phía Đông dọc theo con phố.
• Người kia di chuyển đến góc đường tiếp theo về phía Tây dọc theo con phố.

Hãy nhớ rằng con phố rất dài, vì vậy không có nguy cơ hết góc đường. Cho biết vị trí bắt đầu của tất cả những người bán xúc xích, bạn cần tìm số bước di chuyển tối thiểu họ cần thực hiện trước khi tất cả những người bán được tách rời nhau (nghĩa là mỗi người ở một góc đường khác nhau).

Ví dụ, giả sử con phố bắt đầu với số lượng người bán xúc xích tại mỗi góc đường như sau, liệt kê theo thứ tự từ Tây sang Đông:

... 0 0 2 1 2 0 0 ...

Khi đó, những người bán có thể được tách rời trong 3 bước di chuyển, như hình dưới đây:

... 0 0 2 1 2 0 0 ...
        |
        +--- Do a move here

... 0 1 0 2 2 0 0 ...
          |
          +--- Do a move here

... 0 1 1 0 3 0 0 ...
            |
            +--- Do a move here

... 0 1 1 1 1 1 0 ...

Dữ liệu vào

Mỗi góc đường được gắn nhãn bằng một số nguyên, dương hoặc âm. Với mỗi i, góc đường i+1 là góc đường tiếp theo về phía Đông của góc đường i. Chúng ta sẽ sử dụng hệ thống nhãn này để mô tả các góc đường trong tệp dữ liệu vào.

Dòng đầu tiên của tệp dữ liệu vào chứa số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng số lượng góc đường \(C\) có ít nhất một người bán xúc xích trong cấu hình ban đầu. \(C\) dòng tiếp theo, mỗi dòng chứa một cặp số nguyên cách nhau bởi dấu cách \(P\), \(V\), cho biết có \(V\) người bán tại góc đường \(P\).

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #x: M", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và M là số bước di chuyển tối thiểu cần thực hiện để tất cả người bán kết thúc ở các góc đường khác nhau.

Ràng buộc

• Thời gian giới hạn: 30 giây mỗi bộ test.
• Bộ nhớ giới hạn: 1GB.
• \(1 \le T \le 50\).
• \(1 \le C \le 200\).
• Tất cả các giá trị \(P\) nằm trong khoảng \([-1000000, 1000000]\).
• Trong mỗi bộ test, tất cả các giá trị \(P\) là phân biệt và được liệt kê theo thứ tự tăng dần.
• Tất cả các giá trị \(V\) là số nguyên dương. Giới hạn về tổng của tất cả các giá trị \(V\) được liệt kê bên dưới.
• Luôn có thể tách rời những người bán xúc xích trong một số bước di chuyển hữu hạn.

Phân nhóm

• Small dataset (Test set 1): Tổng số người bán xúc xích trong mỗi bộ test tối đa là 200.
• Large dataset (Test set 2): Tổng số người bán xúc xích trong mỗi bộ test tối đa là 100000.

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

2
3
-1 2
0 1
1 2
2
-1000 1
2000 1

Case #1: 3
Case #2: 0

Nguồn

Google Code Jam 2010, Vòng 3, bài Hot Dog Proliferation.

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