Google Code Jam 2015 - Ominous Omino - LQDOJ: Le Quy Don Online Judge

Google Code Jam 2015 - Ominous Omino

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: 1800 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Một \(N\)-omino là một hình hai chiều tạo bởi \(N\) ô vuông đơn vị ghép trọn cạnh với nhau. Chính xác hơn, 1-omino là một ô vuông \(1\times1\), còn một \(N\)-omino là một \((N-1)\)-omino được ghép một hay nhiều cạnh với một ô vuông \(1\times1\) kề nó. Trong bài này, hai \(N\)-omino được xem là giống nhau nếu có thể biến hình này thành hình kia bằng phép phản chiếu và/hoặc phép quay. Chẳng hạn, đây là năm 4-omino có thể có:

Và đây là một số trong 108 hình 7-omino có thể có:

Richard và Gabriel chơi một trò chơi với ba giá trị định trước \(X,R,C\) theo luật sau:

Richard chọn một hình bất kỳ trong các \(X\)-omino có thể có.
Gabriel phải dùng ít nhất một bản sao của \(X\)-omino đó, cùng với số lượng tùy ý bản sao của bất kỳ \(X\)-omino nào khác (có thể gồm chính hình Richard chọn), để phủ kín một lưới \(R\times C\), không chồng lấn và không tràn ra ngoài. Mỗi ô lưới phải được phủ bởi đúng một trong \(X\) ô của một \(X\)-omino. Gabriel được quay hoặc phản chiếu bao nhiêu hình tùy ý, kể cả hình Richard chọn. Nếu phủ kín được lưới thì Gabriel thắng; nếu không, Richard thắng.

Với \(X,R,C\) cho trước, Richard có thể chọn một \(X\)-omino bảo đảm mình thắng, hay Gabriel được bảo đảm thắng bất kể Richard chọn gì?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi test là một dòng gồm ba số nguyên cách nhau bởi dấu cách: \(X,R,C\).

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là RICHARD nếu tồn tại lựa chọn bảo đảm Richard thắng, hoặc GABRIEL nếu Gabriel thắng với mọi lựa chọn.

Ràng buộc

Phân nhóm

Nhỏ: \(T=64\), \(1\le X,R,C\le4\).
Lớn: \(1\le T\le100\), \(1\le X,R,C\le20\).

Đ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	8/34	23,53%
Test Set 2	26/34	76,47%

Ví dụ

Ví dụ 1

Input

Output

Case #1: GABRIEL
Case #2: RICHARD
Case #3: RICHARD
Case #4: GABRIEL

Note

Test 1: Richard chỉ có thể chọn domino \(1\times2\). Dù Gabriel đặt nó thế nào trên lưới \(2\times2\), phần trống còn lại vừa khít một domino nữa, nên Gabriel thắng.

Test 2: Richard vẫn phải chọn domino, nhưng nó luôn để lại một lỗ \(1\times1\) trên lưới \(1\times3\), không thể lấp bằng 2-omino, nên Richard thắng.

Test 3: Richard có thể chọn 4-omino hình vuông \(2\times2\); nó không thể nằm trọn trong lưới \(4\times1\), nên Richard thắng.

Test 4: Richard có thể chọn thanh thẳng hoặc hình chữ L gồm 3 ô. Trong cả hai trường hợp, Gabriel đặt được hình đó và dùng một bản cùng loại để lấp phần còn lại của lưới \(2\times3\).

Nguồn

Google Code Jam 2015, Vòng loại, bài Ominous Omino.

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 2015 - Qualification Round (11 Tháng tư, 2015)