== include(page="template/taskheader" task_id="heist") ==
== include(page="template/taskheader" task_id="heist") ==
Dupa ce s-a jucat prea multa MFA(Marele Furt Auto), $Jimmy$ a decis ca e timpul sa recurga la ultima solutie, jefuirea unei banci. 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") ==
