Fişierul intrare/ieşire:faleza.in, faleza.outSursăONI 2017 clasa a 6-a
AutorMarius NicoliAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.6 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Faleza (clasa a 6-a)

Acum iarna s-a terminat şi, apropiindu-se sezonul de vară, gospodarii din oraşul de pe malul fluviului doresc să pregătească faleza pentru a primi cum se cuvine turiştii. Faleza este sub formă dreptunghiulară cu lungimea de n metri şi lăţimea de 2 metri. În toamnă ea era pavată cu 2n dale pătrate cu latura de un metru, lipite una de alta şi care acopereau complet zona falezei. În urma iernii grele, unele dale s-au deteriorat şi acum se doreşte înlocuirea lor.

Cum de multe ori oamenii fac treaba doar "pe jumătate", gospodarii au hotărât să cheltuie cât mai puţin pentru reamenajarea falezei, aşa că au decis că nu trebuie neapărat să înlocuiască toate dalele deteriorate, ci doar un număr minim dintre acestea astfel încât să fie posibil să se parcurgă faleza de la un capăt la altul păşind doar pe dale bune (nedeteriorate). De pe o dală pe alta se poate păşi doar dacă ele au o latură comună.

Cerinţă

Scrieţi un program care să determine numărul minim de dale deteriorate ce trebuie înlocuite astfel încât faleza să poată fi parcursă de la un capăt la altul.

Date de intrare

Fişierul de intrare faleza.in are pe prima linie un număr natural n ce reprezintă lungimea falezei. Pe linia a doua şi a treia se află câte n numere care pot fi 0 sau 1. Pe aceeaşi linie, numerele sunt separate prin câte un spaţiu. O valoare 1 semnifică prezenţa unei dale bune în acel loc iar valoarea 0 semnifică o dală deteriorată. Pe linia a doua a fişierului se află codificarea unei părţi din faleză (să spunem că aceea aflată către apă), iar pe linia a treia se află codificarea celeilalte părţi a falezei. Dalele sunt lipite una de alta în cadrul aceleiaşi linii, şi două câte două pe coloane.

Date de ieşire

Fişierul de ieşire faleza.out conţine un singur număr natural ce reprezintă numărul minim de dale deteriorate ce trebuie înlocuite pentru a putea fi parcursă faleza de la un capăt la celălalt.

Restricţii

  • 3 ≤ n ≤ 100000
  • pentru teste în valoare de 20 puncte, una dintre părţile falezei are în întregime dale deteriorate

Exemplu

faleza.infaleza.outExplicaţie
8
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 1
5
Am notat cu D o dală înlocuită.
D D 1 1 1 0 0 0
0 0 0 0 D D D 1
În această soluţie, faleza poate fi parcursă de la stânga la dreapta
păşind pe 5 dale de sus, apoi se coboară pe partea de jos şi se păşeşte
pe cele 4 dale, până se ajunge în dreapta.
sau
D D 1 1 1 D D D
0 0 0 0 0 0 0 1
În această soluţie, faleza poate fi parcursă de la stânga la dreapta
păşind doar pe dalele de sus.
Trebuie sa te autentifici pentru a trimite solutii. Click aici