Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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 
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?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.