Google Code Jam 2013 - Manage your Energy
Xem PDFBạn có một lịch trình làm việc rất bận rộn vào ngày hôm nay, với đầy những hoạt động quan trọng cần thực hiện. Bạn đã chuẩn bị kỹ lưỡng để đảm bảo các hoạt động không bị chồng chéo. Bây giờ là buổi sáng, và bạn lo lắng rằng dù rất nhiệt huyết, bạn có thể không đủ năng lượng để hoàn thành tất cả các công việc với sự tập trung cao nhất.
Bạn sẽ phải quản lý năng lượng của mình một cách cẩn thận. Bạn bắt đầu ngày mới với mức năng lượng tối đa là \(E\) joules. Bạn biết rằng mình không thể để năng lượng xuống dưới 0 joules, nếu không bạn sẽ kiệt sức. Bạn có thể dành một lượng năng lượng là số nguyên không âm cho mỗi hoạt động (bạn có thể dành 0 joules nếu cảm thấy lười biếng). Sau mỗi hoạt động, bạn sẽ hồi phục lại \(R\) joules năng lượng. Tuy nhiên, dù bạn có lười biếng đến đâu, bạn không bao giờ có thể có nhiều hơn \(E\) joules năng lượng tại bất kỳ thời điểm nào; bất kỳ lượng năng lượng hồi phục nào vượt quá mức đó đều bị lãng phí.
Một số hoạt động (như giải các bài tập Code Jam) quan trọng hơn những hoạt động khác. Đối với hoạt động thứ \(i\), bạn có một giá trị \(v_i\) thể hiện mức độ quan trọng của hoạt động đó. Giá trị thu được từ mỗi hoạt động là tích của giá trị hoạt động đó với lượng năng lượng bạn đã bỏ ra (tính bằng joules). Bạn muốn quản lý năng lượng của mình sao cho tổng giá trị thu được là lớn nhất.
Lưu ý rằng bạn không thể thay đổi thứ tự các hoạt động trong lịch trình. Bạn chỉ cần quản lý năng lượng tốt nhất có thể với lịch trình đã có.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo, mỗi bộ gồm hai dòng:
- Dòng đầu tiên chứa ba số nguyên: \(E\), lượng năng lượng tối đa (và ban đầu), \(R\), lượng năng lượng hồi phục sau mỗi hoạt động, và \(N\), số lượng hoạt động được lập kế hoạch trong ngày.
- Dòng thứ hai chứa \(N\) số nguyên \(v_i\), mô tả giá trị của các hoạt động đã lập kế hoạch.
Dữ liệu ra
Đối với mỗi bộ thử nghiệm, xuất một dòng chứa "Case #\(x\): \(y\)", trong đó \(x\) là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và \(y\) là tổng giá trị lớn nhất bạn có thể đạt được.
Ràng buộc
- \(1 \le T \le 100\).
Phân nhóm
- Tập thử nghiệm 1 (Small):
- \(1 \le E \le 5\).
- \(1 \le R \le 5\).
- \(1 \le N \le 10\).
- \(1 \le v_i \le 10\).
- Tập thử nghiệm 2 (Large):
- \(1 \le E \le 10^7\).
- \(1 \le R \le 10^7\).
- \(1 \le N \le 10^4\).
- \(1 \le v_i \le 10^7\).
Đ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 | 12/35 | 34,29% |
| Test Set 2 | 23/35 | 65,71% |
Ví dụ
Ví dụ 1
Input
3
5 2 2
2 1
5 2 2
1 2
3 3 4
4 1 3 5Output
Case #1: 12
Case #2: 12
Case #3: 39Note
- Trong trường hợp đầu tiên, chúng ta có thể dành toàn bộ 5 joules năng lượng cho hoạt động đầu tiên (thu được \(5 \times 2 = 10\)), hồi phục 2 và dành chúng cho hoạt động thứ hai (\(2 \times 1 = 2\)). Tổng cộng là 12.
- Trong trường hợp thứ hai, chúng ta dành 2 joules cho hoạt động đầu tiên, hồi phục lại chúng, và dành 5 joules cho hoạt động thứ hai.
- Trong trường hợp thứ ba, tốc độ hồi phục bằng với năng lượng tối đa, nghĩa là chúng ta luôn hồi phục đầy năng lượng sau mỗi hoạt động - vì vậy chúng ta có thể dành trọn 3 joules cho mỗi hoạt động.
Nguồn
Google Code Jam 2013, Vòng 1A, bài Manage your Energy.
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 2013 - Round 1A (27 Tháng tư, 2013)
Bình luận