Heist

heist

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

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

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.

Poveste şi cerinţă...

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:

h2. Date de intrare

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

Fişierul de intrare $heist.in$ ...

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 ieşire

h2. Date de intrare

În fişierul de ieşire $heist.out$ ...

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. Restricţii

h2. Date de ieşire

* $... ≤ ... ≤ ...$

Î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. Exemplu

h2. Restricţii

table(example). |_. heist.in |_. heist.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

* $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.

h3. Explicaţie

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@
|
| 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") ==
 
 

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