K - Không đơn độc

View as PDF

Submit solution

Points: 1.13 (partial)
Time limit: 0.9s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Online Informatics Olympiad '09Day 2
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một dãy số được gọi là ~K~--không đơn độc nếu mỗi phần tử của dãy đều thuộc một đoạn gồm ít nhất ~K~ phần tử liên tiếp có giá trị giống nhau. Ví dụ dãy ~[1, 1, 2, 2, 2, 1, 1]~ là ~2~--không đơn độc , nhưng không phải là ~3~--không đơn độc vì phần tử đầu tiên chỉ thuộc một đoạn gồm ~2~ số ~1~. Nếu một dãy số chưa phải là ~K~--không đơn độc , bạn có quyền thực hiện các thao tác biến đổi, mỗi thao tác sẽ cộng (hoặc trừ) một đơn vị vào một phần tử của dãy. Hãy đếm số thao tác ít nhất cần thực hiện để biến một dãy số thành dãy ~K~--không đơn độc .

Input

  • Dòng đầu ghi ~2~ số ~N~, ~K~. ~N~ là số lượng phần tử của dãy số.
  • Dòng sau ghi ~N~ số tự nhiên thể hiện dãy số.

Output

  • Gồm một dòng duy nhất ghi ra số thao tác cần thực hiện.

Giới hạn

  • ~1 \leq N \leq 10000~
  • ~1 \leq K \leq 100~
  • ~K \leq N~
  • Phần tử của dãy có giá trị không quá ~10^{9}~

  • Có ~30\%~ số test thỏa mãn ~N \leq 200~.

  • Có ~50\%~ số test thỏa mãn ~N \leq 2000~.

Sample Input

7 3
2 2 3 4 4 5 5

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.