CSES - Datatähti 2021 loppu - Kolmijako
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tehtäväsi on jakaa luvut 1,2,,n1,2,\dots,n kolmeen joukkoon niin, että joukon 22 lukujen summa on yhden suurempi kuin joukon 11 lukujen summa ja yhden pienempi kuin joukon 33 lukujen summa.

Syöte

Syötteen ainoalla rivillä on kokonaisluku nn.

Tuloste

Tulosta yksi rivi, jolla on nn lukua g1 g2  gng_1\ g_2\ \dots\ g_n. Luku gkg_k ilmaisee, mihin joukkoon luku kk kuuluu.

Jos ratkaisua ei ole olemassa, tulosta IMPOSSIBLE.

Esimerkki 1

Syöte:

8

Tuloste:

1 3 1 2 3 3 1 2

Selitys: Tässä ratkaisussa joukot ovat {1,3,7}\{1,3,7\}, {4,8}\{4,8\} ja {2,5,6}\{2,5,6\} ja summat vastaavasti 1111, 1212 ja 1313.

Esimerkki 2

Syöte:

4

Tuloste:

IMPOSSIBLE

Osatehtävä 1 (22 pistettä)

  • 3n103 \le n \le 10

Osatehtävä 2 (78 pistettä)

  • 3n1003 \le n \le 100