Cod sursa(job #2823940)

Utilizator puica2018Puica Andrei puica2018 Data 30 decembrie 2021 11:41:48
Problema Stergeri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

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

/// f(i,j) = valoarea de la poz.i dupa j operatii
/// f(k,0) = k
/// f(k,m) = f(x,m-1)+x-k, m>=1
/// daca k>=st[m]: x=k+dr[m]-st[m]+1
/// altfel: x=k

/// daca k>=st[m]
///    f(k,m) = f(k+l[m],m-1)
/// altfel
///    f(k,m) = f(k,m-1)

int n,m,k;
int st[100005],dr[100005];

int f(int k,int m)
{
    if(m==0)
        return k;
    if(k>=st[m])
        return f(k+dr[m]-st[m]+1,m-1);
    return f(k,m-1);
}

int main()
{
    fin>>n>>m>>k;
    int i;
    for(i=1; i<=m; i++)
        fin>>st[i]>>dr[i];
    fout<<f(k,m)<<"\n";
    return 0;
}