Rezolvare completă PbInfo #2433 cufar

Vrăjitoarea cea bună are un cufăr în care este închisă piatra magică de către piticii lăzii cu ajutorul unui cifru digital. Piticii i-au dat vrăjitoarei o cutie în care sunt n cartonașe. Pe fiecare cartonaș este scris un număr natural pe care vrăjitoarea îl va folosi să deschidă lada. Valorile scrise pe cartonașe sunt distincte între ele.
Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaș din cutie și apoi determină valoarea magică asociată numărului natural scris pe cartonaș. Pentru fiecare cartonaș valoarea magică este dată de al k-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obținute pentru cele n cartonașe și apoi să introducă în ordine cifrele valorii obținute, pentru a descuia lada.

Cerința

Deoarece vrăjitoarea nu are timp la dispoziție vă roagă pe voi să o ajutați să rezolve următoarele probleme:
1. Să afle valoarea magică pentru un cartonaș dat;
2. Să afle cifrul cufărului.

Date de intrare

Fișierul de intrare este cufar.in. Pe prima linie a fișierului de intrare se găsesc o valoare p care poate fi doar 1 sau 2 și numărul n de cartonașe despărțite prin câte un spațiu.
Dacă p este 1 pe linia a doua a fișierului de intrare se găsesc două valori reprezentând numărul de pe cartonașul dat și valoarea k, separate printr-un spațiu, cu semnificația de mai sus.
Dacă p este 2 pe următoarele n linii ale fișierului de intrare se găsesc câte două valori, separate prin câte un spațiu, reprezentând numărul de pe cartonaș și valoarea lui k pentru fiecare din cele n cartonașe.

Date de ieșire

Fișierul de ieșire este cufar.out. Dacă valoarea lui p este 1, atunci se va rezolva doar cerința 1 și fișierul de ieșire va conține pe prima linie valoarea magică asociată cartonașului dat.
Dacă valoarea lui p este 2, atunci se va rezolva doar cerința 2 și fișierul de ieșire va conține pe prima linie cifrul necesar deschiderii cufărului.

Restricții și precizări

  • 1 ≤ n < 1 000 000
  • 2 ≤ valoarea înscrisă pe un cartonaș ≤ 1 000 000
  • Se garantează că pentru fiecare pereche (număr, k), număr are cel puțin k divizori primi.
  • Pentru rezolvarea corectă a cerinței 1 se acordă 18 puncte
  • Pentru rezolvarea corectă a cerinței 2 se acordă 72 de puncte
  • Pentru rezultate corecte la cerința a doua respectând restricțiile problemei și n ≤ 1000 se acordă 18 puncte
  • Pentru rezultate corecte la cerința a doua respectând restricțiile problemei și n ≤ 500 000 se acordă 43 de puncte
  • În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplele din enunț.

Exemplul 1:

cufar.in

1 1
30 3

cufar.out

5

Explicație

p = 1, n = 1
Se rezolvă doar prima cerință. Al treilea divizor prim al numărului 30 este 5.

Exemplul 2:

cufar.in

2 5
30 3
64 1
105 2
1001 3
5474 4

cufar.out

48

Explicație

p = 2, n = 5
Se rezolvă doar a doua cerință. Al treilea divizor prim al numărului 30 este 5.
Primul divizor prim al numărului 64 este 2.
Al doilea divizor prim al numărului 105 este 5.
Al treilea divizor prim al numărului 1001 este 13.
Al patrulea divizor prim al numărului 5474 este 23.
Suma căutată va fi S = 5 + 2 + 5 + 13 + 23, de unde rezultă cifrul 48.

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

//prof. Cristian Toncea - Colegiul National "Nicolae Balcescu" - Braila
#include <cstdio>

using namespace std;
int p;
long long s=0;
long a[1000005],k[1000005]={-1},i,n,j,c,l;

int main()
{
     freopen("cufar.in","r",stdin);
    freopen("cufar.out","w",stdout);
    scanf("%d %lld",&p,&n);
    if(p==1)
    {
        scanf("%d%d",&l,&c);
        for(i=2;i<=500000;i++)
        if(a[i]==0)
        for(j=1;j<=1000000/i;j++)
        {
            a[i*j]++;
            if(a[i*j]==c && i*j==l)
                printf("%ld",i);
        }

    }
    else
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&j,&c);
            k[j]=c;
        }
    for(i=2;i<=1000000;i++)
        if(a[i]==0)
        for(j=1;j<=1000000/i;j++)
        {
            a[i*j]++;
            if(a[i*j]==k[i*j])
{s=s+i;
}
        }
    printf("%lld",s);
    }
    fclose(stdin);
    fclose(stdout);
    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 #2433 cufar

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