Đầu năm nay, đội Code Jam trồng một vườn cây với sự giúp đỡ của một chú chuột túi má cần mẫn. Hẳn nó đã kể cho đồng loại, vì giờ trong vườn có từ \(2\) đến \(25\) chú. Rất khó biết chính xác có bao nhiêu: chúng chỉ chui khỏi hang ngầm để ăn vào ban đêm, còn sau một ngày tỉa cây vất vả chúng tôi quá mệt để thức quan sát. Tuy nhiên, mỗi ngày chúng tôi làm được đúng một “món ăn cho chuột”, để ngoài trời ban đêm rồi sáng hôm sau xem có bị ăn hay không. Chúng tôi nghĩ có thể dùng thông tin này để xác định số chuột.

Đây là những gì đã biết về cách chúng ăn. Ban ngày, \(N\) chú chuột họp hội đồng để quyết định thứ tự xuất hiện trong \(N\) đêm tiếp theo, mỗi đêm một chú. Đêm thứ \(i\), chú thứ \(i\) trong thứ tự chui lên và tìm món ăn. Mỗi chú có một ngưỡng khẩu vị riêng, không bao giờ thay đổi; nó ăn khi và chỉ khi chất lượng món ăn ít nhất bằng ngưỡng của nó. Ban ngày sau khi chú thứ \(N\) xuất hiện, hội đồng chọn thứ tự mới và quá trình tiếp tục. Dù một chú không ăn món nó tìm thấy, nó vẫn không xuất hiện lại cho đến lượt của mình trong thứ tự kế tiếp.

Mỗi ngày phải làm đúng một món mới. Món không bị ăn cũng hỏng và không thể dùng lại đêm sau. Mỗi sáng, bạn biết món của đêm trước có bị lấy hay không.

Hôm nay, bạn biết chúng đang họp để chọn thứ tự kế tiếp, nên tối nay là đầu một thứ tự mới. Bạn sẵn lòng dành rất nhiều thời gian cho cuộc điều tra — tới \(10^5\) đêm. Dùng không quá \(S\) món, hãy xác định số chuột.

Dữ liệu vào

Đây là bài tương tác, nên khái niệm dữ liệu vào và dữ liệu ra khác các bài Code Jam thông thường. Chương trình tương tác với một tiến trình riêng vừa cung cấp thông tin vừa đánh giá phản hồi. Mọi thông tin đi vào chương trình qua đầu vào chuẩn; mọi điều cần truyền cho bộ chấm phải gửi qua đầu ra chuẩn.

Ban đầu, chương trình đọc một dòng chứa số nguyên \(T\). Ở đầu mỗi bộ test, đọc một dòng chứa số nguyên \(S\), số món tối đa có thể dùng.

Dữ liệu ra

Chương trình gửi từng truy vấn chất lượng món ăn hoặc câu trả lời cuối cùng qua đầu ra chuẩn theo giao thức bên dưới. Nhiều ngôn ngữ mặc định lưu đầu ra trong bộ đệm, nên phải bảo đảm dữ liệu thật sự được gửi — chẳng hạn bằng cách flush — trước khi chặn để chờ phản hồi. FAQ về bài tương tác của Code Jam giải thích chi tiết thao tác flush. Dữ liệu gửi qua lỗi chuẩn bị bỏ qua, nhưng vẫn có thể tiêu thụ bộ nhớ.

Để hỗ trợ gỡ lỗi, cuối đề chính thức có một công cụ kiểm thử cục bộ viết bằng Python. Phần phân tích bài tương tác Number Guessing của Code Jam trước đó cũng cung cấp lời giải mẫu bằng mọi ngôn ngữ được hỗ trợ.

Giao thức tương tác

Với mỗi bộ test, chương trình thực hiện nhiều nhất \(S+1\) lượt trao đổi; lượt cuối bắt buộc là một lần đoán đáp án. Ở lượt thứ \(i\), in một dòng chứa số nguyên \(Q_i\):

• Nếu \(1\le Q_i\le10^6\), bạn để ra một món chất lượng \(Q_i\). Bộ chấm trả một dòng chứa 1 nếu chuột ăn, hoặc 0 nếu không. Chương trình phải đọc phản hồi rồi mới tiếp tục.
• Nếu \(-25\le Q_i\le-2\), câu trả lời của bạn là có \(-Q_i\) chú chuột. Nếu đúng, bộ chấm chuyển sang bộ test tiếp theo, nếu còn.

Bộ chấm in -1 trên một dòng rồi ngừng gửi dữ liệu nếu xảy ra bất kỳ điều nào sau đây:

1. Chương trình gửi giá trị sai định dạng, vượt biên — chẳng hạn 1000001, -1, GO_IS_THE_BEST_LANGUAGE — hoặc gửi quá nhiều giá trị trên một dòng, chẳng hạn 1 2.
2. Sau khi đã gửi \(S\) chất lượng món cho bộ test hiện tại, chương trình lại gửi giá trị ngoài đoạn \([-25,-2]\).
3. Chương trình gửi một giá trị trong \([-25,-2]\) nhưng đoán sai. Mỗi bộ test chỉ được đoán một lần.

Sau khi nhận -1, chương trình phải thoát ngay; nếu tiếp tục chờ bộ chấm, nó sẽ bị Time Limit Exceeded thay vì nhận đúng phán quyết như Wrong Answer hay Runtime Error. Chương trình cũng không được gửi thêm bất kỳ thông tin nào sau khi giải xong tất cả bộ test; tiếp tục in sau câu trả lời của test cuối sẽ bị Wrong Answer.

Để tham khảo hiệu năng, nhóm tác giả chạy \(S=10^5\) lượt, chia thành các lô kích thước \(B\): in \(B\) chất lượng, đọc \(B\) phản hồi, rồi lặp lại \(S/B\) lần. Cả Python và C++ đều ghép \(B\) chất lượng vào một biến chuỗi rồi mới in, bảo đảm bộ đệm không bị flush giữa lô. Bảng dưới là số giây, làm tròn lên nửa giây kế tiếp và lấy trường hợp xấu nhất qua nhiều lần chạy:

Với kích thước lô tương đối nhỏ, thời gian chuyển ngữ cảnh giảm xuống dưới \(5\) giây mỗi test, tức dưới một phút cho cả Test Set.

Ràng buộc

• \(1\le T\le10\).
• Số chuột nằm trong \([2,25]\).
• Ngưỡng khẩu vị của mỗi chú nằm trong \([1,10^6]\).
• \(S=10^5\).
• Với mỗi bộ test, đa tập ngưỡng khẩu vị và hạt giống sinh số ngẫu nhiên được ban tổ chức tạo trước cuộc thi, giống nhau cho mọi thí sinh và mọi lần nộp. Vì thế hai bài nộp cung cấp cùng số món \(s_i\) cho test \(i\) sẽ thấy cùng thứ tự xuất hiện.

Phân nhóm

Test Set 1 (Visible): Không có hai chú chuột cùng ngưỡng khẩu vị. Mỗi thứ tự xuất hiện được chọn đều ngẫu nhiên trong mọi hoán vị và độc lập với mọi thứ tự khác.

Test Set 2 (Hidden):

Thứ tự chuột xuất hiện độc lập với các món được đưa ra.

Ví dụ, hai chú có ngưỡng lần lượt \(1\) và \(2\) có thể xuất hiện ở cả hai Test Set. Ba chú với ngưỡng \(1,1,2\) có thể xuất hiện ở Test Set 2 nhưng không ở Test Set 1. Sáu chú với ngưỡng \(1,1,1,1,2,2\) không thể xuất hiện ở Test Set 2 vì các bội số là \(4\) và \(2\), có gcd bằng \(2\); cũng không thể ở Test Set 1 vì có ngưỡng trùng. Hai chú cùng ngưỡng \(7\) cũng không thể xuất hiện ở bất kỳ Test Set nào.

Ví dụ

  // In this example, the problem setters have already determined that the first
  // test case has two gophers with taste levels 1 and 2 (we will call them A
  // and B, respectively), and that the second test case has four gophers with
  // taste levels 1, 999, 123, and 4567 (we will call them C, D, E, and F,
  // respectively).
  // The judge randomly generates the first order: A, B.
  t = readline_int()           // Code reads 2 into t.
  s = readline_int()           // Code reads 100000 into s.
  printline 1 to stdout        // Code sends a snack with quality level 1.
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher A ate the
                               //   snack).
  printline 1 to stdout
  flush stdout
  resp = readline_srt()        // Code reads 0 into resp (gopher B did not eat
                               //   the snack).
                               // Judge randomly generates B, A as the next
                               //   order.
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher B ate the
                               //   snack).
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher A ate the
                               //   snack).
                               // Judge randomly generates B, A as the next
                               //   order.
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher B ate the
                               //   snack).
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher A ate the
                               //   snack).
  printline -2 to stdout       // Code correctly determines that the only
  flush stdout                 //   scenario consistent with the information
                               //   given so far is two gophers with taste
                               //   levels 1 and 2.
                               // Judge rules that the answer is correct, and
                               //   prepares the next test case...
                               // Judge randomly generates C, E, F, D as the
                               //   first order.
  s = readline_int()           // Code reads 100000 into s. (This also shows
                               //   that the answer to the first test case was
                               //   correct.)
  printline 0 to stdout        // Code sends an invalid value.
  flush stdout
  resp = readline_str()        // Code reads -1 into resp.
  exit                         // Code exits to avoid an ambiguous TLE error.

  // In this example, the problem setters have already determined that the first
  // test case has three gophers with taste levels 1, 2, and 1; we will call
  // them A, B, and C, respectively, and they will be ordered ABCCBAABCCBA...
  t = readline_int()           // Code reads 1 into t.
  s = readline_int()           // Code reads 100000 into s.
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher A ate
                               //   the snack).
  printline 1 to stdout
  flush stdout
  resp = readline_srt()        // Code reads 0 into resp (gopher B did not eat
                               //   the snack).
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher C ate the
                               //   snack).
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher C ate the
                               //   snack).
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher B ate the
                               //   snack).
  printline -2 to stdout       // Code erroneously decides that there
                               //   are two gophers A and B with taste levels
                               //   1 and 2; this is consistent with the
                               //   information given so far for the order
                               //   A,B,A,B,A, but the true number of gophers
  flush stdout                 //   is different, so judge rules it is wrong.
  s = readline_str()           // Code tries to read s but gets -1, meaning
                               //   that the answer to the last test case was
                               //   wrong.
  exit                         // Code exits to avoid an ambiguous TLE error.

Công cụ kiểm thử

Có thể dùng công cụ kiểm thử đi kèm để chạy cục bộ hoặc trên nền tảng. Khi chạy cục bộ, cần chạy công cụ song song với chương trình, chẳng hạn qua interactive runner chính thức của Code Jam, và làm theo hướng dẫn trong các chú thích của tệp runner cũng như mục Interactive Problems trong FAQ.

Hướng dẫn dùng công cụ nằm trong chú thích của chính công cụ. Nhóm tác giả khuyến khích bổ sung test riêng. Công cụ chỉ mô phỏng hệ thống chấm, không phải hệ thống chấm thật và có thể hành xử khác. Nếu chương trình qua công cụ nhưng trượt hệ thống thật, cần kiểm tra rằng đang dùng cùng trình biên dịch với hệ thống Code Jam.

Tệp công cụ cục bộ chính thức là local_testing_tool.py trong gói bài toán.

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài Go, Gophers!.

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

Thành phố Gridtopia là một ma trận các ô vuông, hay “khu phố”, gồm \(R\) hàng và \(C\) cột. Hàng được đánh số từ trên xuống dưới, cột từ trái sang phải, đều bắt đầu từ \(1\). Thành phố có \(S\) đồn cảnh sát. Đồn thứ \(i\) nằm ở hàng \(R_i\), cột \(C_i\), và không ô nào chứa quá một đồn.

Mỗi đồn chỉ có thể tuần tra các ô cách nó không quá \(D_i\) ô theo cả chiều ngang lẫn chiều dọc. Nói chính xác, đồn \(i\) chỉ tuần tra được ô ở hàng \(R'\), cột \(C'\) nếu

Tương đương, đồn \(i\) chỉ tuần tra được các ô trong hình vuông cạnh \(2D_i+1\) có tâm tại đồn ấy.

Là cảnh sát trưởng mới, bạn cần phân công một số ô trong thành phố cho đúng một đồn có khả năng tuần tra chúng. Không phân công ô chứa đồn và ô không có đồn nào tuần tra được; mọi ô khác bắt buộc phải được phân công. Đồng thời, cần chia tải đều nhất có thể. Gọi \(A_i\) là số ô được giao cho đồn \(i\); mục tiêu là tối thiểu hóa hiệu giữa giá trị lớn nhất và nhỏ nhất trong các \(A_i\). Với cách phân công tối ưu, hiệu nhỏ nhất là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng ba số nguyên \(R,C,S\): số hàng, số cột và số đồn. Tiếp theo là \(S\) dòng; dòng thứ \(i\) chứa \(R_i,C_i,D_i\): vị trí đồn thứ \(i\) và tham số phạm vi tuần tra như trên.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\), và y là hiệu nhỏ nhất cần tìm.

Ràng buộc

• \(1\le T\le100\).
• \(2\le S\le15\).
• \(1\le R_i\le R\) và \(1\le C_i\le C\) với mọi \(i\).
• Với mọi \(i\ne j\), \(R_i\ne R_j\) hoặc \(C_i\ne C_j\); không hai đồn nào cùng ô.
• \(1\le D_i<\max(R,C)\) với mọi \(i\).

Phân nhóm

Test Set 1 (Visible): \(1\le R,C\le20\).

Test Set 2 (Hidden): \(1\le R,C\le10^9\).

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

Case #1: 4
Case #2: 0

@@@@.
!!!@.
!2!@.
1!!@.
!@!@.

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài Jurisdiction Restrictions.

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ạn là một kiếm sĩ quyết đấu, khao khát trở thành Kiếm Sư tiếp theo. Để đạt danh hiệu này, bạn sẽ đấu với các đối thủ cho đến khi thắng tất cả họ. Mọi đối thủ luôn sẵn sàng quyết đấu và họ không đấu với nhau.

Mỗi kiếm sĩ, kể cả bạn, biết ít nhất một đòn tấn công và một thế phòng thủ. Trên thế giới có tối đa \(P\) cặp tấn công–phòng thủ; thế thủ thứ \(i\) chỉ hóa giải đòn công thứ \(i\), và đòn công thứ \(i\) cũng chỉ bị thế thủ thứ \(i\) hóa giải. Có thể tồn tại đòn công hoặc thế thủ không ai biết. Một kỹ năng đã biết có thể dùng bao nhiêu lần tùy ý, không bị “tiêu hao”.

Mỗi trận quyết đấu tuân theo các quy tắc:

• Là ứng viên Kiếm Sư, bạn luôn tấn công trước. Bạn chọn một đòn công mình biết. Nếu đối thủ biết thế thủ tương ứng, họ có thể chọn dùng nó; nếu không biết hoặc chọn không dùng, họ không phòng thủ.
• Sau đó đối thủ chọn một đòn công họ biết. Nếu bạn biết thế thủ tương ứng, bạn có thể chọn dùng; nếu không biết hoặc chọn không dùng, bạn không phòng thủ.
• Nếu bạn phòng thủ thành công còn đối thủ không phòng thủ, bạn thắng trận. Trong mọi trường hợp khác bạn không thắng, nhưng hành trình trở thành Kiếm Sư vẫn có thể tiếp tục.

Bạn có thể đấu bao nhiêu trận tùy ý, kể cả đấu nhiều lần với cùng một người, bất kể kết quả trước đó. Không cần lập sẵn toàn bộ lịch; quyết định tiếp theo có thể dựa trên những gì đã xảy ra. Khi đã thắng mỗi đối thủ ít nhất một lần, bạn trở thành Kiếm Sư.

Bạn học cực nhanh. Sau mỗi trận, bất kể kết quả, bạn thêm vào bộ kỹ năng của mình đòn công và thế thủ, nếu có, mà đối thủ đã dùng. Nếu đối thủ dùng một thế thủ lạ chống lại bạn, bạn chỉ học nó sau trận, nên không thể dùng nó để chống đòn công của đối thủ ngay trong cùng trận. Chỉ bạn có lợi thế học hỏi này; kỹ năng của đối thủ không bao giờ thay đổi.

Hơn nữa, sau khi bạn thắng một đối thủ và trước trận tiếp theo, người đó sẽ dạy bạn toàn bộ đòn công và thế thủ họ biết mà bạn chưa biết. Một khi đã thua bạn, họ sẽ trông đỡ tệ hơn nếu cuối cùng bạn thật sự trở thành Kiếm Sư.

Bạn biết trước mọi đòn công và thế thủ của từng đối thủ. Nếu lựa chọn tối ưu, liệu bạn có thể bảo đảm trở thành Kiếm Sư, bất kể các đối thủ lựa chọn thế nào hay không?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test có cấu trúc:

• Dòng đầu chứa \(N,P\): số kiếm sĩ, kể cả bạn, và số cặp tấn công–phòng thủ tối đa.
• Tiếp theo là \(N\) nhóm, mỗi nhóm ba dòng, mô tả một kiếm sĩ; nhóm đầu tiên mô tả bạn:
  1. Một dòng chứa \(Attacks_i,Defenses_i\), số đòn công và số thế thủ kiếm sĩ \(i\) biết.
  2. Một dòng chứa \(Attacks_i\) số nguyên phân biệt \(A_{ij}\) theo thứ tự tăng dần, là chỉ số các đòn công họ biết.
  3. Một dòng chứa \(Defenses_i\) số nguyên phân biệt \(D_{ij}\) theo thứ tự tăng dần, là chỉ số các thế thủ họ biết.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\), và y là YES nếu có thể bảo đảm trở thành Kiếm Sư, hoặc NO nếu không.

Ràng buộc

• \(1\le T\le100\).
• \(2\le N\le1000\).
• \(1\le P\le1000\).
• \(1\le Attacks_i,Defenses_i\le P\) với mọi \(i\).
• \(1\le A_{ij}<A_{i,j+1}\le P\) với mọi chỉ số hợp lệ.
• \(1\le D_{ij}<D_{i,j+1}\le P\) với mọi chỉ số hợp lệ.
• Tổng mọi \(Attacks_i\) cộng tổng mọi \(Defenses_i\) không vượt \(50000\).

Phân nhóm

Test Set 1 (Visible): \(A_{i1}=1\) và \(D_{i1}=1\) với mọi \(i\); mọi kiếm sĩ, kể cả bạn, đều biết đòn công \(1\) và thế thủ \(1\).

Test Set 2 (Hidden): Không có ràng buộc bổ sung.

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

5
2 2
1 2
1
1 2
2 1
1 2
1
2 2
1 1
1
2
1 1
2
1
2 5
1 1
2
3
2 1
2 4
2
3 5
3 2
1 2 3
3 4
2 4
3 4
2 3 4 5
2 5
4 5
1 2 3 4 5
4 4
1 1
1
4
2 3
2 3
2 3 4
1 3
4
1 2 4
1 3
4
1 3 4

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

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài Swordmaster.

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

The Cartesian Job

Có lẽ bạn đã nghe nói về khối trụ bạch kim–iridi dùng làm chuẩn kilôgam, nhưng bạn có biết còn có một đoạn thẳng đặc biệt dùng làm chuẩn kilômét không? Trong một địa điểm bí mật và rất bằng phẳng, đoạn thẳng ấy nằm trên mặt phẳng hai chiều, nối \((0,0)\) với \((0,1000)\).

Đương nhiên đoạn chuẩn này vô cùng quý giá, nên nó được bảo vệ bởi \(N\) laser giám sát quay, mỗi laser là một tia trên mặt phẳng. Mỗi laser có một đầu mút cố định và quay quanh đầu mút đó với tốc độ không đổi đúng một vòng mỗi giây. Hệ thống an ninh chọn chiều quay thuận hay ngược chiều kim đồng hồ của từng laser một cách độc lập và đồng xác suất.

Các laser không bị cản bởi laser khác, bởi đầu mút của chúng hay bởi chính đoạn chuẩn. Không laser nào có đầu mút nằm trên đoạn chuẩn.

Bạn được thuê để kiểm định hệ thống an ninh, nhưng dữ liệu duy nhất là một ảnh chụp tại một thời điểm, cho biết đầu mút và hướng của từng laser lúc ấy. Vì chỉ là ảnh tĩnh, bạn không thể suy ra chiều quay của bất kỳ laser nào.

Bạn xác định rằng đoạn chuẩn có thể bị đánh cắp nếu từng tồn tại một khoảng thời gian mở, khác rỗng mà không laser nào chạm vào đoạn. Xác suất để điều đó xảy ra là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số lượng test \(T\). Mỗi test bắt đầu bằng một dòng chứa số nguyên \(N\), là số laser. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa bốn số nguyên \(X_i,Y_i,X'_i,Y'_i\), lần lượt là tọa độ đầu mút của tia laser thứ \(i\) và tọa độ của một điểm khác nằm trên tia đó.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test (bắt đầu từ 1), còn y là xác suất cần tìm. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(-10^6\le X_i,Y_i,X'_i,Y'_i\le10^6\) với mọi \(i\).
• \((X_i,Y_i)\ne(X'_i,Y'_i)\) với mọi \(i\).
• Nếu \(X_i=0\) thì \(Y_i<0\) hoặc \(Y_i>1000\); tức là không đầu mút laser nào nằm trên đoạn chuẩn.

Phân nhóm

• Test Set 1 (hiển thị): \(1\le N\le10\).
• Test Set 2 (ẩn): \(1\le N\le10000\); có nhiều nhất 8 test với \(N>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
5
0 1001 -1 1001
0 1001 -1 1001
0 1001 -2 1001
0 1001 0 500
0 1002 1234 5678
4
500 500 1000 1000
500 500 0 1000
500 500 0 0
500 500 1000 0
4
500 500 1000 1001
500 500 0 1000
500 500 0 0
500 500 1000 0

Case #1: 1.000000
Case #2: 0.750000
Case #3: 1.000000

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài The Cartesian Job.

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

Two-Tiling

Công ty trò chơi của bạn vừa đặt mua rất nhiều bảng vuông gồm 64 ô đơn vị trống để làm bàn cờ vua, nhưng sếp đột nhiên tuyên bố cờ vua đã lỗi thời. Để tận dụng số bảng này, bạn thiết kế một câu đố mới dùng các tile.

Một tile là một tập ô đơn vị liên thông cạnh và có thể đặt vừa trong một hình vuông \(3\times3\). Ví dụ, dưới đây là bốn tile hợp lệ (@ là ô thuộc tile, . chỉ là phần đệm):

...  @@@  @@@  .@@
...  @@@  @.@  @.@
.@.  @@@  @..  @@@

Các hình sau không phải tile hợp lệ: hình đầu không liên thông cạnh, hình thứ hai không nằm vừa trong \(3\times3\), và hình thứ ba cũng không liên thông cạnh.

@@.  @.@  .@@.
...  .@.  @@@@
.@@  @.@  .@@.

Khi đặt một tile, các ô của nó phải trùng khít với những ô bảng chưa bị tile khác phủ. Sau mọi phép tịnh tiến, quay theo bội của \(90^\circ\) và/hoặc phản xạ, tile vẫn được coi là cùng một loại; người giải được phép dùng mọi phép biến đổi ấy. Chẳng hạn, ba hình sau chỉ là các biến thể của cùng một tile:

.@.  ..@  @..
...  @@.  @@.
.@@  @@.  .@@
@@.  .@@  @..
.@.  .@.  @@.

Để tạo câu đố, bạn sẽ tô đỏ một hay nhiều ô bảng. Người chơi phải đặt tile sao cho phủ tất cả và chỉ các ô đỏ. Để tiết kiệm chi phí sản xuất, họ chỉ nhận một loại tile, nhưng nhận vừa đủ số bản sao để phủ toàn bộ ô đỏ.

Bạn phải quyết định tô đỏ những ô nào. Tuy nhiên, sếp vẫn đang chọn giữa hai loại tile. Không muốn chờ nữa, bạn quyết định tìm một tập ô sao cho câu đố giải được bất kể cuối cùng dùng loại tile nào.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test gồm bốn dòng. Mỗi trong ba dòng đầu có ba ký tự, một dấu cách, rồi ba ký tự nữa; dòng thứ tư để trống.

Trong toàn bộ test, dấu cách ngăn lưới \(3\times3\) bên trái với lưới \(3\times3\) bên phải; mỗi lưới là khung hiển thị một tile. Ký tự @ chỉ ô thuộc tile, còn . chỉ là phần đệm để hình dạng rõ ràng và không liên quan đến bảng hay câu đố. Hai tile được bảo đảm khác nhau ngay cả khi cho phép mọi phép biến đổi nêu trên.

Dữ liệu ra

Với mỗi test, trước hết in Case #x: y, trong đó x là số thứ tự test và y là POSSIBLE nếu tồn tại lời giải, ngược lại là IMPOSSIBLE.

Nếu có lời giải, in thêm tám dòng, mỗi dòng đúng 17 ký tự, tạo thành hai lưới \(8\times8\) cách nhau bởi một cột dấu cách. Trong mỗi lưới, dùng . cho ô trống, và dùng các ký tự trong tập 64 ký tự sau để định danh từng tile:

!?0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

Trong cùng một lưới, mọi lần xuất hiện của một ký tự khác . phải thuộc đúng một tile; hai ký tự khác nhau phải biểu diễn hai tile khác nhau. Mỗi tile ở lưới trái phải tương đương, qua quay/tịnh tiến/phản xạ, với tile trái của input; quy tắc tương tự áp dụng cho lưới phải. Tập vị trí khác . của hai lưới phải giống hệt nhau và khác rỗng. Nếu có nhiều lời giải, có thể in bất kỳ lời giải nào.

Ràng buộc

• Mỗi tile đầu vào là một nhóm ô liên thông cạnh.
• Hai tile đầu vào không cùng loại theo định nghĩa trên.

Phân nhóm

• Chỉ có Test Set 1 (hiển thị): \(T=595\). Mọi test có thể có, tính đến đẳng cấu, đều xuất hiện.

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

4
.@@ .@.
.@. .@.
.@@ @@.

@@@ @@@
@.@ @@@
@@@ @@@

.@. ...
@@. .@@
@.. ...

... ..@
... ..@
@.. ...

Case #1: POSSIBLE
....11.. ....11..
...221.. ...221..
...211.. ...321..
...22... ...32...
.333.... .433....
4343.... 5444....
444..... 555.....
........ ........
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
........ ........
..T..I.. ..T..I..
.TT..II. .tT..Ii.
.T....I. .t....i.
........ ........
.LL..EE. .LL..EE.
..LLEE.. ..llee..
........ ........
Case #4: POSSIBLE
the.CODE AAB.CDDE
Jam.2018 FFB.CGGE
........ ........
World... HHIIJ...
.FiNALS. .KLLJMM.
.cup.... .KNN....
........ ........
TRIUMPH! OOPPQQRR

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài Two-Tiling.

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