DICE - Đổ xúc xắc
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: mrtan_lovelife

Misaki và bạn của cô đang chơi một trò chơi đổ xúc xắc, trò chơi như sau: Cho 1 dãy các ô được đánh số từ 1 đến N, mỗi ô mang một giá trị nhất định. Bắt đầu từ vị trí 0 với số điểm là 0, người chơi sẽ đổ xúc xắc có K mặt được đánh số từ 1 đến K, khi xúc xắc ngừng quay, số chỉ trên mặt xúc xắc chính là số bước mà người chơi sẽ tiến tới, người chơi đi đến ô i thì sẽ được thêm ai điểm, người chơi có thể dừng đổ bất kì lúc nào. Do Misaki có biệt tài đổ xúc xắc ra số chỉ như ý muốn nên trò chơi này không làm khó được cô, vấn đề là cô không biết nên đổ xúc xắc thế nào để đạt số điểm cao nhất, bạn hãy lập trình giúp cô ấy nhé! wink

Yêu cầu: Cho số K và dãy các ô cùng với giá trị của chúng, bạn hãy tìm cách đổ xúc xắc sao cho khi dừng cuộc chơi, người chơi đạt số điểm cao nhất.

Dữ liệu vào:

  - Dòng thứ nhất chứa 2 số nguyên N, K là số lượng ô và số mặt của xúc xắc (1 ≤ N,K ≤ 105).

  - Dòng thứ hai chứa N số, số ai là giá trị của ô thứ i (|ai| ≤ 109).

Dữ liệu ra:

  - Dòng thứ nhất chứa 1 số nguyên duy nhất là số điểm lớn nhất đạt được.

  - Ở dòng thứ hai, số M đầu tiên là số các ô đi qua, sau đó là M số bắt đầu từ 0 cho biết các ô đi qua theo thứ tự tăng dần. Nếu có nhiều cách đi, chỉ cần in ra 1 cách bất kì.

Ví dụ

  • input
    5 2
    1 -1 2 -5 3
    output
    6
    4 0 1 3 5
Back to Top