Fişierul intrare/ieşire:heist.in, heist.outSursăJunior Challenge 2020
AutorAlexandru Enache, Alexandru PetrescuAdăugată deJuniorChallenge2020Comisia •JuniorChallenge2020
Timp execuţie pe test0.04 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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 2N 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 2N 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 2N 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

heist.inheist.out
3
01101001
9
!(!a^b)^c
4
0000000000000000
15
a^a^b^b^c^c^d^d

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?