Gigel a studiat recent şirurile cu n elemente, numere naturale. Pentru un astfel de şir S, Gigel doreşte să afle răspunsul la întrebările:

a) Care este numărul minim de subşiruri strict crescătoare în care se poate partiţiona S?
b) Care este numărul de secvenţe, modulo 20011, cu suma elementelor divizibilă cu k care se pot obţine din S?

Cerința

Dându-se un şir S cu n elemente numere naturale şi un număr natural k se cere să se răspundă la cele două întrebări.

Date de intrare

Fișierul de intrare calcule.in conține pe prima linie valorile naturale n şi k separate printr-un spaţiu. Pe următoarea linie se află cele n elemente ale şirului S, numere naturale separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire calcule.out va conține două linii, pe prima linie fiind scris un număr natural reprezentând răspunsul la întrebarea a), iar pe a doua, un număr natural reprezentând răspunsul la întrebarea b).

Restricții și precizări

1 < n < 100.000
S are elemente mai mici sau egale cu 20.000
k < 50.000, k < n
Un subşir al şirului S se obţine selectând elemente din S în ordinea în care sunt în S, dar nu obligatoriu de pe poziţii consecutive, iar o secvenţă a şirului S se obţine selectând elemente în ordinea în care sunt în S, dar obligatoriu de pe poziţii consecutive. Se admit şi secvenţe sau subşiruri cu un singur element.
Pentru 50% din teste k < 10.000
Pentru răspuns corect la o singură cerinţă se acordă 50% din punctaj.
Mai multe subşiruri ale lui S formează o partiţie dacă elementele reuniunii subşirurilor pot fi reaşezate astfel încât să se obţină exact S.
x modulo y reprezintă restul împărţirii lui x la y.

Exemplu

calcule.in

10 3         		
5 3 8 6 9 6 2 7 9 6

calcule.out

4 
23

Explicație

a) O partiţie cu număr minim (4) de subşiruri crescătoare este următoarea:
5 6 7 9
3 6 9
8
2 6
b) Există 23 de secvenţe cu suma divizibilă cu 3. Iată două dintre acestea:
3
6 2 7

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

#include<fstream>
using namespace std;
#define MOD 20011
int n,k,v[100010],i,sol,x,t,r[50010],s;
unsigned long long sol1;
ifstream f("calcule.in");
ofstream g("calcule.out");
int bs(int a){
    int s=0,d,m;
    for(d=sol;s<d;){
        m=(s+d)/2;
        if(v[m]>=a)
            s=m+1;
        else
            d=m;
    }
    return s;
}
int main(){
    f>>n>>k;
    for(i=1;i<=n;++i){
        f>>x;
        s=(s+x)%k;
        r[s]++;
        t=bs(x);
        v[t]=x;
        if(t==sol)
            ++sol;
    }
    sol1=((r[0]%MOD)*((r[0]%MOD)+1)/2)%MOD;
    for(i=1;i<k;++i)
        sol1=(sol1+((r[i]%MOD)*((r[i]%MOD)-1)/2)%MOD)%MOD;
    g<<sol<<'\n'<<sol1<<'\n';
    g.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 #1037 Calcule

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