1. Google Code Jam 2017 - Ample Syrup
Nhà bếp của Infinite House of Pancakes vừa nhận một đơn đặt một chồng gồm \(K\) chiếc bánh kếp! Đầu bếp hiện có \(N\) chiếc bánh, với \(N\ge K\). Mỗi chiếc bánh là một hình trụ; các bánh khác nhau có thể có bán kính và chiều cao khác nhau.
Là bếp phó, bạn phải chọn \(K\) trong số \(N\) chiếc bánh, bỏ những chiếc còn lại rồi xếp \(K\) chiếc đã chọn lên đĩa như sau. Trước tiên, lấy chiếc có bán kính lớn nhất và đặt một mặt tròn của nó xuống đĩa (nếu có nhiều chiếc cùng bán kính, có thể chọn bất kỳ chiếc nào). Sau đó đặt chiếc có bán kính lớn tiếp theo lên trên, cứ thế cho đến khi đủ \(K\) chiếc; tâm các mặt tròn phải nằm trên một đường thẳng vuông góc với đĩa, như hình minh họa:
Bạn biết thực khách chỉ yêu thích một thứ ngang với bánh kếp: si-rô! Ta muốn cực đại hóa tổng diện tích bề mặt bánh lộ ra trong chồng, vì càng nhiều bề mặt lộ ra thì càng có nhiều chỗ để rưới si-rô ngon tuyệt. Mọi phần của một chiếc bánh không tiếp xúc với chiếc bánh khác hoặc với đĩa đều được coi là lộ ra.
Nếu chọn tối ưu \(K\) chiếc bánh, tổng diện tích bề mặt lộ ra lớn nhất có thể đạt được là bao nhiêu?
Dữ liệu vào
Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng gồm hai số nguyên \(N\) và \(K\): tổng số bánh hiện có và số bánh trong chồng mà thực khách đặt. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa hai số nguyên \(R_i\) và \(H_i\), lần lượt là bán kính và chiều cao của chiếc bánh thứ \(i\), tính bằng milimét.
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) và y là tổng diện tích bề mặt lộ ra lớn nhất, tính bằng milimét vuông. y được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không vượt quá \(10^{-6}\).
Ràng buộc
- \(1\le T\le100\).
- \(1\le K\le N\).
- \(1\le R_i\le10^6\) với mọi \(i\).
- \(1\le H_i\le10^6\) với mọi \(i\).
Phân nhóm
Test Set 1 (Visible): \(1\le N\le10\).
Test Set 2 (Hidden): \(1\le N\le1000\).
Đ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 | 9/25 | 36% |
| Test Set 2 | 16/25 | 64% |
Ví dụ
Ví dụ 1
Input
4
2 1
100 20
200 10
2 2
100 20
200 10
3 2
100 10
100 10
100 10
4 2
9 3
7 1
10 1
8 4Output
Case #1: 138230.076757951
Case #2: 150796.447372310
Case #3: 43982.297150257
Case #4: 625.176938064Giải thích
Ở test 1, “chồng” chỉ có một chiếc bánh. Nếu dùng chiếc đầu tiên, diện tích lộ ra là \(\pi R_0^2+2\pi R_0H_0=14000\pi\,\mathrm{mm}^2\). Nếu dùng chiếc thứ hai, diện tích là \(44000\pi\,\mathrm{mm}^2\). Vì vậy dùng chiếc thứ hai tốt hơn.
Ở test 2, ta dùng cả hai chiếc bánh của test 1. Chiếc thứ nhất đóng góp mặt trên và mặt bên, tổng cộng \(14000\pi\,\mathrm{mm}^2\). Chiếc thứ hai đóng góp phần mặt trên không bị chiếc thứ nhất che cùng mặt bên, tổng cộng \(34000\pi\,\mathrm{mm}^2\). Tổng diện tích lộ ra là \(48000\pi\,\mathrm{mm}^2\).
Ở test 3, mọi chiếc bánh đều có bán kính 100 và chiều cao 10. Xếp hai chiếc lại tương đương một hình trụ mới có bán kính 100 và chiều cao 20, với diện tích lộ ra \(14000\pi\,\mathrm{mm}^2\).
Ở test 4, chồng tối ưu dùng hai chiếc bánh có bán kính 8 và 9.
Nguồn
Google Code Jam 2017, Vòng 1C, bài Ample Syrup.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.