Fişierul intrare/ieşire:vitraliu.in, vitraliu.outSursăad-hoc
AutorCristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Vitraliu (clasa a 6-a)

Trolilor le plac culorile. Ei creează vitralii, adică sticle cu pătrăţele de diverse culori. Toate vitraliile sunt sticle de formă pătrată cu pătrăţele colorate aranjate în N linii şi N coloane. Branch, mai morocănos din fire, a creat două vitralii N ori N, doar cu pătrăţele albe (transparente) şi gri. Ele au o proprietate interesantă: când le suprapui, două pătrăţele gri suprapuse se vor vedea ca un pătrăţel negru!

Cerinţă

Poppy vrea să ştie cum să suprapună cele două vitralii astfel încât să obţină cât mai multe pătrăţele negre.

Date de intrare

Fişierul de intrare vitraliu.in conţine două vitralii astfel:

  • Pe prima linie vor fi N pătrăţele codificate cu 0 pentru un pătrăţel alb, sau 1 pentru un pătrăţel negru.
  • Pe a doua linie vor fi următoarele N pătrăţele, cea de-a doua linie a primului vitraliu.
  • ...
  • Pe a n-a linie vor fi N pătrăţele, ultima linie din primul vitraliu.

În continuare fişierul conţine încă N linii corespunzătoare celui de-al doilea vitraliu, astfel:

  • Pe linia n+1 vor fi N pătrăţele, prima linie a celui de-al doilea vitraliu.
  • Pe linia n+2 vor fi N pătrăţele, cea de-a doua linie a celui de-al doilea vitraliu.
  • ...
  • Pe linia 2n vor fi N pătrăţele, ultima linie din al doilea vitraliu.

Date de ieşire

În fişierul de ieşire vitraliu.out veţi scrie un singur număr, numărul de pătrăţele negre maxim pe care îl poate obţine Poppy suprapunând cele două vitralii.

Restricţii

  • Vitraliile sunt de maxim 500 ori 500 pătrăţele.
  • Suprapunerile sunt complete, nu se acceptă să rămână colţuri în afară.
  • Dimensiunea minima a unui vitraliu este de 3 × 3.

Exemple

vitraliu.invitraliu.out
0100
1010
0100
0001
0010
0010
0101
1010
4
100
001
011
010
101
101
3

Explicaţie la primul exemplu

Fişierul de intrare codifică următoarele două vitralii:

Formăm toate suprapunerile posibile, rotind şi întorcând pe cealaltă faţă al doilea vitraliu:

Numărul maxim de pătrăţele negre este 4. Acest număr se obţine în două dintre suprapunerile posibile.

Trebuie sa te autentifici pentru a trimite solutii. Click aici