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

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

Syöte

Syötteen ainoalla rivillä on kokonaisluku n.

Tuloste

Tulosta yksi rivi, jolla on n lukua g_1\ g_2\ \dots\ g_n. Luku g_k ilmaisee, mihin joukkoon luku k 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\}, \{4,8\} ja \{2,5,6\} ja summat vastaavasti 11, 12 ja 13.

Esimerkki 2

Syöte:

4

Tuloste:

IMPOSSIBLE

Osatehtävä 1 (22 pistettä)

  • 3 \le n \le 10

Osatehtävä 2 (78 pistettä)

  • 3 \le n \le 100