No queremos un tercer acto triste, como dice la canción. Aunque esa es triste; recordemos una alegre.
¿Sabéis qué son las šnenokle? ¿Šufnudle? ¿Pihtije? ¿Knaput?
El señor Malnar lo sabe, pero necesita ayuda con la siguiente tarea:
Se da un número entero positivo par $N$. Un conjunto $S$ de números de $\{0,1,\ldots,2^N-1\}$ es hambriento si los $\binom{|S|}{2}$ resultados de aplicar XOR bit a bit a los pares de elementos del conjunto son todos distintos.
Encontrad un conjunto hambriento lo más grande posible.
Entrada
La única línea de la entrada contiene el número entero positivo $N$ del enunciado.
Salida
En la primera línea, imprimid el número de elementos de vuestro conjunto hambriento.
En la segunda línea, imprimid los elementos del conjunto separados por espacios.
Subtareas
| Subtarea | $N$ | $t_1$ | $t_2$ | $t_3$ | Puntos |
|---|---|---|---|---|---|
| 1 | 18 | 267 | 283 | 512 | 20 |
| 2 | 20 | 444 | 462 | 1024 | 20 |
| 3 | 26 | 2019 | 2040 | 8192 | 20 |
| 4 | 28 | 3295 | 3327 | 16384 | 20 |
| 5 | 30 | 5377 | 5430 | 32768 | 20 |
Si en una subtarea habéis impreso un conjunto hambriento de tamaño $t$, vuestra solución recibirá en esa subtarea una puntuación según la siguiente expresión:
$$ \operatorname{puntos}(t)= \begin{cases} 2.4\cdot\frac{t}{t_1} & t<t_1,\\ 2.4+3.6\cdot\frac{t-t_1}{t_2-t_1} & t_1\le t<t_2,\\ 6+12\cdot\frac{t-t_2}{t_3-t_2} & t_2\le t<t_3,\\ 20 & t_3\le t. \end{cases} $$
La puntuación de cada subtarea se redondeará a dos decimales. La puntuación total será la suma de las puntuaciones de las subtareas y también se redondeará a dos decimales.
Vuestro código fuente puede ocupar como máximo 1 MiB.
Ejemplos
Entrada 1
4
Salida 1
6 0 1 2 4 8 15