Problem B
Lövsprickning

I Uppsala finns en allé av björkar från olika delar av Sverige, planterade i ordning utifrån deras breddgrad. De sydligaste björkarna, från Ystad, står därför i den södra änden av allén, medan de nordligaste från Kiruna befinner sig i den norra änden. Detta skapar en vacker effekt på hösten då löven på träden från norra Sverige blir gula och faller av före löven från träden i södra Sverige. Detta beror på att det är mörkret – inte kylan – som ger höstlöven färg.

Lara älskar våren och vill observera hur lövsprickningen skiljer sig åt på träd från olika breddgrader. Men till skillnad från allén i Uppsala vill hon maximera kaos. Det är viktigt för henne att inga träd från närliggande breddgrader står bredvid varandra! Hur kan hon plantera träden i en rad för att uppfylla detta krav?

Indata

En rad innehållande ett tal $N$, antalet träd. Träden är numrerade från $0$ till $N-1$, baserat på deras ursprungliga breddgrad – trädet nummer $0$ är det nordligaste, och trädet $N-1$ är det sydligaste.

Utdata

Om det är möjligt att uppfylla ovanstående krav ska du skriva ut $N$ rader med ett heltal var, trädens index i en ordning som följer kraven. Annars ska du skriva ut ”impossible”.

Poängsättning

Din lösning kommer att testas på två olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring

I exempelfall 1 finns det 8 träd. I svaret som visas här är skillnaderna $3, 5, 7, 4, 2, 5$ och $2$ mellan paren av närliggande träd. Eftersom alla skillnader är $2$ eller mer är detta ett godkänt svar.

8

2
5
0
7
3
1
6
4

7

1
4
0
5
2
6
3