Google Code Jam 2020 - Incremental House of Pancakes
Xem PDFMỗi sáng tại Nhà Bánh Kếp Tăng Dần, nhân viên nhà bếp chuẩn bị toàn bộ bánh kếp cho ngày hôm đó và xếp chúng thành hai chồng. Ban đầu, chồng bên trái có \(L\) chiếc bánh kếp và chồng bên phải có \(R\) chiếc bánh kếp.
Khách hàng của nhà hàng này có thói quen rất nhất quán: khách thứ \(i\) đến nhà hàng (đánh số từ 1) luôn gọi \(i\) chiếc bánh kếp. Khi khách thứ \(i\) gọi \(i\) chiếc, bạn lấy \(i\) chiếc từ chồng hiện còn nhiều bánh nhất (hoặc từ chồng bên trái nếu hai chồng có số bánh bằng nhau). Nếu không chồng nào có ít nhất \(i\) chiếc bánh, nhà hàng đóng cửa và khách thứ \(i\) không được phục vụ chiếc bánh nào. Bạn không bao giờ dùng bánh từ cả hai chồng để hoàn thành một đơn gọi món.
Biết số bánh kếp ban đầu trong mỗi chồng, hãy xác định có bao nhiêu khách hàng được phục vụ và mỗi chồng còn lại bao nhiêu chiếc bánh khi nhà hàng đóng cửa.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào cho biết số bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên \(L\) và \(R\): lần lượt là số bánh kếp ban đầu trong chồng bên trái và chồng bên phải như mô tả ở trên.
Dữ liệu ra
Với mỗi bộ test, in một dòng có dạng Case #x: n l r, trong đó x là số thứ tự bộ test (bắt đầu từ 1), n là số khách hàng được phục vụ, còn l và r lần lượt là số bánh kếp còn lại trong chồng bên trái và bên phải khi nhà hàng đóng cửa.
Ràng buộc
- \(1 \le T \le 1000\).
Phân nhóm
Test Set 1 (Visible Verdict):
- \(1 \le L \le 1000\).
- \(1 \le R \le 1000\).
Test Set 2 (Hidden Verdict):
- \(1 \le L \le 10^{18}\).
- \(1 \le R \le 10^{18}\).
Đ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 | 5/19 | 26,32% |
| Test Set 2 | 14/19 | 73,68% |
Ví dụ
Ví dụ 1
Input
3
1 2
2 2
8 11Output
Case #1: 1 1 1
Case #2: 2 1 0
Case #3: 5 0 4Giải thích
Trong bộ test mẫu số 1, khách hàng đầu tiên nhận 1 chiếc bánh từ chồng bên phải, khiến mỗi chồng còn lại 1 chiếc. Khách hàng thứ hai muốn 2 chiếc bánh, nhưng không chồng nào có đủ cho họ, mặc dù tổng cộng vẫn còn 2 chiếc bánh.
Trong bộ test mẫu số 2, khách hàng đầu tiên nhận 1 chiếc bánh từ chồng bên trái vì hai chồng có số bánh bằng nhau. Sau đó, chồng bên trái còn 1 chiếc và chồng bên phải còn 2 chiếc. Khách hàng thứ hai muốn 2 chiếc bánh; bạn phục vụ họ bằng chồng bên phải và làm chồng này hết sạch. Khi khách hàng thứ ba đến, không chồng nào có 3 chiếc bánh, nên không có thêm đơn gọi món nào được phục vụ.
Trong bộ test mẫu số 3, khách hàng đầu tiên được phục vụ từ chồng bên phải, khiến chồng bên trái còn 8 chiếc và chồng bên phải còn 10 chiếc. Khách hàng thứ hai cũng được phục vụ từ chồng bên phải, khiến mỗi chồng còn 8 chiếc. Khách hàng thứ ba được phục vụ từ chồng bên trái, khiến chồng này còn 5 chiếc và chồng bên phải còn 8 chiếc. Sau đó, khách hàng thứ tư được phục vụ từ chồng bên phải, khiến chồng này còn 4 chiếc. Phục vụ khách hàng thứ năm làm chồng bên trái hết sạch; tiếp đó, không chồng nào còn đủ bánh để phục vụ khách hàng thứ sáu.
Nguồn
Google Code Jam 2020, Vòng 2, bài Incremental House of Pancakes.
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 2020 - Round 2 (16 Tháng năm, 2020)
Bình luận