CSES - Datatähti 2022 loppu - Lista
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB

On olemassa lista, jossa on n positiivista kokonaislukua. Jokainen luku on suurempi kuin edellinen luku. Luvuissa ei ole etunollia.

Sinulle kerrotaan kuitenkin vain osa lukujen numeroista ja muiden kohdalla on kysymysmerkki. Tehtäväsi on etsiä jokin kuvaukseen sopiva lista tai todeta, että mitään ratkaisua ei ole olemassa.

Syöte

Ensimmäisellä rivillä on kokonaisluku n: lukujen määrä.

Tämän jälkeen tulee n riviä, joista jokainen kuvaa yhden luvun. Jokaisessa luvussa on enintään k numeroa.

Tuloste

Tulosta jokin mahdollinen ratkaisu. Jos ratkaisua ei ole, tulosta vain IMPOSSIBLE.

Esimerkki 1

Syöte:

5
12
??
1??
?5?
???

Tuloste:

12
35
121
150
719

Esimerkki 2

Syöte:

3
98
??
??

Tuloste:

IMPOSSIBLE

Osatehtävä 1 (13 pistettä)

  • 1 \le n \le 100
  • 1 \le k \le 3

Osatehtävä 2 (26 pistettä)

  • 1 \le n \le 1000
  • 1 \le k \le 6

Osatehtävä 3 (61 pistettä)

  • 1 \le n \le 1000
  • 1 \le k \le 9