Hide

Problem K
Minröj i kvadrat

Languages en sv
/problems/minrojikvadrat/file/statement/sv/img-0001.png
Du spelar minröj, och har hamnat i situationen som bilden visar, med en $n\times n$ -kvadrat kantad av ettor, och okända rutor runt om. Din uppgift är att bestämma vilka av de $4n+4$ omkringliggande rutorna som är garanterat fria från minor.

Om du inte är bekant med spelet minröj så kommer här en kort beskrivning av situationen:

  1. Var och en av de rödmarkerade rutorna är antingen tom eller innehåller en mina. Alla de andra rutorna är tomma.

  2. 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