Google Code Jam 2018 - Edgy Baking
Xem PDFThợ làm bánh Maillard đã cán một ít bột bánh quy rồi cắt thành \(N\) chiếc bánh quy, mỗi chiếc là một hình chữ nhật. Ngay trước khi cho chúng vào lò, ông nhớ ra rằng phần rìa giòn và được caramen hóa của bánh quy đặc biệt thơm ngon. Cụ thể, ông cho rằng mình sẽ hài lòng nhất nếu tổng chu vi của tất cả bánh quy gần \(P\) milimét (mm) nhất có thể nhưng không vượt quá \(P\). (Nếu mẻ bánh có quá nhiều rìa, nó có thể bị cháy!)
Với mỗi chiếc bánh, ông Maillard có thể quyết định giữ nguyên nó, hoặc thực hiện một đường cắt thẳng duy nhất để chia nó thành hai nửa (không nhất thiết là hình chữ nhật) có diện tích bằng nhau. (Lưu ý rằng một đường cắt như vậy nhất thiết phải đi qua tâm chiếc bánh.) Hai chiếc bánh mới được tạo ra theo cách này không thể tiếp tục bị cắt.
Nếu ông Maillard đưa ra các quyết định tối ưu, ông có thể tiến gần đến \(P\) nhất là bao nhiêu mà không vượt quá nó?
Dữ liệu vào
Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng gồm hai số nguyên \(N\) và \(P\): lần lượt là số bánh quy và tổng chu vi mong muốn (tính bằng mm). Sau đó là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(W_i\) và \(H_i\): chiều rộng và chiều cao (đều tính bằng mm) của chiếc bánh thứ \(i\).
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à một số thực: tổng chu vi lớn nhất có thể (tính bằng mm) của tất cả bánh quy sau khi ông Maillard cắt xong mà không vượt quá \(P\). Giá trị y được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không quá \(10^{-6}\). Xem FAQ của Code Jam để biết ý nghĩa của điều này và các định dạng số thực được chấp nhận.
Ràng buộc
- \(1\le T\le100\).
- \(1\le N\le100\).
- \(1\le W_i\le250\) với mọi \(i\).
- \(1\le H_i\le250\) với mọi \(i\).
- \(P\ge 2\times\sum_i(W_i+H_i)\). (\(P\) ít nhất bằng tổng chu vi của tất cả bánh trước khi thực hiện bất kỳ đường cắt nào.)
- \(P\le10^8\).
Phân nhóm
Test Set 1 (Hiển thị):
- \(W_i=W_j\) với mọi \(i,j\).
- \(H_i=H_j\) với mọi \(i,j\).
- Tất cả bánh quy được cung cấp đều có cùng kích thước.
Test Set 2 (Ẩn): Không có ràng buộc bổ sung ngoài các ràng buộc chung. (Đặc biệt, các bánh quy được cung cấp không nhất thiết đều có cùng kích thước.)
Đ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 | 14/43 | 32,56% |
| Test Set 2 | 29/43 | 67,44% |
Ví dụ
Ví dụ 1
Input
4
1 7
1 1
2 920
50 120
50 120
1 32
7 4
3 240
10 20
20 30
30 10Output
Case #1: 6.828427
Case #2: 920.000000
Case #3: 32.000000
Case #4: 240.000000Giải thích
Lưu ý rằng bộ test ví dụ cuối cùng sẽ không xuất hiện trong Test Set 1.
Trong Ví dụ #1, chỉ có một chiếc bánh, là hình vuông cạnh 1. Ông Maillard có thể cắt từ một góc đến góc đối diện theo đường chéo, tạo ra hai tam giác vuông, mỗi tam giác có các cạnh dài \(1\), \(1\) và \(\sqrt{2}\). Khi đó tổng chu vi là \(4+2\times\sqrt{2}\); giá trị này nhỏ hơn \(P=7\), nhưng không thể tiến gần hơn nữa.
Trong Ví dụ #2, ông Maillard có thể cắt chiếc bánh đầu tiên dọc theo trục dài hơn để tạo ra hai hình chữ nhật mới kích thước \(25\times120\), và giữ nguyên chiếc bánh thứ hai. Khi đó tổng chu vi là \(580+340=920\), đúng bằng \(P\).
Trong Ví dụ #3, ông Maillard có thể cắt chiếc bánh để tạo ra hai hình thang, mỗi hình có các cạnh dài \(2\), \(4\), \(5\) và \(5\). Khi đó tổng chu vi mới là \(32\), đúng bằng \(P\).
Trong Ví dụ #4, tổng chu vi ban đầu đã đúng bằng \(P\), vì vậy ông Maillard không nên thực hiện đường cắt nào.
Nguồn
Google Code Jam 2018, Vòng 1A, bài Edgy Baking.
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 2018 - Round 1A (14 Tháng tư, 2018)
Bình luận