Baltic Olympiad in Informatics 2018 - day 1

Start

2018-04-28 07:00 UTC

Baltic Olympiad in Informatics 2018 - day 1

End

2018-04-28 12:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -226 days 0:29:56

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Marsi DNA

Nagu sa ilmselt tead, saab inimese DNA esitada pika stringina, kus esineb vaid neli erinevat tähte (A, C, G, T) ja iga sümbol vastab erinevale nukleotiidile (adeniin, tsütosiin, guaniin ja tümiin).

Marslastel käivad asjad aga veidi teisiti: uuringud näitavad, et viimasel NASA poolt kinni püütud marslasel on tervelt $K$ erinevat nukleotiidi! Seega saab marslase DNA esitada kui stringi, mille märgid on tähestikust suurusega $K$.

Nüüd uurib grupp teadlasi, kuidas kasutada marslaste DNA-d tehisintellektirakendustes ja neil on vaja marslase DNA näidist. Täpsemalt on nad öelnud $R$ nukleotiidi kohta, mis on minimaalne arv, kui palju vastavat nukleotiidi peab näidises olema.

Sul on vaja leida lühim võimalik nõuetele vastav DNA alamstring.

Input

Sisendi esimesel real on kolm täisarvu $N$, $K$ ja $R$, mis tähistavad vastavalt marslase DNA täielikku pikkust, tähestiku suurust ning nende nukleotiidide arvu, millele rakendub minimaalse arvu nõue. Kehtib reegel $1 \le R \le K \le N$.

Teisel real on $N$ tühikutega eraldatud täisarvu, mis kirjeldavad täielikku marslase DNA järjendit. $i$-s arv $D_ i$ tähistab, milline nukleotiid on marslase DNA-s $i$-ndal kohal. Nukleotiidide loendamine algab nullist, s.t $0 \leq D_ i < K$. Iga nukleotiidi esineb vähemalt üks kord.

Järgmistel $R$ real on igaühel kaks täisarvu $B$ ja $Q$, mis tähistavad nukleotiidi ja selle minimaalset soovitud hulka ($0 \le B < K, 1 \le Q \le N$). Ükski nukleotiid ei esine rohkem kui üks kord.

Output

Väljastada üks täisarv, lühima nõuetele vastava DNA alamstringi pikkus. Kui sellist alamstringi pole, väljastada “impossible”.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

1

16

$1 \le N \le 100, R \le 10$

2

24

$1 \le N \le 4\, 000, R \le 10$

3

28

$1 \le N \le 200\, 000, R \le 10$

4

32

$1 \le N \le 200\, 000$

Explanation of Samples

Esimeses näites leidub kolm alamstringi pikkusega $2$, mis kõik sisaldavad ühe nukleotiidi 0 ja ühe 1 (täpsemalt “0 1”, “1 0” ja “0 1”), aga ei leidu ühtki alamstringi pikkusega $1$. Lühim pikkus on seega $2$.

Teises näites on (ainus) optimaalne alamstring “1 3 2 0 1 2 0”.

Kolmandas näites pole piisavalt 0-tüüpi nukleotiide.

Sample Input 1 Sample Output 1
5 2 2
0 1 1 0 1
0 1
1 1
2
Sample Input 2 Sample Output 2
13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2
7
Sample Input 3 Sample Output 3
5 3 1
1 2 0 1 2
0 2
impossible