Google Code Jam 2013 - Qualification Round

Little John rất thích các số đối xứng (palindrome) và coi chúng là những con số "đẹp". Một số đối xứng là một số nguyên có giá trị không đổi khi đọc ngược hay đọc xuôi - ví dụ: 6, 11 và 121 là các số đối xứng, trong khi 10, 12, 223 và 2244 thì không (mặc dù 010=10, nhưng chúng ta không xét các chữ số 0 ở đầu khi xác định một số có phải là số đối xứng hay không).

Gần đây, cậu ấy cũng bắt đầu quan tâm đến các số chính phương và đưa ra định nghĩa về số vừa đẹp vừa phương (fair and square) - đó là một số vừa là số đối xứng, vừa là bình phương của một số đối xứng khác. Ví dụ, 1, 9 và 121 là các số vừa đẹp vừa phương (vì chúng là số đối xứng và lần lượt là bình phương của 1, 3 và 11), trong khi 16, 22 và 676 không phải là số vừa đẹp vừa phương: 16 không phải là số đối xứng, 22 không phải là số chính phương, và mặc dù 676 là số đối xứng và là số chính phương, nhưng nó là bình phương của 26, mà 26 không phải là số đối xứng.

Bây giờ cậu ấy muốn tìm kiếm các số vừa đẹp vừa phương lớn hơn. Nhiệm vụ của bạn là, cho trước một khoảng mà Little John đang tìm kiếm, hãy cho cậu ấy biết có bao nhiêu số vừa đẹp vừa phương trong khoảng đó để cậu ấy biết khi nào mình đã tìm thấy tất cả.

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 \(A\) và \(B\) - các điểm đầu mút của khoảng mà Little John đang xem xét.

Dữ liệu ra

Với mỗi bộ test, hãy xuất ra 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 số vừa đẹp vừa phương lớn hơn hoặc bằng \(A\) và nhỏ hơn hoặc bằng \(B\).

Ràng buộc

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1):
• \(1 \le T \le 100\).
• \(1 \le A \le B \le 1000\).
• Tập dữ liệu lớn thứ nhất (Test set 2):
• \(1 \le T \le 10000\).
• \(1 \le A \le B \le 10^{14}\).
• Tập dữ liệu lớn thứ hai (Test set 3):
• \(1 \le T \le 1000\).
• \(1 \le A \le B \le 10^{100}\).

Đ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 4
10 120
100 1000

Case #1: 2
Case #2: 0
Case #3: 2

Nguồn

Google Code Jam 2013, Vòng loại, bài Fair and Square.

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

Alice và Bob có một bãi cỏ trước nhà, hình dạng là một hình chữ nhật kích thước \(N\) mét x \(M\) mét. Mỗi năm, họ cố gắng cắt cỏ theo một số hoa văn thú vị. Họ từng cắt bằng kéo, việc này rất tốn thời gian; nhưng giờ họ đã có một chiếc máy cắt cỏ tự động mới với nhiều chế độ cài đặt, và họ muốn dùng thử nó.

Máy cắt cỏ mới có cài đặt độ cao - bạn có thể đặt nó ở bất kỳ độ cao \(h\) nào từ 1 đến 100 milimét, và nó sẽ cắt tất cả cỏ cao hơn \(h\) mà nó đi qua xuống độ cao \(h\). Bạn vận hành nó bằng cách đưa máy vào bãi cỏ từ bất kỳ phần nào của mép bãi cỏ; sau đó máy cắt cỏ sẽ đi theo một đường thẳng, vuông góc với mép bãi cỏ mà nó đã đi vào, cắt cỏ trong một dải rộng 1m, cho đến khi nó ra khỏi bãi cỏ ở phía bên kia. Độ cao của máy cắt cỏ chỉ có thể được cài đặt khi nó không ở trên bãi cỏ.

Alice và Bob có một số hoa văn cỏ khác nhau mà họ có thể có trên bãi cỏ của mình. Đối với mỗi hoa văn đó, họ muốn biết liệu có thể cắt cỏ thành hoa văn này bằng máy cắt cỏ mới của họ hay không. Mỗi hoa văn được mô tả bằng cách chỉ định độ cao của cỏ trên mỗi ô vuông 1m x 1m của bãi cỏ.

Ban đầu, cỏ cao 100mm trên toàn bộ bãi cỏ.

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\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên: \(N\) và \(M\). Tiếp theo là \(N\) dòng, với dòng thứ \(i\) chứa \(M\) số nguyên \(a_{i,j}\), mỗi số \(a_{i,j}\) mô tả độ cao mong muốn của cỏ ở ô thứ \(j\) của hàng thứ \(i\).

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à từ "YES" nếu có thể tạo ra hoa văn thứ x bằng máy cắt cỏ, hoặc "NO" nếu không thể.

Ràng buộc

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

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(1 \le N, M \le 10\).

• \(1 \le a_{i,j} \le 2\).

• Large dataset (Test set 2 - Hidden):

• \(1 \le N, M \le 100\).
• \(1 \le a_{i,j} \le 100\).

Đ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
3 3
2 1 2
1 1 1
2 1 2
5 5
2 2 2 2 2
2 1 1 1 2
2 1 2 1 2
2 1 1 1 2
2 2 2 2 2
1 3
1 2 1

Case #1: YES
Case #2: NO
Case #3: YES

Nguồn

Google Code Jam 2013, Vòng loại, bài Lawnmower.

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

Tic-Tac-Toe-Tomek là một trò chơi được chơi trên bảng vuông kích thước \(4 \times 4\). Ban đầu bảng trống, ngoại trừ một ký hiệu 'T' duy nhất có thể xuất hiện ở một trong 16 ô vuông. Có hai người chơi: X và O. Họ thay phiên nhau thực hiện các nước đi, bắt đầu từ X. Trong mỗi nước đi, một người chơi đặt ký hiệu của mình vào một trong các ô trống. Ký hiệu của người chơi X là 'X', và ký hiệu của người chơi O là 'O'.

Sau nước đi của một người chơi, nếu có một hàng, một cột hoặc một đường chéo chứa 4 ký hiệu của người chơi đó, hoặc chứa 3 ký hiệu của người đó và ký hiệu 'T', người đó thắng và trò chơi kết thúc. Nếu không, trò chơi tiếp tục với nước đi của người chơi kia. Nếu tất cả các ô đã được lấp đầy bởi các ký hiệu và không ai thắng, trò chơi kết thúc với kết quả hòa. Xem dữ liệu mẫu để biết ví dụ về các vị trí thắng khác nhau.

Cho mô tả bảng \(4 \times 4\) chứa các ký tự 'X', 'O', 'T' và '.' (trong đó '.' đại diện cho một ô trống), mô tả trạng thái hiện tại của một trò chơi, hãy xác định trạng thái của trò chơi Tic-Tac-Toe-Tomek đang diễn ra. Các trạng thái để lựa chọn là:

• "X won" (trò chơi đã kết thúc và X thắng)
• "O won" (trò chơi đã kết thúc và O thắng)
• "Draw" (trò chơi đã kết thúc và kết quả hòa)
• "Game has not completed" (trò chơi chưa kết thúc)

Nếu có các ô trống và trò chơi chưa kết thúc, bạn nên xuất ra "Game has not completed", ngay cả khi kết quả của trò chơi là không thể tránh khỏi.

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ộ thử nghiệm gồm 4 dòng, mỗi dòng có 4 ký tự, mỗi ký tự là 'X', 'O', '.' hoặc 'T' (dấu ngoặc kép chỉ để làm rõ). Mỗi bộ thử nghiệm được theo sau bởi một dòng trống.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất ra một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là một trong các trạng thái được đưa ra ở trên. Hãy đảm bảo ghi đúng các trạng thái một cách chính xác. Khi bạn chạy mã của mình trên dữ liệu mẫu, nó sẽ tạo ra kết quả mẫu chính xác, bao gồm cả "Case #1: ", chữ cái viết hoa "O" thay vì số "0", v.v.

Ràng buộc

• Bảng trò chơi được cung cấp sẽ đại diện cho một trạng thái hợp lệ đạt được thông qua quá trình chơi trò chơi Tic-Tac-Toe-Tomek như mô tả ở trên.

Phân nhóm

• Small dataset (Test set 1 - Visible): \(1 \le \mathbf{T} \le 10\).
• Large dataset (Test set 2 - Hidden): \(1 \le \mathbf{T} \le 1000\).

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

6
XXXT
....
OO..
....

XOXT
XXOO
OXOX
XXOO

XOX.
OX..
....
....

OOXX
OXXX
OX.T
O..O

XXXO
..O.
.O..
T...

OXXX
XO..
..O.
...O

Case #1: X won
Case #2: Draw
Case #3: Game has not completed
Case #4: O won
Case #5: O won
Case #6: O won

Nguồn

Google Code Jam 2013, Vòng loại, bài Tic-Tac-Toe-Tomek.

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

Theo một bản đồ cũ, bạn đã tình cờ tìm thấy kho báu bí mật của Cướp biển Larry Đáng sợ!

Kho báu bao gồm \(N\) chiếc rương bị khóa, mỗi chiếc chỉ có thể được mở bằng một loại chìa khóa cụ thể. Hơn nữa, một khi chìa khóa đã được sử dụng để mở rương, nó sẽ không bao giờ có thể được sử dụng lại. Bên trong mỗi chiếc rương, tất nhiên bạn sẽ tìm thấy rất nhiều kho báu, và bạn cũng có thể tìm thấy một hoặc nhiều chìa khóa mà bạn có thể sử dụng để mở các rương khác. Một chiếc rương có thể chứa nhiều chìa khóa cùng loại, và bạn có thể giữ bất kỳ số lượng chìa khóa nào.

Bạn đã có sẵn ít nhất một chiếc chìa khóa và bản đồ của bạn cho biết những chiếc chìa khóa nào khác có thể được tìm thấy bên trong các rương khác nhau. Với tất cả thông tin này, bạn có thể tìm ra cách mở tất cả các rương không?

Ví dụ, giả sử kho báu bao gồm bốn chiếc rương như mô tả dưới đây, và bạn bắt đầu với chính xác một chiếc chìa khóa loại 1:

Chest Number  |  Key Type To Open Chest  |  Key Types Inside
--------------+--------------------------+------------------
1             |  1                       |  None
2             |  1                       |  1, 3
3             |  2                       |  None
4             |  3                       |  2

Bạn có thể mở tất cả các rương trong ví dụ này nếu bạn thực hiện chúng theo thứ tự 2, 1, 4, 3. Nếu bạn bắt đầu bằng cách mở rương số 1 trước, thì bạn sẽ dùng hết chiếc chìa khóa duy nhất của mình và bạn sẽ bị kẹt.

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\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên dương \(K\) và \(N\), đại diện cho số lượng chìa khóa bạn có lúc đầu và số lượng rương bạn cần mở.

Tiếp theo là một dòng chứa \(K\) số nguyên, đại diện cho các loại chìa khóa mà bạn có lúc đầu.

Sau đó, sẽ có \(N\) dòng, mỗi dòng đại diện cho một chiếc rương duy nhất. Mỗi dòng sẽ bắt đầu bằng các số nguyên \(T_i\) và \(K_i\), cho biết loại chìa khóa cần thiết để mở rương và số lượng chìa khóa bên trong rương. Hai số nguyên này sẽ được theo sau bởi \(K_i\) số nguyên nữa, cho biết các loại chìa khóa có trong rương đó.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: \(C_1\) \(C_2\) ... \(C_N\)", trong đó x là số thứ tự bộ test (bắt đầu từ 1), và \(C_i\) đại diện cho chỉ số (bắt đầu từ 1) của chiếc rương thứ \(i\) mà bạn nên mở.

Nếu có nhiều cách mở tất cả các rương, hãy chọn cách "nhỏ nhất về mặt từ điển". Nói cách khác, bạn nên chọn làm cho \(C_1\) nhỏ nhất có thể, và nếu có nhiều cách để làm cho \(C_1\) nhỏ nhất có thể, hãy chọn cách làm cho \(C_2\) nhỏ nhất có thể, và cứ tiếp tục như vậy.

Nếu không có cách nào để mở tất cả các rương, thay vào đó bạn nên xuất một dòng chứa "Case #x: IMPOSSIBLE".

Ràng buộc

• \(1 \le T \le 25\).
• \(1 \le K\).
• Tất cả các loại chìa khóa sẽ là các số nguyên từ 1 đến 200 bao gồm cả hai đầu.

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 20\). Trong mỗi bộ test, sẽ có tổng cộng tối đa 40 chìa khóa.
• Large dataset (Test set 2): \(1 \le N \le 200\). Trong mỗi bộ test, sẽ có tổng cộng tối đa 400 chìa khóa.

Đ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 4
1
1 0
1 2 1 3
2 0
3 1 2
3 3
1 1 1
1 0
1 0
1 0
1 1
2
1 1 1

Case #1: 2 1 4 3
Case #2: 1 2 3
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2013, Vòng loại, bài Treasure.

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