== include(page="template/taskheader" task_id="heist") ==
== include(page="template/taskheader" task_id="heist") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
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:
Fişierul de intrare $heist.in$ ...
* aceste variabile
* operatorul $^$ (xor) (cu prioritate mică)
* operatorul $!$ (not) (cu prioritate mare)
* paranteze deschise şi închise (cu prioritate uriaşă)
h2. Date de ieşire
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$.
În fişierul de ieşire $heist.out$ ...
h2. Date de intrare
h2. Restricţii
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. Exemplu
Î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.
table(example). |_. heist.in |_. heist.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h2. Restricţii
h3. Explicaţie
* $1 ≤ N ≤ 20$
* $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
== include(page="template/taskfooter" task_id="heist") ==
* $**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@
|
| 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$
== include(page="template/taskfooter" task_id="heist") ==
