Giới thiệu

Bài có nhiều khía cạnh. Trước hết là nhận xét then chốt cho \(X\ge7\). Sau đó editorial trình bày một lời giải vét cạn: sinh mọi \(X\)-omino, mô phỏng từng lựa chọn của Richard, rồi thử mọi cách đặt hình bắt buộc để xem Gabriel có cấu hình thắng hay không. Cuối cùng là lời giải thay thế bằng phân tích đầy đủ từng trường hợp.

Trường hợp \(X\ge7\)

Với \(X\ge7\), Gabriel không thể được bảo đảm thắng. Richard luôn chọn được một \(X\)-omino có lỗ ở giữa, như hình 7-omino bên trái và 10-omino bên phải:

###  ####
#.#  #.##
##.  ###.

Vì Gabriel bắt buộc dùng hình đó ít nhất một lần nhưng không \(X\)-omino nào lọt vào lỗ một ô, lưới không thể được phủ kín. Do đó Richard luôn thắng khi \(X\ge7\).

Số ô phải là bội của \(X\)

Nếu \(RC\) không chia hết cho \(X\), Gabriel không thể thắng vì mỗi hình phủ đúng \(X\) ô.

Nguyên lý này còn áp dụng sau khi đặt hình bắt buộc. Nếu hình ấy chia phần trống thành hai hay nhiều miền liên thông cạnh, mọi miền phải có số ô chia hết cho \(X\). Ví dụ, đặt 4-omino sau vào lưới \(2\times6\):

.##...
##....

Hai thành phần trống có kích thước 1 và 7; một miền quá nhỏ và cả hai đều không là bội của 4, nên cách đặt này thất bại. Có thể tìm các thành phần bằng flood fill. Với các trường hợp \(X\le6\) đang xét, phân tích trường hợp bên dưới chứng minh rằng nếu mọi miền trống có kích thước là bội của \(X\), chúng có thể được lấp bằng các \(X\)-omino.

Sinh mọi \(X\)-omino

Bắt đầu với 1-omino duy nhất:

#

Đặt một # giữa một bảng đủ lớn (chẳng hạn \(20\times20\)), rồi đệ quy thêm # kề cạnh một ô đã đặt cho đến khi có \(X\) ô. Với 2-omino, các dạng sinh ra gồm:

#   ##
#

Quá trình tạo nhiều bản trùng. Quanh ô đầu, bốn vị trí có thể được đánh số:

.1.
4#2
.3.

nhưng 4# tương đương #2, và 1# tương đương 3#. Có thể chuẩn hóa theo tịnh tiến, quay và phản chiếu để loại trùng. Ta tiền tính mọi hình cho \(1\le X\le6\); cũng có thể liệt kê bằng tay. Thủ tục trên sinh cả các hướng quay/phản chiếu, ví dụ:

#.  .#  .##  ##.
##  ##  ##.  .##
.#  #.

Giữ tất cả các hướng này vẫn đủ nhanh.

Chiến lược vét cạn

Sau khi loại ngay \(X\ge7\) và \(X\nmid RC\), lần lượt cho Richard chọn từng hình. Nếu có một hình mà Gabriel không thể xử lý, Richard thắng; chỉ khi Gabriel thắng với mọi hình mới trả lời Gabriel.

Với một hình đã chọn, thử đặt nó ở mọi vị trí trên cả lưới \(R\times C\) và \(C\times R\). Nếu hình không lọt vào cả hai hướng, Richard thắng. Sau mỗi cách đặt hợp lệ, flood fill phần trống. Gabriel thắng với hình đó nếu tồn tại cách đặt mà mọi thành phần trống có kích thước chia hết cho \(X\).

Ví dụ với hình 4-omino

.##
##.

trên lưới \(2\times4\), hai cách đặt đại diện là

.##.
##..

và

..##
.##.

Cả hai chia phần trống thành các miền 1 và 3 ô, nên Gabriel thua.

Với hình vuông

##
##

trên lưới \(2\times6\), cách đặt

.##...
.##...

tạo các miền 2 và 6, không là bội của 4. Nhưng các cách

##....
##....

và

..##..
..##..

lần lượt để lại một miền 8 ô hoặc hai miền 4 ô, nên Gabriel thắng.

Ta thử cả \(C\times R\) để bao quát phép quay 90 độ của hình. Thay vì quay hình, quay lưới; các phép quay/phản chiếu còn lại đối xứng trong không gian lưới. Tính đúng của tiêu chuẩn “mọi thành phần là bội của \(X\)” dựa trên phân tích đầy đủ tiếp theo.

Lời giải thay thế: phân tích từng trường hợp

Đặt \(S=\min(R,C)\) và \(L=\max(R,C)\). Richard thắng khi một trong các điều kiện sau đúng; nếu không, Gabriel thắng:

1. \(X\nmid SL\);
2. \(X=3\) và \(S=1\);
3. \(X=4\) và \(S\le2\);
4. \(X=5\) và \(S\le2\), hoặc \((S,L)=(3,5)\);
5. \(X=6\) và \(S\le3\);
6. \(X\ge7\).

Điều 1 và 6 đã được chứng minh. Với điều 2, Richard chọn

#.
##

hình này không thể lọt vào bảng có \(S=1\).

Với điều 3, Richard chọn

###
.#.

Khi \(S=2\), hình chia phần trống thành hai miền không thể đồng thời có kích thước là bội của 4; khi \(S=1\), hình không lọt.

Với điều 4 khi \(S\le2\), Richard chọn

#..
##.
.##

hình không lọt vào chiều rộng đó. Khi \((S,L)=(3,5)\), dùng cùng hình; thử mọi vị trí đều cho thấy Gabriel không thể thắng:

#....  .#...  ..#..
##...  .##..  ..##.
.##..  ..##.  ...##

Với điều 5, Richard chọn

.#..
####
.#..

và lập luận tách miền giống trường hợp \(X=4\).

Với mọi bộ \((X,S,L)\) khác, Gabriel thắng. Editorial chứng minh chi tiết trường hợp khó nhất \(X=6\) và để các \(X\) nhỏ hơn làm bài tập. Số hình tương ứng với \(X=1,2,3,4,5,6\) là \(1,1,2,5,12,35\).

Lưới cơ sở nhỏ nhất cho \(X=6\), \(S>3\) và diện tích chia hết cho 6 là \(4\times6\). Dưới đây là phân tích đủ cả 35 lựa chọn: # là hình Richard bắt buộc, còn a, b, c là các 6-omino Gabriel thêm vào.

######   a#####   a#####   a#####   ####cc   ##abbb   ##abbb
aaaaaa   aaaaa#   aaaa#c   abb#cc   aab##c   ##abbb   #aabbb
bbbbbb   bbbbbb   abbbbc   aabbcc   aabbcc   #aaccc   ##accc
cccccc   cccccc   bbcccc   aabbcc   aabbbc   #aaccc   #aaccc

##abbb   #aabbb   ###bbb   #aaaaa   #aaaaa   aaa#bb   aa#bbb
#aabbb   ##abbb   #aabbb   ###cca   ####ca   a####b   a####b
#aaccc   ##accc   #aaccc   #ccccb   #ccccc   aacc#b   aaac#b
##accc   #aaccc   #aaccc   #bbbbb   bbbbbb   ccccbb   cccccb

a#bbbb   aa#bbb   aa#bbb   a###bb   ###bbb   ###bbb   ###bbb
a####b   a####b   a####b   aaa##b   #a##bb   aa###b   a###bb
aacc#b   aaa#bb   aa#ccb   acc#bb   aaaccb   aacccb   aaaccb
aacccc   cccccc   accccb   accccb   aacccc   aacccb   aacccc

###aaa   aaa#bb   aaa###   aa#bbb   ###bbb   ###bbb   aaaaaa
###aaa   a###bb   aaab##   a###bb   aa#bbb   aa##bb   ###bbb
cccbbb   aac##b   bbbb#c   aaa##b   aa##cc   aaa#cb   #c#bbb
cccbbb   cccccb   bccccc   cccccc   aacccc   accccc   #ccccc

aaaaab   aabbbb   ##bbbb   aaaaaa   aaaaab   aaaabb   ##aaaa
#a#cbb   a#b#bc   a###bb   #bbbbc   a#bbbb   aa#cbb   c##aab
###cbb   a###cc   aaa#cc   ##bbcc   ###ccb   ###cbb   cc##bb
#ccccb   aa#ccc   aacccc   ###ccc   ##cccc   ##cccc   cccbbb

Như vậy Gabriel luôn thắng trên \(4\times6\) với bất kỳ 6-omino nào.

Với bảng lớn hơn, chẳng hạn \(6\times8\), Gabriel đặt hình Richard ở góc trên trái và hoàn tất một vùng \(4\times6\) như trên. Phần còn lại được đi bằng một đường Hamilton kiểu rắn; Z là vùng \(4\times6\), còn a đến x là thứ tự đường đi:

ZZZZZZba
ZZZZZZcd
ZZZZZZfe
ZZZZZZgh
ponmlkji
qrstuvwx

Các ô a–x tạo thành một chuỗi liên thông, chỉ cần chặt chuỗi thành từng đoạn 6 ô, mỗi đoạn là một 6-omino. Tổng quát, nếu vùng Z cao \(T\) hàng, bắt đầu đường rắn ở góc trên phải khi \(T\) chẵn, hoặc ở ô kề góc trên phải của vùng Z khi \(T\) lẻ. Vì thế Gabriel thắng cho mọi bảng lớn hơn trường hợp cơ sở. Các \(X\) khác được liệt kê và chứng minh tương tự.

Cài đặt

def richard_wins(X, R, C):
  S = min(R, C)
  L = max(R, C)
  if (S * L) % X != 0: return True
  if X == 3 and S == 1: return True
  if X == 4 and S <= 2: return True
  if X == 5 and (S <= 2 or (S, L) == (3, 5)): return True
  if X == 6 and S <= 3: return True
  if X >= 7: return True
  return False

for tc in range(input()):
  X, R, C = map(int, raw_input().split())
  print "Case #%d: %s" % (tc + 1,
    "RICHARD" if richard_wins(X, R, C) else "GABRIEL")

Phân tích đóng chạy trong \(O(1)\) mỗi test.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2015 - Qualification Round - Ominous Omino, kho Google Coding Competitions (Apache-2.0).