Google Code Jam 2018 - Transmutation
Xem PDFBạn là nhà giả kim tài giỏi nhất của một đất nước coi những kim loại như vàng, bạch kim và bạc là tẻ nhạt, nhưng lại đặc biệt quý trọng chì. Thế giới biết đến \(M\) kim loại; chì là kim loại số 1 trong bảng tuần hoàn của bạn. Nhà lãnh đạo yêu cầu bạn dùng số kim loại trong kho bạc để tạo ra nhiều chì nhất có thể.
Với mỗi kim loại, kể cả chì, bạn biết đúng một công thức tạo một gram kim loại đó bằng cách phá hủy một gram của mỗi loại trong hai kim loại nguyên liệu. Nếu thắc mắc về định luật bảo toàn khối lượng, gram còn lại bị mất vào các phế phẩm vô dụng. Công thức không hoạt động với phần lẻ của một gram. Tuy nhiên, bạn có thể dùng mỗi công thức bao nhiêu lần tùy ý, hoặc không dùng lần nào, miễn là mỗi lần đều có đủ nguyên liệu.
Nếu lựa chọn tối ưu, tổng lượng chì lớn nhất mà bạn có thể thu được là bao nhiêu? Lưu ý rằng sau khi hoàn tất, một số kim loại khác chì có thể vẫn còn dư.
Dữ liệu vào
Dòng đầu chứa số bộ test \(T\).
Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(M\), số kim loại được biết đến. Tiếp theo là \(M\) dòng, mỗi dòng chứa hai số nguyên \(R_{i1}\) và \(R_{i2}\); dòng thứ \(i\) cho biết có thể tạo một gram kim loại \(i\) bằng cách phá hủy một gram kim loại \(R_{i1}\) và một gram kim loại \(R_{i2}\). Cuối cùng là một dòng chứa \(M\) số nguyên \(G_1,G_2,\ldots,G_M\), trong đó \(G_i\) là số gram kim loại \(i\) trong kho bạc. Chì là kim loại 1.
Dữ liệu ra
Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là lượng chì lớn nhất, tính bằng gram, mà bạn có thể thu được.
Ràng buộc
- \(1\le T\le100\).
- \(1\le R_{i1}<R_{i2}\le M\) với mọi \(i\).
Phân nhóm
- Test Set 1 (Hiển thị): \(2\le M\le8\); \(0\le G_i\le8\) với mọi \(i\).
- Test Set 2 (Ẩn): \(2\le M\le100\); \(0\le G_i\le100\) với mọi \(i\).
- Test Set 3 (Ẩn): \(2\le M\le100\); \(0\le G_i\le10^9\) với mọi \(i\).
Đ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 | 15/45 | 33,33% |
| Test Set 2 | 18/45 | 40% |
| Test Set 3 | 12/45 | 26,67% |
Ví dụ
Ví dụ 1
Input
3
3
2 3
1 3
1 2
5 2 3
5
3 4
3 4
4 5
3 5
1 3
0 8 6 2 4
4
3 4
2 3
2 3
2 3
0 1 1 0Output
Case #1: 7
Case #2: 4
Case #3: 0Giải thích
Trong test mẫu 1, chiến lược tối ưu dùng 2 gram kim loại 2 và 2 gram kim loại 3 để tạo thêm 2 gram chì, cho tổng cộng 7 gram chì.
Trong test mẫu 2, trước hết dùng 2 gram kim loại 3 và 2 gram kim loại 5 để tạo 2 gram kim loại 4; sau đó dùng 4 gram kim loại 3 và 4 gram kim loại 4 để tạo 4 gram chì. Hai công thức có thể có cùng cặp nguyên liệu, chỉ khác kỹ thuật giả kim. Không phải kim loại nào cũng nhất thiết là nguyên liệu của công thức khác; ở đây kim loại 2 không bao giờ là nguyên liệu.
Test mẫu 3 cho thấy một kim loại có thể được dùng để tạo ra chính nó. Dù luật giả kim đôi khi kỳ quặc, trường hợp này vẫn không thể tạo ra chì. Vì công thức chỉ hoạt động với từng gram nguyên, ta không thể dùng 0,5 gram của kim loại 2 và 3 để tạo 0,5 gram kim loại 4, rồi dùng 0,5 gram kim loại 3 và 4 để tạo 0,5 gram chì.
Nguồn
Google Code Jam 2018, Vòng 1B, bài Transmutation.
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 1B (29 Tháng tư, 2018)
Bình luận