Google Code Jam 2018 - Round 2

Supervin là một biên đạo múa nổi tiếng. Hôm nay là kỷ niệm năm thứ \(N\) trong sự nghiệp biên đạo của anh. Để ăn mừng, anh lên kế hoạch cho một điệu múa trên sân khấu là lưới vuông \(N\times N\), mỗi ô có đúng một vũ công.

Mỗi vũ công mặc một bộ trang phục có đúng một màu và làm bằng len hoặc cotton. Supervin có \(N\) màu, được đánh số từ 1 đến \(N\).

Mỗi vũ công muốn cảm thấy mình đặc biệt. Nếu có ít nhất hai vũ công cùng hàng hoặc cùng cột, đồng thời mặc trang phục cùng màu và cùng chất liệu, họ sẽ không còn cảm thấy đặc biệt.

Supervin muốn tất cả vũ công đều đặc biệt. Anh sẵn sàng đổi màu và/hoặc chất liệu của một số trang phục sao cho không vũ công nào chung hàng hoặc cột với một người có cùng kiểu trang phục. Cần đổi trang phục của ít nhất bao nhiêu vũ công? Đổi cả màu lẫn chất liệu của một bộ vẫn chỉ tính là một lần đổi.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi bộ test bắt đầu bằng \(N\), độ dài cạnh sân khấu tính theo số ô. Tiếp theo là \(N\) dòng, mỗi dòng chứa \(N\) số nguyên khác 0 \(A_{i,j}\). Giá trị thứ \(j\) trên dòng thứ \(i\) biểu diễn trang phục tại hàng \(i\), cột \(j\): trị tuyệt đối là màu, dấu âm là len và dấu dương là cotton.

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à số vũ công ít nhất phải đổi trang phục.

Ràng buộc

• \(1\le T\le100\).
• \(-N\le A_{i,j}\le N\) với mọi \(i,j\).
• \(A_{i,j}\ne0\) với mọi \(i,j\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2\le N\le4\).
• Test Set 2 (Ẩn): \(2\le N\le100\).

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

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

  1 -2
  2 1

  1 2
  2 1

  2 -2
  -2 2

Nguồn

Google Code Jam 2018, Vòng 2, bài Costume Change.

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 món đồ chơi gồm một lưới có ít nhất 2 cột và ít nhất 1 hàng. Mỗi ô chứa dốc \, dốc /, hoặc để trống. Cột ngoài cùng bên trái, cột ngoài cùng bên phải và hàng cuối đều phải trống. Để bi không mắc kẹt, một ô chứa dốc \ không bao giờ nằm ngay bên trái một ô chứa dốc /.

Khi thả một viên bi vào hàng trên cùng, nó di chuyển tất định:

• Trong ô trống, bi đi xuống ô ngay dưới; nếu đang ở hàng cuối thì dừng.
• Trong ô có dốc \, bi đi xuống dưới và sang phải một ô.
• Trong ô có dốc /, bi đi xuống dưới và sang trái một ô.

Để quan sát toàn bộ cơ chế, người dùng thả đúng một viên vào mỗi cột. Các viên không ảnh hưởng nhau và một ô có thể chứa nhiều viên.

Bạn của bạn có món đồ chơi gồm \(C\) cột và số hàng chưa biết. Họ vừa thả mỗi cột trên cùng một viên, chờ tất cả dừng, rồi đếm số bi ở từng ô của hàng cuối và đưa kết quả cho bạn. Nhưng bạn nghi rằng họ có thể đã đếm sai. Hãy tạo một bố cục phù hợp với kết quả và dùng ít hàng nhất có thể, hoặc xác định rằng không có bố cục nào.

Ví dụ, nếu kết quả là 3 0 0 2 0 1, một lời giải có thể là:

.//\..
./\./.
......

Không bắt buộc dùng số dốc ít nhất, và cũng không bắt buộc mọi dốc đều tác động đến bi.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi bộ test bắt đầu bằng \(C\), số cột của đồ chơi. Dòng tiếp theo chứa \(C\) số nguyên \(B_i\); số thứ \(i\) là số bi mà bạn của bạn báo đã dừng ở ô thứ \(i\) từ trái sang trên hàng cuối.

Dữ liệu ra

Với mỗi bộ test, trước hết in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là IMPOSSIBLE hoặc số hàng của bố cục.

Nếu \(y\) không phải IMPOSSIBLE, in tiếp \(y\) dòng theo thứ tự từ trên xuống dưới. Dùng . cho ô trống, \ và / cho hai loại dốc. Bố cục phải tuân thủ mọi quy tắc trong đề.

Ràng buộc

• \(1\le T\le100\).
• \(0\le B_i\le C\) với mọi \(i\).
• \(\sum_{i=1}^{C}B_i=C\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2\le C\le5\).
• Test Set 2 (Ẩn): \(2\le C\le100\).

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

Case #1: 1
....
Case #2: IMPOSSIBLE
Case #3: 3
.//\..
./\./.
......

\\..\/
../.\/
./../.
..../.

Nguồn

Google Code Jam 2018, Vòng 2, bài Falling Balls.

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à quản lý của đoàn biểu diễn Graceful Chainsaw Jugglers và đang cố gắng thành công trong ngành tung hứng cưa máy đầy cạnh tranh. Bạn có vô hạn nghệ sĩ tài năng giống hệt nhau; mỗi người đều biết tung hứng với số lượng cưa máy bất kỳ. Để tổ chức một buổi diễn, bạn sẽ chọn một số nghệ sĩ rồi phân phát những chiếc cưa máy đỏ và xanh cho họ sao cho mỗi nghệ sĩ nhận ít nhất một chiếc. Chẳng hạn, một người có thể tung hứng hai cưa đỏ và ba cưa xanh, còn người khác chỉ tung hứng một cưa đỏ. Trong suốt buổi diễn, mỗi chiếc cưa chỉ do một nghệ sĩ sử dụng; các nghệ sĩ không chuyền cưa cho nhau, bởi chỉ riêng việc tung hứng chúng đã đủ khó rồi!

Theo nghiên cứu thị trường của bạn, khán giả vui nhất khi buổi diễn sử dụng càng nhiều nghệ sĩ và cưa máy càng tốt, nhưng họ cũng đòi hỏi sự đa dạng: không được có hai nghệ sĩ vừa dùng cùng số cưa đỏ và cùng số cưa xanh.

Bạn có \(R\) cưa đỏ và \(B\) cưa xanh, và phải dùng hết tất cả trong buổi diễn. Số nghệ sĩ lớn nhất bạn có thể sử dụng mà vẫn đáp ứng yêu cầu của khán giả là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\); sau đó là \(T\) bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên \(R\) và \(B\): lần lượt là số cưa đỏ và cưa xanh mà bạn phải sử dụng trong buổi diễn.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số nghệ sĩ lớn nhất có thể dùng trong buổi diễn mà vẫn đáp ứng các yêu cầu nêu trên.

Ràng buộc

• \(1 \le T \le 100\).
• \(R + B > 0\).

Phân nhóm

Test Set 1 (Hiển thị):

• \(0 \le R \le 50\).
• \(0 \le B \le 50\).

Test Set 2 (Ẩn):

• \(0 \le R \le 500\).
• \(0 \le B \le 500\).

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

Case #1: 1
Case #2: 5

Nguồn

Google Code Jam 2018, Vòng 2, bài Graceful Chainsaw Jugglers.

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

Siêu trộm Jom Codd có khả năng thâm nhập vào giấc mơ của người khác. Vì công nghệ quan sát giấc mơ vẫn chưa tốt lắm, Codd nhìn thấy một giấc mơ dưới dạng một lưới giấc mơ gồm các ô đơn vị, mỗi ô có màu trắng hoặc đen.

Từ một lưới giấc mơ ban đầu, Codd có thể đi sâu hơn bằng cách thay mỗi ô trắng bằng một lưới \(2\times2\) toàn ô trắng và mỗi ô đen bằng một lưới \(2\times2\) toàn ô đen; thao tác này tạo ra một lưới giấc mơ lớn gấp bốn lần. Anh có thể tiếp tục đi sâu hơn từ lưới mới ấy, rồi lặp lại như vậy. Chẳng hạn, với lưới giấc mơ ban đầu:

BBB
BWB
BBB

đi sâu hơn một lần tạo ra lưới mới:

BBBBBB
BBBBBB
BBWWBB
BBWWBB
BBBBBB
BBBBBB

và đi sâu hơn một lần nữa tạo ra:

BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB

và cứ tiếp tục như vậy.

Codd vừa thâm nhập vào một giấc mơ và quan sát lưới giấc mơ ban đầu của nó. Anh đang thực hiện một nhiệm vụ rất khó và biết rằng mình sẽ phải đi sâu hơn rất nhiều lần. Để hỗ trợ việc định hướng, anh xem xét nhiều mẫu khác nhau trong lưới ban đầu. Một mẫu gồm một nhóm ô duy nhất liên thông qua cạnh chung (chỉ chung góc không được tính là liên thông), cùng với màu của các ô đó. Mẫu có thể có các khoảng trống bên trong, miễn là các ô của mẫu tạo thành một nhóm liên thông duy nhất; những khoảng trống ấy không được coi là một phần của mẫu. Hai mẫu giống nhau khi và chỉ khi chúng có cùng số lượng và cách sắp xếp các ô (không lật đối xứng hay xoay), với các màu tương ứng giống nhau.

Ví dụ, trong các lưới trên, mẫu 8 ô sau xuất hiện trong lưới ban đầu:

BBB
B B
BBB

Nó không xuất hiện sau khi đi sâu hơn một lần, nhưng xuất hiện sau khi đi sâu hơn hai lần, ba lần, và cứ như vậy trong mọi lưới giấc mơ sâu hơn nữa.

Codd muốn tìm mẫu lớn nhất từ lưới giấc mơ ban đầu mà sẽ xuất hiện trong ít nhất một googol (\(10^{100}\)) lưới giấc mơ sâu hơn. Với ví dụ đã cho, mẫu trên là mẫu lớn nhất như vậy. Mặc dù nó không xuất hiện sau lần đi sâu đầu tiên, nó vẫn xuất hiện ở ít nhất một googol mức sâu hơn. Những mẫu khác có kích thước nhỏ hơn cũng thỏa điều kiện, nhưng không có mẫu 9 ô nào thỏa; mẫu 9 ô duy nhất có thể có phải giống hệt toàn bộ lưới ban đầu, và mẫu đó sẽ không bao giờ xuất hiện trong bất kỳ lưới sâu hơn nào, chứ chưa nói đến một googol lưới.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\): lần lượt là số hàng và số cột của lưới giấc mơ. Tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) ký tự; mỗi ký tự là B hoặc W. Các dòng này biểu diễn trực tiếp lưới giấc mơ.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là kích thước lớn nhất có thể của ít nhất một mẫu thỏa yêu cầu của Codd như mô tả ở trên.

Ràng buộc

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

Phân nhóm

Test Set 1 (Hiển thị):

• \(1 \le R \le 3\).
• \(1 \le C \le 4\).

Test Set 2 (Ẩn):

• \(1 \le R \le 20\).
• \(1 \le C \le 20\).

Đ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
3 3
BBB
BWB
BBB
2 3
BBB
WBW
1 1
W
3 3
WBW
BWB
WBW
2 4
BBWW
BBWW

Case #1: 8
Case #2: 5
Case #3: 1
Case #4: 4
Case #5: 8

BBB
WB

BBB
W W

WB
BW

Nguồn

Google Code Jam 2018, Vòng 2, bài Gridception.

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