Masala #PONTAPZBVJ
Qism massivlarga ajratish
Sardorda ta butun sondan iborat massiv bor . Sardor massivni bir nechta uzluksiz va o'zaro kesishmaydigan qism massivlarga ajratmoqchi, boshqacha so'zlar bilan aytganda har bir element aynan bitta qism massivda bo'lishi va har bir qism massiv kamida 1 ta elementdan iborat bo'lishi lozim.
Uning do'sti Farrux ajratilgan har bir qism massivning faqat birinchi elementiga qiziqadi, va uning norozilik darajasi ushbu qism massivlarning turli xil birinchi elementlarining soniga teng (turlilar soni).
Bundan tashqari, Farrux Sardoga ta shart bergan:
- Har bir shart va qiymatlaridan iborat – shu va oraliqdagi birorta elementdan boshlangan kamida 1 ta qism massiv bo'lishi kerak.
Sardor Farruxning noroziligini minimallashtiradigan va barcha ta shartlarni qanoatlantiradigan qism-massivlarga bo'lish usulini topishi kerak. Unga yordam bering!
Birinchi qatorda va – mos ravishda massivnig uzunligi va Farrux bergan shartlar soni.
Keyingi qatorda ta elementdan iborat massiv elementlari.
Keyingi ta qatorning har birida ikkita butun son - shartlarning parametrlari kiritiladi.
Birinchi qatorda minimal norozilik darajasini va massivning necha bo'lakka bo'linganligini ni chop eting.
Keyingi qatorda uzunligi ta elementdan iborat, optimal bo'linishni tasvirlovchi massivni chiqaring.
Shu massivni way deb olaylik.
- – -qismmassivning birinchi elementi indexiga teng bo'lsin.
- va bo'lsin
Agar optimal bo'lish bir nechta bo'lsa istalganini chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
3 2 1 2 3 1 2 3 3 |
2 2 1 3 |
2 |
5 2 1 2 0 0 1 2 3 4 5 |
2 3 1 2 5 |
3 |
5 5 1 2 0 0 1 1 1 2 2 3 3 4 4 5 5 |
3 5 1 2 3 4 5 |