Cerinț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 2*n 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ă.
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 și precizări
3 ≤ n ≤ 100000- pentru teste în valoare de
20puncte, una dintre părțile falezei are în întregime dale deteriorate.
Exemplu
faleza.in
8 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1
faleza.out
5
Explicație
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.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Faleza:
/// Flavius Boian
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("faleza.in");
ofstream g("faleza.out");
int a[200001],b[200001],i,n,poza,pozb,k;
int main()
{
f>>n;
for(i=1; i<=n; i++) ///citesc caracter cu caracter si le pun in vector
{
f>>a[i];
}
for(i=1; i<=n; i++)
{
f>>b[i];
}
i=1;
while(a[i]==0 && b[i]==0) ///caut primul 1
{
k++;
a[i]=b[i]==k;
i++;
if(i==n+1)
break;
}
if(a[i]==1)
poza=1; ///marchez randul pe care ma deplasez, cel in care am gasit primul 1
else if(b[i]==1)
pozb=1;
while(i<n)
{
while(a[i]==0 && b[i]==0) /// daca ajung in cazul in care pe pozitia curenta am 0 pe amandoua liniile
{ /// merg pana ajung la primul 1 si cresc numarul de placute
k++;
a[i]=b[i]==k;
i++;
if(i==n+1)
break;
}
if(a[i]==1)
{
poza=1; ///marchez randul pe care ma deplasez,cel in care am gasit primul 1 dupa secventa de 0
pozb=0;
}
else if(b[i]==1)
{
pozb=1;
poza=0;
}
if(poza==1)
{
while(a[i+1]==1 and i!=n+1) ///ma deplasez pe linia curenta pana la capatul secventei de 1
i++;
if(i==n) break;
else
if(a[i+1]==0 and b[i]==0) /// daca urmatorul element e 0 si nu pot sa ma duc nici jos
{
i++;
k++; ///creste nr de patratele necesare
a[i]=b[i-1]=k;
}
else if(a[i+1]==0 and b[i]!=0) /// daca urmatorul element e 0, dar am 1 pe linia cealalta
{
i++;
poza=0;
pozb=1; /// schimb randul
}
else if(a[i+1]==0 and b[i]!=0 and b[i+1]!=0) ///ma duc jos si la dreapta pe randul 2, daca acolo am elemente nenule
{
i++;
poza=0;
pozb=1;
}
if(i==n && a[i]==0 && b[i]==0) /// daca am ajuns pe ultima pozitie si am 0 pe amandoua liniile
k++; /// creste numarul de placute
}
else if(pozb==1) /// daca sunt pe randul 2
{
while(b[i+1]==1 and i!=n+1) /// fac aceleasi verificari ca la randul 1
i++;
if(i==n) break;
if(b[i+1]==0 and a[i]==0)
{
i++;
k++;
b[i]=a[i-1]=k;
}
else if(b[i+1]==0 and a[i]!=0)
{
i++;
poza=1;
pozb=0;
}
else if(b[i+1]==0 and a[i]!=0 and a[i+1]!=0)
{
i++;
poza=1;
pozb=0;
}
if(i==n && a[i]==0 && b[i]==0)
k++;
}
}
g<<k;
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #2045 Faleza
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2045 Faleza de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!