| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 6 | 6 | 6 | 100.000% |
Nicolas vill börja tävla i programmering på hemsidan kodkraft\texttrademark. Det finns jättemånga olika divisioner man kan tävla i, men eftersom Nicolas är en ny deltagare på kodkraft™ så måste han börja i den lägsta divisionen (division 1). Nicolas mål är att så snabbt som möjligt komma upp till högsta divisionen (division $K$) och vinna en tävling i den.
Enligt kodkrafts™ regler får man bara gå upp en division per tävling, så han kommer behöva göra minst en tävling i varje division. Nicolas är dock väldigt självsäker och tror därför att han kommer behöva göra exakt en tävling i varje division för att gå upp till nästa division. När det är tävling på kodkraft™ så är det bara en division i taget som tävlar, och två tävlingar överlappar aldrig i tiden. Tävlingarna följer dessutom samma schema varje år.
Nicolas får påbörja sitt tävlande på kodkraft™ vilket datum på året han vill. Det Nicolas menar med så snabbt som möjligt är att så få tävlingar som möjligt ska gå på kodkraft™ (oavsett om han deltar i dessa eller inte) mellan den första tävling han deltar i, och den första vinsten Nicolas har i den högsta divisionen. Hjälp Nicolas att beräkna hur många tävlingar som krävs!
Den första raden innehåller två heltal $N$ och $K$ (1ドル \leq K \leq N \leq 10^6$), antalet tävlingar per år, samt antalet divisioner.
Därefter kommer en rad med $N$ heltal $x_1, \dots, x_N,ドル (1ドル \leq x_i \leq K$), schemat för tävlingarna under ett år. $x_i$ är divisionen som tävlar under den $i$:te tävlingen efter nyår. Varje division mellan 1ドル$ och $K$ har minst en tävling under året.
Ett heltal, det minsta antalet tävlingar som behöver gå på kodkraft™ från det att han börjar tävla där tills han har vunnit division $K$.
3 3 3 2 1
5
3 2 1 1 2
2
7 5 2 1 1 4 3 2 5
19
Det snabbaste sättet för Nicolas att nå sitt mål är genom att låta sin första tävling vara den andra för division 1 under året. Sen väntar han i fyra tävlingar för att sedan delta i den första tävlingen för division 2 året efter. Sen väntar han tre tävlingar och tävlar i division 3. Sen väntar han i fem tävlingar och tävlar i division 4. Sen väntar han i 2 tävlingar för att vinna division 5. Totalt krävs det 1ドル+(4+1)+(3+1)+(5+1)+(2+1) = 19$ tävlingar.
Olympiad > Swedish Olympiad in Informatics > 2019 > Final C번