Masala #ZOO3ZP80LC
Masala yechishlar soni
Qoravoy dasturlash musobaqasida qatnashadi. Musobaqada \(n\) ta masala bor va har bir masalaning qiyinligi \(a_1,a_2,…,a_n\) bilan berilgan. Qoravoy faqat o‘zining mahorati k ga teng yoki undan kichik bo‘lgan masalalarni yechishi mumkin. U har doim masalalarni listning ikki uchidan biridan yechadi (yoki chapdan, yoki o‘ngdan). Maqsad, Qoravoy qaysi masalalarni yecha olishiga qarab, maksimal yechilgan masalalar sonini aniqlash.
Qoravoy \(k\) dan katta qiyinchilikka ega bo‘lgan masalani yecha olmaydi. Qoravoy masalani yechganidan so‘ng, u masala ro‘yxatdan o‘chadi, ya'ni ro‘yxat uzunligi 1 taga kamayadi. Qoravoy ro‘yxatning har ikki uchidan ham yechishga qodir bo‘lmagan masalani uchratganida to‘xtaydi.
Birinchi qatorda ikki butun son \(n\) va \(k\) berilgan (\(1≤n,k≤100\)) — bu musobaqadagi masalalar soni va Qoravoyning masalani yechish qobiliyati.
Ikkinchi qatorda n ta butun son va \(a_1, a_2, \dots, a_n(1 \leq a_i \leq 100)\) berilgan , bu yerda \(a_i\) \(i\)-chi masalaning qiyinchiligidir. Masalalar ro‘yxati chapdan o‘ngga qarab berilgan.
Qoravoy musobaqada maksimal qancha masalani yechishi mumkinligini hisoblash kerak.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
8 4 4 2 3 1 5 1 6 4 |
5 |
| 2 |
5 2 3 1 2 1 3 |
0 |
| 3 |
5 100 12 34 55 43 21 |
5 |
Birinchi testda, Qoravoy masalalarni quyidagi tartibda yechishi mumkin:
[4,2,3,1,5,1,6,4] → [2,3,1,5,1,6,4] → [2,3,1,5,1,6] → [3,1,5,1,6] → [1,5,1,6] → [5,1,6].
Shunday qilib, yechilgan masalalar soni 5 ta bo‘ladi.
Ikkinchi testda, Qoravoy hech bir masalani yecha olmaydi, chunki har ikkala tomondagi masalalarning qiyinchilik darajasi k dan katta.
Uchinchi testda, Qoravoyning yechish mahorati juda yuqori bo‘lib, u barcha masalalarni yechishi mumkin.
Telegram kanalimizga obuna bo'ling