Xưởng máy
Đề bài
Mô tả
Bạn là giám đốc của Arbitrarily Complex Machines (gọi tắt là ACM), một công ty sản xuất máy móc tiên tiến bằng những máy móc còn tiên tiến hơn. Dây chuyền sản xuất cũ đã hỏng, nên bạn cần mua máy sản xuất mới cho công ty. Mục tiêu của bạn là kiếm được nhiều tiền nhất có thể trong giai đoạn tái cơ cấu. Trong giai đoạn này bạn có thể mua và bán máy, và vận hành chúng để kiếm lời trong thời gian ACM sở hữu chúng. Do hạn chế về mặt bằng, ACM sở hữu nhiều nhất một máy tại mỗi thời điểm.
Trong giai đoạn tái cơ cấu sẽ có một số máy được rao bán. Là chuyên gia của thị trường máy móc, bạn đã biết trước giá và ngày mở bán của từng máy . Nếu bạn không mua máy vào đúng ngày thì người khác sẽ mua nó và về sau nó không còn được bán nữa. Dĩ nhiên bạn không thể mua một máy nếu số tiền ACM đang có nhỏ hơn giá của máy đó.
Nếu mua máy vào ngày thì ACM có thể vận hành nó bắt đầu từ ngày . Mỗi ngày máy được vận hành, nó tạo ra lợi nhuận đô la cho công ty.
Bạn có thể bán một máy để thu hồi một phần giá mua vào bất kỳ ngày nào sau ngày mua nó. Mỗi máy có giá bán lại trên thị trường. Bạn không thể vận hành máy vào ngày bán nó, nhưng có thể bán một máy rồi dùng tiền thu được để mua máy mới ngay trong cùng ngày.
Khi giai đoạn tái cơ cấu kết thúc, ACM sẽ bán máy mà nó còn sở hữu (nếu có). Nhiệm vụ của bạn là cực đại hóa số tiền ACM có được sau giai đoạn tái cơ cấu.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên dương , và : là số máy được rao bán, là số đô la công ty có khi bắt đầu tái cơ cấu, là số ngày của giai đoạn tái cơ cấu.
Mỗi dòng trong dòng tiếp theo mô tả một máy được rao bán, gồm bốn số nguyên , , và : lần lượt là ngày máy được bán, giá mua (đô la), giá bán lại (đô la) và lợi nhuận mỗi ngày khi vận hành máy.
Sau bộ test cuối cùng là một dòng gồm ba số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test và sau đó là số đô la lớn nhất ACM có thể có vào cuối ngày , theo đúng định dạng Case i: x của ví dụ.
Ràng buộc
- , , .
- , , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 10 20 6 12 1 3 1 9 1 2 3 2 1 2 8 20 5 4 4 11 7 4 2 10 9 1 0 0 0 |
Case 1: 44 | Ngày 3 mua máy , còn đô la; vận hành ngày 4, 5 được (có ). Ngày 6 bán máy được (có ) rồi mua máy , còn ; vận hành ngày 7 đến 20 ( ngày) được (có ). Ngày 21 bán máy được : tổng . |
| 3 5 10 2 4 3 1 5 6 2 3 8 20 1 10 1 10 3 2 8 1 1 0 0 0 |
Case 1: 17 Case 2: 10 |
Bộ 1: ngày 2 mua máy giá (còn ), vận hành ngày 3, 4 (có ); ngày 5 bán được (có ) và mua máy giá (còn ); vận hành ngày 6 đến 10 được , ngày 11 bán được : tổng . Máy giá không bao giờ mua nổi. Bộ 2: nếu mua máy vào ngày 2 thì tới ngày 4 chỉ có , nên tốt nhất là không mua gì. |
Bình luận