Problem K
Minröj i kvadrat
Languages
en
sv
Om du inte är bekant med spelet minröj så kommer här en kort beskrivning av situationen:
-
Var och en av de rödmarkerade rutorna är antingen tom eller innehåller en mina. Alla de andra rutorna är tomma.
-
Var och en av rutorna med en blå etta är granne med exakt en mina. Två rutor anses vara grannar om de delar en kant eller ett hörn. Alla rutor som inte är på kanten har alltså $8$ grannar.
Skriv ut vilka av de rödmarkerade rutorna som garanterat inte har en mina.
Indata
Ett heltal, $1 \leq n \leq 1\, 000$, sidlängden på kvadraten. Kvadraten på bilden motsvarar alltså $n = 6$.
Det går att bevisa att det för varje $n$ finns minst en giltig utplacering av minor.
Utdata
Först en rad med ett heltal $m$, antalet säkra rutor. Sedan en rad med $m$ heltal, index på de säkra rutorna i ökande ordning. Rutorna är indexerade från $1$ till $4n+4$ från nedre vänstra hörnet och medurs (som på bilden).
| Sample Input 1 | Sample Output 1 |
|---|---|
3 |
8 1 3 5 7 9 11 13 15 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 |
0 |
