Fişierul intrare/ieşire:	heist.in, heist.out	Sursă	Junior Challenge 2020
Autor	Alexandru Enache, Alexandru Petrescu	Adăugată de	Comisia •JuniorChallenge2020
Timp execuţie pe test	0.04 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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 mică)
• operatorul ! (not) (cu prioritate mare)
• paranteze deschise şi închise (cu prioritate uriaşă)

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.

Date de intrare

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.

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.

Restricţii

• 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.

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

Exemplu

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

Cum se trimit solutii?