Google Code Jam 2011 - Spinning Blade
Xem PDFVì đã chán với những cái bẫy trong thiết kế căn cứ bí mật của mình, bạn quyết định chọn một thứ gì đó cổ điển nhưng luôn thú vị - lưỡi dao xoay. Bạn đã đặt hàng một tấm kim loại rất nặng, từ đó bạn sẽ cắt ra lưỡi dao; một lưới ô vuông đồng nhất kích thước \(C \times R\) sẽ được vẽ trên tấm kim loại. Bạn đã xác định được hình dạng tốt nhất cho lưỡi dao -- trước tiên bạn sẽ cắt một hình vuông lớn gồm \(K \times K\) ô lưới, với \(K \ge 3\). Sau đó, bạn sẽ cắt bỏ bốn ô góc \(1 \times 1\) của hình vuông đó để tạo thành một lưỡi dao. Sau khi xác định xong tất cả những điều này, bạn bắt đầu đợi tấm kim loại được giao đến.
Khi tấm kim loại đến nơi, bạn đã bị sốc khi phát hiện ra rằng nó có những khiếm khuyết! Bạn mong đợi mỗi ô có khối lượng \(D\), nhưng hóa ra khối lượng có thể thay đổi một chút do sự khác biệt về độ dày. Điều này thật tệ vì bạn muốn lắp một trục xoay chính xác vào tâm của lưỡi dao và xoay nó thật nhanh, vì vậy trọng tâm của lưỡi dao cũng phải nằm chính xác tại tâm của nó. Định nghĩa về trọng tâm của một vật thể phẳng có thể được tìm thấy bên dưới.
Cho lưới và khối lượng của từng ô, kích thước lớn nhất có thể của lưỡi dao mà bạn có thể tạo ra để trọng tâm nằm chính xác ở tâm của nó là bao nhiê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ộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa 3 số nguyên: \(R, C\) và \(D\) — kích thước của lưới và khối lượng bạn mong đợi mỗi ô sẽ có. \(R\) dòng tiếp theo, mỗi dòng chứa \(C\) chữ số \(w_{ij}\), cho biết sự chênh lệch giữa khối lượng thực tế và khối lượng mong đợi của các ô lưới. Mỗi ô có mật độ đồng nhất, nhưng có thể có khối lượng nguyên trong khoảng từ \(D + 0\) đến \(D + 9\), bao gồm cả hai đầu.
Dữ liệu ra
Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: \(K\)", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và \(K\) là kích thước lớn nhất có thể của lưỡi dao bạn có thể cắt ra. Nếu không tìm thấy lưỡi dao chấp nhận được nào có kích thước ít nhất là 3, hãy in "IMPOSSIBLE" thay thế.
Ràng buộc
- \(1 \le T \le 20\).
- \(0 \le w_{ij} \le 9\).
- Kích thước tệp đầu vào không quá 625KB.
Phân nhóm
- Test set 1 (Visible): \(3 \le R \le 10, 3 \le C \le 10, 1 \le D \le 100\).
- Test set 2 (Hidden): \(3 \le R \le 500, 3 \le C \le 500, 1 \le D \le 10^6\).
Đ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/20 | 40% |
| Test Set 2 | 12/20 | 60% |
Ví dụ
Ví dụ 1
Input
2
6 7 2
1111111
1122271
1211521
1329131
1242121
1122211
3 3 7
123
234
345Output
Case #1: 5
Case #2: IMPOSSIBLENote
Trọng tâm của một vật thể 2D được định nghĩa chính thức là một điểm \(c\). Nếu bạn tính tổng của \((p - c) \times \text{mass}(p)\) cho tất cả các điểm \(p\) trong vật thể, bạn phải nhận được \(0\). Ở đây, \(p, c\) và \(0\) là các vectơ hai chiều. Định nghĩa này cũng hoạt động nếu bạn coi mỗi ô lưới là một "điểm", với toàn bộ khối lượng của nó tập trung tại tâm.
Trong thực tế, bạn có thể đặt ngón tay của mình dưới trọng tâm của một vật thể phẳng và giữ thăng bằng vật thể đó trên ngón tay. Nó sẽ không rơi.
Để minh họa bằng một ví dụ, lưỡi dao duy nhất có thể cắt ra trong ví dụ thứ hai, lưỡi dao \(3 \times 3\) được tạo ra bằng cách cắt bỏ các góc, có trọng tâm tại điểm \((1.54, 1.46)\), trong đó chúng ta giả định góc dưới bên trái của tấm kim loại có tọa độ \((0, 0)\), và tọa độ tăng dần sang phải và lên trên tương ứng. Điều này được xác nhận bằng cách kiểm tra đẳng thức sau: \((-1.04, 0.04) \times 9 + (-0.04, 1.04) \times 9 + (-0.04, 0.04) \times 10 + (-0.04, -0.96) \times 11 + (0.96, 0.04) \times 11 = (0, 0)\).
Nguồn
Google Code Jam 2011, Vòng 2, bài Spinning Blade.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2011 - Round 2 (4 Tháng sáu, 2011)
Bình luận