Un gard este format din mai multe plăci dreptunghiulare. Fiecare placă este, la rândul ei, construită din NxM cărămizi. Una dintre plăci ridică o problemă, deoarece este deteriorată. Placa este reprezentată pe hârtie cu ajutorul unei matrice cu N linii și M coloane, numerotate de la 1 la N, respectiv de la 1 la M. Matricea conține doar valori 0 și 1, și respectă următoarele reguli:

un element egal cu 1 indică prezența în aceea poziție a unei cărămizi, iar un element egal cu 0 indică absența ei;
linia 1 și linia N conțin numai valori egale cu 1, pentru că marginea de sus și cea de jos a plăcii este intactă;
din orice element egal cu 1, situat în interiorul matricei, se poate ajunge pe linia 1 sau pe linia N sau pe amândouă, mergând doar în sus sau doar în jos, parcurgând numai valorile egale cu 1;
există cel puțin o coloană stabilă (formată numai din elemente egale cu 1).

Se dorește modificarea plăcii și pentru aceasta se pot șterge din matrice maximum K coloane alăturate. După ștergere se alipesc coloanele rămase și se deplasează pe verticală partea de sus a plăcii spre cea de jos, până când se va forma o coloană stabilă.

Cerința

Să se determine înălțimea minimă Hmin pe care o poate avea placa ștergând cel mult K coloane alăturate. Identificați numărul minim de coloane alăturate care trebuie șterse pentru a obține înălțimea Hmin.

Date de intrare

Din fișierul placa.in se citesc de pe prima linie 3 numere naturale N, M, K separate prin câte un spațiu, având semnificația din enunț. Pe fiecare dintre următoarele M linii ale fișierului se găsesc perechi de numere naturale N1, N2, separate printr-un spațiu. Astfel pe linia i+1 a fișierului de intrare numărul N1 reprezintă numărul de elemente de 1 situate pe coloana i, începând cu linia 1, deplasându-ne în „jos” până la întâlnirea unei valori egale cu 0, sau până se ajunge pe linia N; numărul N2 reprezintă numărul de elemente de 1 situate pe coloana i, începând cu linia N, deplasându-ne în „sus” până la întâlnirea unei valori egale cu 0, sau până se ajunge pe linia 1.

Date de ieșire

În fișierul placa.out se va scrie pe prima linie înălțimea minimă cerută Hmin, iar pe a doua linie numărul minim de coloane ce trebuie eliminate pentru a obține înălțimea Hmin.

Restricții și precizări

1 ≤ N ≤ 100.000; 1 ≤ M ≤ 100.000; 1 ≤ K < M;
se garantează că pe liniile ce conțin informații referitoare la cele M coloane ale matricei există cel puțin o linie pe care se află valoarea N de 2 ori, în rest suma celor două valori este strict mai mică decât N;
toate valorile din fișier sunt strict pozitive;

Exemplu

placa.in

placa.out

3
2

Explicație

Matricea inițială:

1 1 1 1 1 1
0 1 0 1 0 0
0 0 0 1 1 0
0 0 1 1 1 0
1 1 1 1 1 1

Înălțimea minimă este 3 și se poate obține eliminând, de exemplu, coloanele 3, 4, 5 rezultând matricea:

1 1 1
0 1 0
1 1 1

O altă modalitate de a obține aceeași înălțime dar prin ștergerea unui număr minim de coloane (4 și 5) conduce la:

1 1 1 1
0 1 1 0
1 1 1 1

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 Placa:

#include <fstream>
#define DIM 1000002

using namespace std;

int v[DIM], a[DIM], b[DIM], c[DIM], d[DIM];
int n, m, k, x, y, i, j, sol, solc, p, u, mid;

int main() {
    ifstream fin("placa.in");
    ofstream fout("placa.out");

    fin>>n>>m>>k;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        if (x!=n)
            v[i] = x+y;
        else
            v[i] = n;
    }

    a[1] = v[1];
    for (i=2;i<=m;i++)
        if (a[i-1] > v[i])
            a[i] = a[i-1];
        else
            a[i] = v[i];

    b[m] = v[m];
    for (i=m-1;i>=1;i--)
        if (v[i] > b[i+1])
            b[i] = v[i];
        else
            b[i] = b[i+1];

    sol = m+2;
    for (i=1,j=k;j<=m;i++,j++) {
        if (a[i-1] > b[j+1])
            x = a[i-1];
        else
            x = b[j+1];

        if (x < sol)
            sol = x;
    }

    fout<<sol<<"
";


    for (i=1;i<=m;i++) {
        if (a[i] > sol)
            c[i] = 1;
        else
            c[i] = c[i-1];
    }

    for (i=m;i>=1;i--) {
        if (b[i] > sol)
            d[i] = 1;
        else
            d[i] = d[i+1];
        c[i] = c[i] && d[i];
        if (c[i] == 1)
            p++;
    }

    fout<<p<<"
";

    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 Adresa de email .

Rezolvarea problemei #1206 Placa

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1206 Placa 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!

Rezolvare completă PbInfo #1206 Placa