Problem F
Kodkraft
Languages
en
ja
sv
Nicolas vill börja tävla i programmering på hemsidan kodkraft™. 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!
Indata
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.
Utdata
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$.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$15$ |
$N \leq 10^2$ |
|
$2$ |
$20$ |
$N \leq 10^3$ |
|
$3$ |
$25$ |
$N = K$ |
|
$4$ |
$40$ |
Inga ytterligare begränsningar |
Förklaring av exempelfall 3
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.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 3 2 1 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 1 1 2 |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 5 2 1 1 4 3 2 5 |
19 |
