| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
TAYTRUC - Đường lên Tây Trúc |
Một hành giả (nhà tu hành) muốn đến được Tây Trúc cần lần lượt thỉnh hết N ngôi chùa (các
ngôi chùa được đánh số từ 1 đến N theo trình tự thỉnh) đồng thời phải trút bỏ hết số hồ lô mang trên
người sau khi thỉnh hết N ngôi chùa đó và tích lũy được càng nhiều càng tốt số hạt xá lợi khi kết thúc
hành trình. Tại mỗi ngôi chùa đều đặt một hồ lô có chứa một số nào đó các hạt xá lợi: hồ lô ở ngôi
chùa i có chứa X
i
hạt.
Xuất phát từ ngôi chùa 1 (trước khi xuất phát, hành giả không có hồ lô nào mang trên người),
mỗi khi đặt chân đến một ngôi chùa i hành giả có thể có một trong hai lựa chọn:
Lấy quả hồ lô ở đó và được thu giữ toàn bộ xá lợi có trong hồ lô. Trường hợp này
khiến hành giả phải mang theo trên người hồ lô này để tiếp tục hành trình.
Bỏ qua, không lấy quả hồ lô đó. Trường hợp này khiến hành giả không lấy được số xá
lợi có trong hồ lô.
Việc lấy thêm hoặc trút bỏ bớt hồ lô phải tuân theo quy tắc nghiêm ngặt sau đây.
Khi đang thỉnh tại chùa i (1 ≤ i ≤ N) và số hồ lô đang mang trên người là K (K ≥ 0) thì:
1. Trong mọi tình huống, hành giả được quyền không lấy hồ lô tại đây nếu muốn.
2. Hành giả chỉ được lấy thêm hồ lô tại đây khi một trong hai trường hợp sau xảy ra:
- Trường hợp 1: K = 0 ;
- Trường hợp 2: 0 < K < M và trước đó, tại chùa i -1 hành giả có lấy hồ lô.
3. Hành giả chỉ được bỏ bớt đúng một hồ lô mang trên người khi K > 0 đồng thời tại chùa
này hành giả đã không lấy hồ lô.
(Như vậy, nếu tại chùa i hành giả không lấy hồ lô và số hồ lô đang mang trên người là K thì
hành giả được trút bỏ bớt 1 hồ lô tại đây nhưng nếu K > 1 thì hành giả không được lấy hồ lô
tại K-1 chùa tiếp theo để trút bỏ hết K-1 hồ lô đó rồi mới có thể tiếp tục lấy thêm hồ lô (nếu
còn và nếu muốn)).
Yêu cầu: Xác định số S, là số nhiều nhất hạt xá lợi mà hành giả có thể thu được sau khi đến được
Tây Trúc.
Dữ liệu: Đọc từ file văn bản TAYTRUC.INP, có cấu trúc:
Dòng đầu ghi lần lượt 2 số nguyên N và M (2 ≤ N ≤ 10000; 1 ≤ M ≤ 500);
N dòng tiếp theo, mỗi dòng ghi một số nguyên dương: dòng i+1 ghi số Xi
, (Xi ≤ 1000).
Kết quả: Ghi ra file văn bản TAYTRUC.OUT duy nhất số nguyên S tìm được.
Ví dụ:
TAYTRUC.INP TAYTRUC.OUT
9 4
1
9
8
3
4
9
8
9
7
35
Giải thích: Hành giả sẽ lấy hồ lô tại các chùa 2, 3, 6, 8.
Một hành giả (nhà tu hành) muốn đến được Tây Trúc cần lần lượt thỉnh hết N ngôi chùa (các
ngôi chùa được đánh số từ 1 đến N theo trình tự thỉnh) đồng thời phải trút bỏ hết số hồ lô mang trên
người sau khi thỉnh hết N ngôi chùa đó và tích lũy được càng nhiều càng tốt số hạt xá lợi khi kết thúc
hành trình. Tại mỗi ngôi chùa đều đặt một hồ lô có chứa một số nào đó các hạt xá lợi: hồ lô ở ngôi
chùa i có chứa Xi hạt.
Xuất phát từ ngôi chùa 1 (trước khi xuất phát, hành giả không có hồ lô nào mang trên người),
mỗi khi đặt chân đến một ngôi chùa i hành giả có thể có một trong hai lựa chọn :
- Lấy quả hồ lô ở đó và được thu giữ toàn bộ xá lợi có trong hồ lô. Trường hợp này
khiến hành giả phải mang theo trên người hồ lô này để tiếp tục hành trình.
- Bỏ qua, không lấy quả hồ lô đó. Trường hợp này khiến hành giả không lấy được số xá
lợi có trong hồ lô.
Việc lấy thêm hoặc trút bỏ bớt hồ lô phải tuân theo quy tắc nghiêm ngặt sau đây :
Khi đang thỉnh tại chùa i (1 ≤ i ≤ N) và số hồ lô đang mang trên người là K (K ≥ 0) thì:
1. Trong mọi tình huống, hành giả được quyền không lấy hồ lô tại đây nếu muốn.
2. Hành giả chỉ được lấy thêm hồ lô tại đây khi một trong hai trường hợp sau xảy ra:
- Trường hợp 1 : K = 0
- Trường hợp 2 : 0 < K < M và trước đó, tại chùa i -1 hành giả có lấy hồ lô
3. Hành giả chỉ được bỏ bớt đúng một hồ lô mang trên người khi K > 0 đồng thời tại chùa
này hành giả đã không lấy hồ lô.
(Như vậy, nếu tại chùa i hành giả không lấy hồ lô và số hồ lô đang mang trên người là K thì
hành giả được trút bỏ bớt 1 hồ lô tại đây nhưng nếu K > 1 thì hành giả không được lấy hồ lô
tại K-1 chùa tiếp theo để trút bỏ hết K-1 hồ lô đó rồi mới có thể tiếp tục lấy thêm hồ lô (nếu
còn và nếu muốn)).
Yêu cầu : Xác định số S, là số nhiều nhất hạt xá lợi mà hành giả có thể thu được sau khi đến được
Tây Trúc
Dữ liệu vào :
- Dòng đầu ghi lần lượt 2 số nguyên N và M (2 ≤ N ≤ 10000; 1 ≤ M ≤ 500)
- N dòng tiếp theo, mỗi dòng ghi một số nguyên dương: dòng i+1 ghi số Xi (Xi ≤ 1000)
Kết quả: Ghi ra duy nhất số nguyên S tìm được
Ví dụ:
Input :
9 4
1
9
8
3
4
9
8
9
7
Output :
35
Giải thích : Hành giả sẽ lấy hồ lô tại các chùa 2, 3, 6, 8
| Được gửi lên bởi: | Kata |
| Ngày: | 2014-04-14 |
| Thời gian chạy: | 0.200s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED |
| Nguồn bài: | Olympic 30/4/2014 Tp.Hồ Chí Minh |
hide comments
|
2021-05-27 18:03:59
Tham khảo: https://vnspoj.github.io/problems/TAYTRUC |
|
|
2015-02-13 04:50:12 Nguyễn Tấn Phát
Last edit: 2016-12-26 03:35:10 |
|
|
2015-01-27 06:24:34 Kakabalo
add 2014 mays chaams pyramid @@ |
|
|
2014-11-30 15:40:48 Lương Ðức Tuấn Ðạt
Copy đề USACO à =)) |
|
|
2014-09-18 14:30:29 hận ðời không ðối thủ
QHĐ cơ bản la\ ac |
|
|
2014-09-17 18:49:05 Thcs Ðặng Chánh Kỷ
cũng bình thường mà sao không thấy ai sub bài này |
|
|
2014-04-22 14:45:29 Nắng
20 điểm là sai test nào vậy? |
RSS