Nous ne voulons pas d'un troisième acte triste, comme le dit aussi la chanson. Celle-là est triste, toutefois ; souvenons-nous d'une chanson joyeuse.
Savez-vous ce que sont les šnenokle ? Les šufnudle ? Les pihtije ? Le Knaput ?
Monsieur Malnar le sait, mais il a besoin d'aide pour la tâche suivante :
On vous donne un entier naturel pair $N$. Un ensemble $S$ de nombres appartenant à $\{0,1,\ldots,2^N-1\}$ est affamé si les $\binom{|S|}{2}$ XOR bit à bit des paires d'éléments de l'ensemble sont tous distincts. Trouvez un ensemble affamé aussi grand que possible.
Entrée
L'unique ligne de l'entrée contient l'entier naturel $N$ de l'énoncé.
Sortie
Sur la première ligne, affichez le nombre d'éléments de votre ensemble affamé.
Sur la deuxième ligne, affichez les éléments de l'ensemble séparés par des espaces.
Sous-tâches
| Sous-tâche | $N$ | $t_1$ | $t_2$ | $t_3$ | Points |
|---|---|---|---|---|---|
| $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 vous avez affiché un ensemble affamé de taille $t$ pour une sous-tâche, votre solution recevra pour cette sous-tâche le nombre de points donné par l'expression suivante :
$$ \operatorname{points}(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} $$
Le nombre de points de chaque sous-tâche sera arrondi à deux décimales. Le nombre total de points sera la somme des points des sous-tâches et sera lui aussi arrondi à deux décimales.
Votre code source peut avoir une taille maximale de 1 MiB.
Exemples
Entrée 1
4
Sortie 1
6 0 1 2 4 8 15