Rezolvare completă PbInfo #3345 divimax

Enunț

Având note mici la matematică, Gicuţa primeşte spre rezolvare următoarea problemă (uşoară pentru clasa a X-a) pentru a-şi mări nota: “Dându-se un şir X cu N numere naturale nenule: X 1 , X 2,…., X N, să se determine cel mai mare divizor prim dintre toti divizorii tuturor numerelor din şirul X“.
Însă, pentru a obţine nota 10, el mai are de rezolvat o cerinţă a problemei: să determine cel mai mare număr care se poate forma din concatenarea divizorilor primi maximi ai fiecărui număr din şirul X.

Cerința

Scrieţi un program care să citească numărul natural N şi cele N numere naturale din şirul X şi care să determine:
1. numărul natural P reprezentând cel mai mare divizor prim dintre toţi divizorii tuturor numerelor din şirul X
2. cel mai mare număr natural K ce se poate forma din concatenarea divizorilor primi maximi ai fiecărui număr din şirul X.

Date de intrare

Fișierul de intrare divimax.in conține conţine N+1 linii. Pe prima linie sunt scrise doua numere naturale C și N, separate printr-un spațiu. Pe fiecare dintre următoarele N linii este scris câte un număr din şirului X, astfel încât pe linia i+1 din fişier este scris numărul Xi (1≤i≤N).

Date de ieșire

Fișierul de ieșire divimax.out va conține o linie.
- Dacă C=1, atunci se va rezolva doar cerința 1 a problemei, iar pe prima linie se va scrie numărul natural P reprezentând raspunsul la cerința 1.
- Dacă C=2, atunci se va rezolva doar cerința 2 a problemei, iar pe prima linie a fişierului se va scrie numărul natural K, reprezentând răspunsul la cerința 2.

Restricții și precizări

- 0 ≤ N ≤ 3030, N număr natural
- C=1 sau C=2
- 2 ≤ Xi ≤ 3500, unde 1 ≤ i ≤N
- Concatenarea a două numere inseamnă lipirea lor. (exemplu: Prin concatenarea numerelor 325 şi 684 rezultă numărul 325684, iar concatenându-le invers, obţinem 684325)
- Numărul determinat la cerinţa 2 poate avea cel mult 8000 de cifre
- Pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.

Exemplul 1:

divimax.in

1 5
2 
36 
15 
12 
33

divimax.out

11

Explicație

C=1, se va rezolva doar cerinta 1.
Cel mai mare divizor prim al lui 2 este 2, cel mai mare divizor prim al lui 36 este 3, cel mai mare divizor prim al lui 15 este 5, cel mai mare divizor prim al lui 12 este 3, cel mai mare divizor al lui 33 este 11.

Exemplul 2:

divimax.in

2 7
23
44
10
204
4
45
9

divimax.out

5532321711

Explicație

C=2, se va rezolva doar cerinta 2.
Cei mai mari divizori primi ai numerelor sunt 23, 11, 5, 17, 2, 5, 3 (în ordinea în care sunt date în fişierul de intrare).

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

#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

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

struct numar{
    char sir[13];}a[3100];
int n,c;
int divi(int x)
{   int f=2,p=1;
    while(x>1)
    {
        if(x%f==0)
        {
            if(p<f)p=f;
            while(x%f==0)
                x=x/f;
        }
        if(f==2)f=3;
        else f++;
    }
    return p;
}
void conversie(int x, char s[])
{
    int k=0,i,j;
    while(x)
    {
        s[k++]=x%10+'0'; x=x/10;
    }
    s[k]='\0';
    i=0, j=k-1;
    while(i<j)
        { swap(s[i],s[j]); i++; j--; }
}

bool comp( numar x, numar y)
{
    char z[30],t[30];
    strcpy(z,x.sir);
    strcat(z,y.sir);
    strcpy(t,y.sir);
    strcat(t,x.sir);
    return strcmp(z,t)>0;
}

int main()
{

    fin>>c>>n;
    int i,x,p,maxp=0;
    for (i=1; i<=n; i++)
        {
            fin>>x;
            p=divi(x);
            maxp=max(maxp,p);
            conversie(p,a[i].sir);
        }
    sort(a+1,a+n+1, comp);
    if(c==1)
        {fout<<maxp<<endl; return 0;}
    ///C=2
    for (i=1; i<=n; i++)
       fout<<a[i].sir;
    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 #3345 divimax

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