E primăvară și se întorc berzele. În satul nostru, stâlpii de la marginea drumului au vârfurile prea ascuțite și din această cauză berzele nu-și pot face cuib. Așa că e tristețe mare la noi… Dar ne-am adunat cu toții și am hotărât ca pe vârful unor stâlpi să instalăm câte un suport orizontal plan, astfel încât să nu-i fie greu unei berze să-și amenajeze cuibul. Avem n stâlpi la marginea drumului, dispuși liniar și numerotați de la 0 la n–1.

Un număr de m săteni au venit cu câte o restricție de forma i j, însemnând faptul că pe stâlpii din intervalul [i,j] se pot instala cel mult două suporturi pentru cuiburi de berze. Motivele acestor restricții sunt diverse, cum ar fi de pildă apropierea prea mare între anumiți stâlpi. Vom ține seama de ele pentru că vrem ca toți sătenii să fie mulțumiți.

Cerința

Cunoscând n, m și cele m restricții, să se determine numărul de posibilități ca berzele să-și amenajeze cuiburi pe cei n stâlpi, modulo 700001.

Date de intrare

Fișierul de intrare berze.in conține pe prima linie numerele n şi m având semnificația din enunț. Pe următoarele m linii se găsesc câte două numere naturale i, j, reprezentând faptul că în intervalul de stâlpi [i,i+1,i+2,...,j] se pot amenaja cel mult două suporturi pentru cuiburi de berze.

Date de ieșire

Fișierul de ieșire berze.out va conține pe o singură linie un număr natural ce reprezintă numărul de posibilități de a plasa suporturi pentru cuiburi de berze pe cei n stâlpi.

Restricții și precizări

2 ≤ m, n ≤ 1000
0 ≤ i < j ≤ n – 1
cele m intervale de forma i j nu sunt neapărat disjuncte
pe un stâlp se poate instala cel mult un suport pentru cuib de barză
pentru 50% din teste N ≤ 100

Exemplu

berze.in

4 1
0 2

berze.out

Explicație

Notăm cu I un stâlp fără suport pentru cuib de barză şi cu T un stâlp cu suport. Atunci cele 14 soluții sunt:
I I I I
T I I I
I T I I
I I T I
T T I I
T I T I
I T T I
I I I T
T I I T
I T I T
I I T T
T T I T
T I T T
I T T T
Observați că restricția este între stâlpii 0 și 2.

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

// prof. Constantin Galatan
// O(n^2)
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("berze.in");
ofstream fout("berze.out");

const int Dim = 1001, Mod = 700001;
int n, m, x, y;
int nr[Dim][Dim];
int t[Dim];

int main()
{
    fin >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y;
        t[x] = max(t[x], y + 1);
    }
    
    for (int i = 1; i < n; ++i)
        t[i] = max(t[i], t[i - 1]);

    nr[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
        {
            if (!nr[i - 1][j]) continue;
            nr[i][j] += nr[i - 1][j];
            if (nr[i][j] >= Mod)
                nr[i][j] -= Mod;

            if (j <= i)
            {
                nr[i][t[i - 1]] += nr[i - 1][j];
                if (nr[i][t[i - 1]] >= Mod)
                    nr[i][t[i - 1]] -= Mod;
            }
            else
            {
                nr[j][t[i - 1]] += nr[i - 1][j];
                if (nr[j][t[i - 1]] >= Mod)
                    nr[j][t[i - 1]] -= Mod;
            }
        }

    int res = 0;
    for (int i = 0; i <= n; ++i)
    {
        res += nr[n][i];
        if (res > Mod)
            res -= Mod;
    }

    fout << res;
    fout.close();
    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 #2515 berze

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