Fișierul intrare/ieșire vitraliu.in, vitraliu.out Sursă ad-hoc
Autor Cristian Frâncu Adăugată de avatar francu Cristian Francu francu
Timp de execuție pe test 0.1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in vitraliu.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii