Olympic 30/4 2016 - Khối 11 - Bài 1 - Robot táo

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: APROBOT.INP
Output: APROBOT.OUT

Problem source:
Olympic 30/4
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một nhà máy chế biến hoa quả đang chế biến một sản phẩm từ táo. Nhà máy này đã có một dây chuyền sản xuất gồm nhiều công đoạn. Trong đó công đoạn đầu tiên, có ~N~ quả táo với trọng lượng đã biết được đưa ngẫu nhiên lên băng chuyền thành hàng dọc và được đánh số từ ~1~ đến ~N~. Chúng được ngầm phân thành ~M = [N/K]~ đoạn, mỗi đoạn gồm đúng ~K~ quả (~N~ là bội của ~K~). Các đoạn này cũng được đánh số từ ~1~ đến ~M~, kể từ đầu băng chuyền. Do yêu cầu kỹ thuật, chúng cần được sắp xếp lại sao cho:

  • Đoạn ~1~ sẽ gồm ~K~ quả có trọng lượng lớn nhất trong số các quả có mặt trên băng chuyền.

  • Nếu ~M > 1~ thì đoạn thứ ~i (i = 2, ..., M)~ sẽ ~K~ quả táo lớn nhất trong số các quả còn lại (không có mặt trong các đoạn từ ~1~ đến ~i-1~).

Một robot sẽ di chuyển dọc theo băng chuyền để thực hiên yêu cầu kỹ thuật nói trên. Mỗi thao tác của robot sẽ gồm việc rút ra khỏi băng chuyền ~1~ quả táo (các quả còn lại được dồn lại) rồi chèn quả táo này vào vị trí thích hợp trên băng chuyền (bao gồm cả vị trí đầu và cuối dãy).

Yêu cầu: Hãy viết chương trình tính xem cần thực hiện ít nhất bao nhiêu thao tác để xếp lại số táo trên băng chuyền theo đúng yêu cầu kỹ thuật.

Input

Vào từ tệp văn bản APROBOT.INP gồm:

  • Dòng đầu gồm hai số nguyên ~N~ và ~K~ ~(1 \le K \le N \le 5000);~

  • Dòng thứ hai ghi N số nguyên ~W_i~ ~(1 \le W_i \le 1000, i = 1, 2, ..., N)~ là số đơn vị trọng lượng của quả táo ~i~.

Các số trên cũng mỗi hàng đều được ghi cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra tệp văn bản APROBOT.OUT duy nhất một số nguyên, là số thao tác ít nhất robot cần thực hiện.

Scoring

~50\%~ số test ứng với ~50\%~ số điểm của bài có ~(N \le 100)~.

Sample Input 1

6 2
7 3 2 5 9 1

Sample Output 1

2

Sample Input 2

6 2
7 8 9 5 3 5

Sample Output 2

1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.