| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 13 | 6 | 6 | 50.000% |
Bitlandijoje tuoj prasidės visų ilgai lauktas koncertas, kuriame gros žymi vietinė grupė „Bitlai“. Koncertą susirinko stebėti N žmonių, o koncerto salė tokia, kad žiūrovai vorele stovi vienas už kito. T. y. pirmas žiūrovas stovi prie pat scenos, už jo stovi antras žiūrovas, už antro – trečias ir t. t. i-to eilėje stovinčio žmogaus ūgis yra ui Bitlandijos metrų, o sceną žiūrovai gali matyti tik tuo atveju, jei visi prieš juos stovintys žmonės griežtai žemesni.
Organizatoriai apie tai nepagalvojo, ir turi tik K vieno Bitlandijos metro aukščio kėdučių, kurias gali išdalinti žiūrovams. Ant vienos kėdutės gali atsistoti tik vienas žiūrovas ir vienam žiūrovui gali tekti daugiausiai viena kėdutė. Žiūrovui atsistojus ant kėdutės galima tarti, kad jo ūgis padidėja vienu Bitlandijos metru. Tuomet gali būti taip, kad šis galės matyti sceną, bet ją užstos už jo stovintiems žiūrovams.
Raskite, kiek daugiausiai žiūrovų galės matyti sceną, jei kėdutės bus išdalintos optimaliai.
Pirmoje eilutėje pateikti du tarpu atskirti sveikieji skaičiai – žiūrovų skaičius N ir kėdučių skaičius K.
Antroje eilutėje pateikta N tarpais atskirtų sveikųjų skaičių ui, žyminčių žiūrovų ūgius jų stovėjimo salėje tvarka.
Išveskite vieną sveikąjį skaičių – kiek daugiausiai žiūrovų galės matyti koncertą optimaliai išdalijus kėdutes.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 22 | Visų žiūrovų ūgiai skirtingi |
| 2 | 15 | K = 1, N ≤ 1 000 |
| 3 | 28 | K = 2, N ≤ 100 |
| 4 | 12 | N ≤ 20 |
| 5 | 23 | Papildomų ribojimų nėra |
5 3 3 2 3 2 5
3
Iš pat pradžių sceną mato pirmas ir penktas žiūrovai (1 pav.). Davus kėdutę žiūrovui nr. 3 sceną matys: pirmas, trečias ir penktas (2 pav.).
Papildomos kėdutės niekaip nepadės padidinti sceną matančių žiūrovų skaičių.
1 pav.
2 pav.
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2020/2021 > National Round (2) > 7-9 Classes 4번