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 ca e timpul sa folosească ce a învăţat, anume sa jefuiască o banca. După ce el a făcut partea grea, adică sa ameninţe oamenii din banca cu un pistol de jucărie într-un mod convingător, Jimmy a ajuns la seif. Acum el va roagă sa îl ajutaţi cu deschiderea acestuia.

 

Seiful are inscripţionat pe el un sir de 2^N biţi. Pentru a-l debloca trebuie sa găsiţi o expresie folosindu-va de N variabile de tip boolean, expresie care sa conţină (de oricâte ori) doar: 

 

• aceste variabile

• operatorul ^ (xor) (cu prioritate mica)

• operatorul ~ (not) (cu prioritate mare)

• paranteze deschise si închise (cu prioritate uriaşa)

 

Daca prin concatenarea rezultatelor expresiei pentru fiecare din configuraţiile de 0 si 1 ale fiecărei variabile, in ordine sistematica (verifica exemplul pentru o explicaţie mai detaliata) 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 ≤ 100

• Variabilele din expresie se vor scrie ca N litere mici începând in ordine crescătoare de la litera a.

• Daca pot exista mai multe expresii care sa genereze şirul de 2^N biţi se accepta oricare.

• Nu se garantează faptul ca 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

 

heist.in	heist.out

| 3

 01101001

| 9

 !(!a^b)^c

| 

 

Explicaţie

 

• Când a=0, b=0, c=0 expresie are valoarea 0

• Când a=0, b=0, c=1 expresie are valoarea 1

• Când a=0, b=1, c=0 expresie are valoarea 1

• Când a=0, b=1, c=1 expresie are valoarea 0

• Când a=1, b=0, c=0 expresie are valoarea 1

• Când a=1, b=0, c=1 expresie are valoarea 0

• Când a=1, b=1, c=0 expresie are valoarea 0

• Când a=1, b=1, c=1 expresie are valoarea 1

 

Cum se trimit solutii?