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

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

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