Google Code Jam 2009 - Round 2

Hang động đang bốc cháy và khói ở khắp mọi nơi! Bạn đang cố gắng đào đường xuống đáy hang, nơi bạn có thể hít thở. Vấn đề là có một số lỗ hổng không khí bên trong hang, và bạn không muốn bị rơi quá nhiều nếu không bạn sẽ bị thương.

Hang động được biểu diễn dưới dạng một ma trận \(R \times C\) với các lỗ hổng không khí và các ô đá cứng. Bạn bắt đầu tại vị trí \((1, 1)\), nằm ở góc trên bên trái.

Bạn có thể di chuyển từng ô một, sang trái hoặc sang phải, nếu ô đó trống (là một lỗ hổng không khí). Sau khi di chuyển, nếu ô bên dưới trống, bạn sẽ rơi xuống cho đến khi chạm vào đá cứng hoặc đáy hang. Khoảng cách rơi phải tối đa là \(F\), nếu không bạn sẽ bị thương. Bạn phải xuống được đáy hang mà không bị thương. Trong khi đang rơi, bạn không thể di chuyển sang trái hoặc sang phải.

Bạn cũng có thể "đào", biến một ô chứa đá cứng thành một lỗ hổng không khí. Ô mà bạn đào có thể là một trong hai ô: ô bên phải và bên dưới bạn, hoặc ô bên trái và bên dưới bạn. Ô phía trên ô bạn đang đào phải là ô trống. Trong khi đang rơi, bạn không thể đào.

Mục tiêu của bạn không chỉ là xuống được đáy hang, mà còn phải "đào" ít ô nhất có thể.

Hãy mô tả các thao tác bằng một ví dụ cụ thể:

Bạn bắt đầu tại \((1, 1)\) và di chuyển sang phải 3 lần đến vị trí \((1, 4)\), giống như trong hình.
Bạn đào đá tại vị trí \((2, 5)\). Ô "A" trở nên trống.
Bạn di chuyển sang phải một vị trí và vì không có ô bên dưới, bạn rơi 3 ô xuống vị trí \((4, 5)\).
Bạn đào đá tại vị trí \((5, 6)\). Ô "B" trở nên trống.
Bạn di chuyển sang phải một vị trí và vì không có ô bên dưới, bạn rơi 1 ô xuống vị trí \((5, 6)\).
Bạn đã xuống được đáy hang bằng cách đào 2 ô.

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, \(N\). \(N\) bộ test tiếp theo.
Dòng đầu tiên của mỗi bộ test có định dạng:

R C F

trong đó \(R\) là số hàng trong hang động, \(C\) là số cột trong hang động, và \(F\) là khoảng cách tối đa bạn có thể rơi mà không bị thương.
Tiếp theo là \(R\) hàng, mỗi hàng chứa \(C\) ký tự. Mỗi ký tự có thể là một trong hai loại:

• # cho đá cứng
• . cho lỗ hổng không khí

Ô trên cùng bên trái luôn trống, và ô bên dưới nó sẽ là đá cứng.

Dữ liệu ra

Với mỗi bộ test, hãy in ra một dòng có định dạng:

Case #X: No/Yes [D]

trong đó \(X\) là số thứ tự bộ test, bắt đầu từ 1. In ra "No" nếu bạn không thể xuống được đáy hang. In ra "Yes \(D\)" nếu có thể xuống được đáy hang và số lượng ô tối thiểu cần đào là \(D\).

Ràng buộc

• \(1 \le N \le 50\)
• \(1 \le F < R\)

Phân nhóm

• Small dataset: \(2 \le R \le 10, 2 \le C \le 6\).
• Large dataset: \(2 \le R \le 50, 2 \le C \le 50\).

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

Case #1: No
Case #2: Yes 3
Case #3: No

Nguồn

Google Code Jam 2009, Vòng 2, bài A Digging Problem.

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 được cho một ma trận kích thước \(N \times N\) với các giá trị 0 và 1. Bạn có thể tráo đổi bất kỳ hai hàng kề nhau nào của ma trận.

Mục tiêu của bạn là đưa tất cả các giá trị 1 trong ma trận xuống dưới hoặc nằm trên đường chéo chính. Nghĩa là, đối với mỗi \(X\) mà \(1 \le X \le N\), không được có giá trị 1 nào ở hàng \(X\) nằm bên phải cột \(X\).

Hãy trả về số lần tráo đổi hàng tối thiểu bạn cần thực hiện để đạt được mục tiêu.

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\). Tiếp theo là \(T\) bộ test.
Dòng đầu tiên của mỗi bộ test có một số nguyên, \(N\). Mỗi dòng trong số \(N\) dòng tiếp theo chứa \(N\) ký tự. Mỗi ký tự là 0 hoặc 1.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra một dòng:

Case #X: K

Bạn được đảm bảo rằng luôn có lời giải cho mỗi bộ test.

Ràng buộc

• \(1 \le T \le 60\)

Phân nhóm

• Small dataset: \(1 \le N \le 8\)
• Large dataset: \(1 \le N \le 40\)

Đ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
2
10
11
3
001
100
010
4
1110
1100
1100
1000

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

Nguồn

Google Code Jam 2009, Vòng 2, bài Crazy Rows.

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 đang trong quá trình viết bản tóm tắt kinh tế cuối năm cho tờ báo của mình và bạn đã quyết định muốn hiển thị một số biểu đồ để chứng minh các loại cổ phiếu khác nhau đã hoạt động như thế nào trong suốt năm qua. Bạn đã quyết định rằng bạn muốn hiển thị giá của \(n\) loại cổ phiếu khác nhau, tất cả tại cùng \(k\) thời điểm trong năm.

Một biểu đồ đơn giản về giá của một loại cổ phiếu sẽ vẽ các đường thẳng giữa các điểm \((0, \text{price}_0), (1, \text{price}_1), \dots, (k-1, \text{price}_{k-1})\), trong đó \(\text{price}_i\) là giá của cổ phiếu tại thời điểm thứ \(i\).

Để tiết kiệm không gian, bạn đã phát minh ra khái niệm biểu đồ lồng nhau. Một biểu đồ lồng nhau là sự kết hợp của một hoặc nhiều biểu đồ đơn giản và hiển thị giá của nhiều loại cổ phiếu (chỉ đơn giản là vẽ một đường cho mỗi loại). Để tránh nhầm lẫn giữa các cổ phiếu được hiển thị trong một biểu đồ, các đường trong một biểu đồ lồng nhau không được cắt nhau hoặc chạm nhau.

Cho danh sách giá của \(n\) loại cổ phiếu tại mỗi thời điểm trong \(k\) thời điểm, hãy xác định số lượng biểu đồ lồng nhau tối thiểu bạn cần để hiển thị tất cả giá của các loại cổ phiếu.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào sẽ chứa một số nguyên duy nhất \(T\), số lượng bộ thử nghiệm. Sau đó sẽ là \(T\) bộ thử nghiệm trên các dòng khác nhau, mỗi bộ có dạng:

n k
price0,0 price0,1 ... price0,k-1
price1,0 price1,1 ... price1,k-1
...
pricen-1,0 pricen-1,1 ... pricen-1,k-1

Trong đó \(\text{price}_{i,j}\) là một số nguyên, giá của cổ phiếu thứ \(i\) tại thời điểm \(j\).

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, in ra một dòng duy nhất chứa "Case #X: Y", trong đó \(X\) là số thứ tự của bộ thử nghiệm (bắt đầu từ 1) và \(Y\) là số lượng biểu đồ lồng nhau tối thiểu cần thiết để hiển thị giá của tất cả các cổ phiếu.

Ràng buộc

• \(1 \le T \le 100\)
• \(2 \le k \le 25\)
• \(0 \le \text{price}_{i,j} \le 1000000\)

Phân nhóm

• Small Input: \(1 \le n \le 16\).
• Large Input: \(1 \le n \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 4
1 2 3 4
2 3 4 6
6 5 4 3
3 3
5 5 5
4 4 6
4 5 4
5 2
1 1
2 2
5 4
4 4
4 1

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

Nguồn

Google Code Jam 2009, Vòng 2, bài Stock Charts.

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

Trong nhà kính của bạn có một số cây cần được tưới nước.

Mỗi cây chiếm một diện tích là một hình tròn. Không có hai cây nào nằm đè lên nhau hoặc chạm nhau.

Bạn định mua hai vòi phun nước. Mỗi vòi phun sẽ phun nước cho mọi thứ trong một hình tròn bán kính \(R\).

Một vòi phun sẽ hoạt động vào buổi sáng, và vòi kia sẽ hoạt động vào ban đêm. Để bạn hài lòng rằng một cây sẽ nhận đủ nước, toàn bộ diện tích của cây đó phải được tưới vào buổi sáng, hoặc toàn bộ diện tích của cây đó phải được tưới vào ban đêm. Vì vậy, mỗi hình tròn đại diện cho một cây phải nằm hoàn toàn trong một hoặc cả hai hình tròn đại diện cho khu vực mà vòi phun có thể tưới.

Cho biết vị trí và bán kính của mỗi cây, hãy tìm bán kính \(R\) nhỏ nhất để có thể đặt hai vòi phun tưới được tất cả các cây. Các vòi phun sẽ được lắp trên trần nhà, vì vậy vị trí của vòi phun có thể nằm bên trong diện tích của một cây.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(C\), số lượng bộ dữ liệu trong file input.
  Với mỗi bộ dữ liệu:
• Một dòng chứa \(N\), trong đó \(N\) là số lượng cây bạn có.
• \(N\) dòng, mỗi dòng cho một cây, chứa ba số nguyên $X$ $Y$ $R$, trong đó (\(X\), \(Y\)) là tọa độ tâm của cây, và \(R\) là bán kính của cây.

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Một dòng chứa chuỗi Case #x: R trong đó \(x\) là số thứ tự của bộ dữ liệu, bắt đầu từ 1, và \(R\) là bán kính nhỏ nhất của vòi phun.

Bất kỳ câu trả lời nào có sai số tuyệt đối hoặc tương đối không quá \(10^{-5}\) đều sẽ được chấp nhận.

Ràng buộc

• Tất cả các số trong file input là số nguyên.
• \(1 \le X \le 1000\)
• \(1 \le Y \le 1000\)
• \(1 \le R \le 100\)

Phân nhóm

• Small Input: \(1 \le C \le 10, 1 \le N \le 3\).
• Large Input: \(1 \le C \le 30, 1 \le N \le 40\).

Đ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
20 10 2
20 20 2
40 10 3
3
20 10 3
30 10 3
40 10 3

Case #1: 7.000000
Case #2: 8.000000

Nguồn

Google Code Jam 2009, Vòng 2, bài Watering Plants.

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