Google Code Jam 2022 - 3D Printing
Xem PDFBạn là thành viên ban điều hành lễ hội Database Design Day. Bạn phụ trách quảng bá và muốn in ba chữ D để tạo logo cuộc thi. Bạn có thể chọn bất kỳ màu nào, nhưng cả ba chữ phải được in cùng một màu.
Bạn được cấp ba máy in và sẽ dùng mỗi máy để in một chữ D. Mỗi máy in sử dụng mực từ \(4\) hộp riêng biệt có màu khác nhau — cyan, magenta, vàng và đen — để tạo nên bất kỳ màu nào. Với các máy in này, một màu được xác định duy nhất bởi bốn số nguyên không âm \(c,m,y,k\), lần lượt là số đơn vị mực cyan, magenta, vàng và đen cần để tạo màu đó.
Tổng lượng mực cần để in một chữ D chính xác là \(10^6\) đơn vị. Chẳng hạn, in một chữ D màu vàng thuần dùng \(10^6\) đơn vị mực vàng và \(0\) đơn vị của mọi màu khác. In một chữ D màu đỏ Code Jam dùng \(0\) đơn vị cyan, \(500000\) đơn vị magenta, \(450000\) đơn vị vàng và \(50000\) đơn vị đen.
Để in một màu, máy in phải có ít nhất lượng mực được yêu cầu trong từng hộp màu. Cho lượng mực mỗi máy còn có trong mỗi hộp, hãy đưa ra một màu bất kỳ, được biểu diễn bởi bốn số nguyên không âm có tổng bằng \(10^6\), sao cho cả ba máy đều có đủ mực để in màu đó.
Dữ liệu vào
Dòng đầu tiên chứa số bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ test gồm \(3\) dòng. Dòng thứ \(i\) chứa bốn số nguyên \(C_i,M_i,Y_i,K_i\), lần lượt là số đơn vị mực cyan, magenta, vàng và đen trong các hộp của máy in thứ \(i\).
Dữ liệu ra
Với mỗi bộ test, in một dòng Case #x: r, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), và \(r\) là IMPOSSIBLE nếu không có màu nào cả ba máy đều in được. Nếu có, \(r\) phải có dạng c m y k, trong đó \(c,m,y,k\) là các số nguyên không âm có tổng bằng \(10^6\), đồng thời \(c\le C_i\), \(m\le M_i\), \(y\le Y_i\) và \(k\le K_i\) với mọi \(i\).
Nếu có nhiều lời giải, bạn có thể in bất kỳ lời giải nào. Xem mục “What if a test case has multiple correct solutions?” trong phần Competing của FAQ. Thông tin về việc có nhiều lời giải này sẽ không còn được nhắc lại một cách tường minh trong phần còn lại của cuộc thi năm 2022.
Ràng buộc
- \(0\le C_i\le10^6\) với mọi \(i\).
- \(0\le M_i\le10^6\) với mọi \(i\).
- \(0\le Y_i\le10^6\) với mọi \(i\).
- \(0\le K_i\le10^6\) với mọi \(i\).
Phân nhóm
- Test Set 1 (phán quyết hiển thị): \(1\le T\le100\).
Đ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 | 13/13 | 100% |
Ví dụ
Ví dụ 1
Input
3
300000 200000 300000 500000
300000 200000 500000 300000
300000 500000 300000 200000
1000000 1000000 0 0
0 1000000 1000000 1000000
999999 999999 999999 999999
768763 148041 178147 984173
699508 515362 534729 714381
949704 625054 946212 951187Output
Case #1: 300000 200000 300000 200000
Case #2: IMPOSSIBLE
Case #3: 400001 100002 100003 399994Giải thích
Ví dụ #1 là hình phía trên. Màu được đề xuất dùng hết mực trong các hộp cyan, magenta và vàng của máy in thứ nhất, đồng thời dùng hết mực trong hộp đen của máy in cuối. Không thể dùng thêm một đơn vị nào của cả bốn màu, nên đầu ra mẫu là đầu ra duy nhất có thể cho trường hợp này.
Trong Ví dụ #2, magenta là màu duy nhất mà cả máy in thứ nhất và thứ hai đều có, nên cơ hội duy nhất là dùng \(10^6\) đơn vị magenta. Đáng tiếc, máy in thứ ba thiếu một chút mực, khiến trường hợp này không thể thực hiện.
Trong Ví dụ #3, một số đầu ra đúng khác là 400000 100000 100000 400000, 300000 0 0 700000 và 350000 140000 160000 350000, cùng rất nhiều đáp án khác. Lưu ý rằng 300000 140000 160000 700000 không hợp lệ: dù mọi máy in đều có đủ từng màu, tổng lượng mực bắt buộc phải đúng bằng \(10^6\).
Nguồn
Google Code Jam 2022, Vòng loại, bài 3D Printing.
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 2022 - Qualification Round (2 Tháng tư, 2022)
Bình luận