== include(page="template/taskheader" task_id="heist") ==

== include(page="template/taskheader" task_id="heist") ==

Dupa ce s-a jucat prea mult MFA(Marele Furt Auto), $Jimmy$ a decis ca e timpul sa foloseasca ce a invatat, anume sa jefuiasca o banca. Dupa ce el a facut partea grea, adica sa ameninte oamenii din banca cu un pistol de jucarie intr-un mod convingator, $Jimmy$ a ajuns la seif. Acum el va roaga sa il ajutati cu deschiderea acestuia.

După ce s-a jucat prea mult $MFA (Marele Furt Auto)$, $Jimmy$ a decis că e timpul sa folosească ce a învăţat, anume cum să jefuiască o bancă. După ce el a făcut partea grea, adică să ameninţe oamenii din bancă cu un pistol de jucărie într-un mod convingător, $Jimmy$ a ajuns la seif. Acum el vă roagă să îl ajutaţi cu deschiderea acestuia.

Seiful are inscriptionat pe el un sir de $2^N^$ biti. Pentru a-l debloca trebuie sa gasiti o expresie folosindu-va de $N$ variabile de tip bool, expresie care sa contina (de oricate ori) doar:

Seiful are inscripţionat pe el un şir de $2^N^$ biţi. Pentru a-l debloca trebuie să găsiţi o expresie folosindu-vă de $N$ variabile de tip boolean, expresie care să conţină (de oricâte ori) doar:

* aceste variabile
* operatorul $^$ (xor) (cu prioritate mica)
* operatorul $~$ (not) (cu prioritate mare)
* paranteze deschise si inchise (cu prioritate uriasa)

* aceste variabile
* operatorul $^$ (xor) (cu prioritate mică)
* operatorul $!$ (not) (cu prioritate mare)
* paranteze deschise şi închise (cu prioritate uriaşă)

Daca prin concatenanrea rezultatelor expresiei pentru fiecare din configuratiile de $0$ si $1$ ale fiecarei variabile, in ordine sistematica (verifica exemplul pentru o explicatie mai detaliata) este exact sirul inscriptionat pe seif, atunci $Jimmy$ va deveni un om foarte bogat.

Dacă prin concatenarea rezultatelor expresiei pentru fiecare dintre configuraţiile de $0$ şi $1$ ale fiecărei variabile, în ordine sistematică (verifică exemplul pentru o explicaţie mai detaliată) este exact şirul inscripţionat pe seif, atunci $Jimmy$ va deveni un om foarte bogat. Din păcate, cum viaţa nu este întotdeauna uşoară, se poate să nu existe nicio expresie pentru care seiful să poată fi deschis, caz în care cheia seifului este $-1$.

h2. Date de intrare

h2. Date de intrare

Fişierul de intrare $heist.in$ va contine pe prima linie numarul $N$ cu semnificatia din enunt. Pe urmatoarea linie se va afla sirul de $2^N^$ biti.

Fişierul de intrare $heist.in$ va conţine pe prima linie numărul $N$ cu semnificaţia din enunţ. Pe următoarea linie se va afla şirul de $2^N^$ biţi.

h2. Date de ieşire

h2. Date de ieşire

În fişierul de ieşire $heist.out$ se va afla numarul $S$ reprezentand lungimea expresiei gasite, urmat, pe linia urmatoare, de expresie.

În fişierul de ieşire $heist.out$ se va afla numărul $S$ reprezentând lungimea expresiei găsite, urmat, pe linia următoare, de expresie.

h2. Restricţii

h2. Restricţii

* $1 ≤ N ≤ 20$

* $1 ≤ S ≤ 100$
* Variabilele din expresie se vor scrie ca $N$ litere mici incepand in ordine crescatoare de la litera $a$.
* Daca pot exista mai multe expresii care sa genereze sirul de $2^N^$ biti se accepta oricare.
* Nu se garanteaza faptul ca autorul acestui enunt stie cum functioneaza un seif.
 
h2. Subtaskuri
 
* $**Subtaskul 1 (20 puncte, testele 1-2):**$ $1 ≤ N ≤ 5$
* $**Subtaskul 2 (20 puncte, testele 3-4):**$ $6 ≤ N ≤ 10$
* $**Subtaskul 3 (20 puncte, testele 5-6):**$ $11 ≤ N ≤ 15$
* $**Subtaskul 4 (40 puncte, testele 7-10):**$ $16 ≤ N ≤ 20$
 
h2. Exemplu
 
table(example). |_. heist.in |_. heist.out |
| 3
  01101001

* $1 ≤ S ≤ 500$
* *Daca cheia solutiei este $-1$, atunci se va afisa pe o singura linie valoarea $-1$*.
* Variabilele din expresie se vor scrie ca $N$ litere mici începând în ordine crescătoare de la litera $a$.
* Dacă există mai multe expresii care să genereze şirul de $2^N^$ biţi se acceptă oricare.
* Operaţia $xor$ reprezintă operaţia de disjuncţie exclusivă realizată pe biţii operanzilor. În Pascal, operatorul corespunzător este $xor$, iar în $C/C++$ acest operator este $^$. De exemplu, $20 xor 14 = 26$.
* Nu se garantează faptul că autorul acestui enunţ ştie cum funcţionează un seif.
 
h2. Subtaskuri
 
* $**Subtaskul 1 (20 puncte, testele 1-2):**$ $1 ≤ N ≤ 5$
* $**Subtaskul 2 (20 puncte, testele 3-4):**$ $6 ≤ N ≤ 10$
* $**Subtaskul 3 (20 puncte, testele 5-6):**$ $11 ≤ N ≤ 15$
* $**Subtaskul 4 (40 puncte, testele 7-10):**$ $16 ≤ N ≤ 20$
 
h2. Exemplu
 
table(example). |_. heist.in |_. heist.out |
| 3
  01101001

| 9

  @!(!a^b)^c@
|

@!(!a^b)^c@
|
| 4
  0000000000000000
| 15
@a^a^b^b^c^c^d^d@
|
 
h3. Explicaţie
 
În primul exemplu @!(!a^b)^c@ este o expresie corectă deoarece:
 
* Când $a=0, b=0, c=0$ expresia are valoarea $0$
* Când $a=0, b=0, c=1$ expresia are valoarea $1$
* Când $a=0, b=1, c=0$ expresia are valoarea $1$
* Când $a=0, b=1, c=1$ expresia are valoarea $0$
* Când $a=1, b=0, c=0$ expresia are valoarea $1$
* Când $a=1, b=0, c=1$ expresia are valoarea $0$
* Când $a=1, b=1, c=0$ expresia are valoarea $0$
* Când $a=1, b=1, c=1$ expresia are valoarea $1$

h3. Explicaţie

== include(page="template/taskfooter" task_id="heist") ==

* Cand $a=0, b=0, c=0$ expresie are valoarea $0$
* Cand $a=0, b=0, c=1$ expresie are valoarea $1$
* Cand $a=0, b=1, c=0$ expresie are valoarea $1$
* Cand $a=0, b=1, c=1$ expresie are valoarea $0$
* Cand $a=1, b=0, c=0$ expresie are valoarea $1$
* Cand $a=1, b=0, c=1$ expresie are valoarea $0$
* Cand $a=1, b=1, c=0$ expresie are valoarea $0$
* Cand $a=1, b=1, c=1$ expresie are valoarea $1$
 
== include(page="template/taskfooter" task_id="heist") ==