Rezolvare completă PbInfo #3432 Tai

Un număr este prim dacă are exact doi divizori naturali. Prin tăierea unui număr în p părți înțelegem împărțirea acestuia în p numere, fiecare de cel puțin o cifră, astfel încât prin alipirea numerelor obținute de la stânga la dreapta obținem numărul inițial.

De exemplu, dacă împărțim numărul 12045 în două părți avem patru variante de tăiere obținându-se numerele: 1 și 2045; 12 și 045; 120 și 45; 1204 și 5. Dacă îl împărțim în trei părți avem șase variante de tăiere obținându-se numerele 1, 2 și 045; 1, 20 și 45; 1, 204 și 5; 12, 0 și 45; 12, 04 și 5; 120, 4 și 5.

Cerința

Se consideră un șir format din N numere naturale.

1) Determinați cel mai mare număr prim din șirul celor N numere.
2) Determinați cel mai mare număr prim dintre cele obținute prin tăierea în două părți a fiecărui număr din șirul celor N.
3) Determinați cel mai mare număr prim dintre cele obținute prin tăierea în trei părți a fiecărui număr din șirul celor N.

Date de intrare

Fișierul de intrare tai.in conține pe prima linie numărul C care poate avea doar valorile 1, 2 sau 3 și reprezintă cerința care urmează a fi rezolvată. Pe a doua linie se găsește N, cu semnificația din enunț, iar pe a treia linie se găsește șirul celor N numere naturale despărțite prin câte un spațiu.

Date de ieșire

Fișierul de ieșire tai.out va conține pe prima linie un număr natural reprezentând răspunsul la cerința specificată.

Restricții și precizări

  • 1 ≤ N ≤ 100
  • 0 ≤ orice număr din șir ≤ 1000000000
  • Pentru cerințele 2 și 3 se garantează că pentru toate numerele din șir se poate efectua tăierea
  • Pentru cerința 1 dacă șirul nu conține numere prime se va afișa 0
  • Pentru cerințele 2 și 3 dacă în urma tăierilor nu se obține niciun număr prim, se va afișa 0
  • În concurs, pentru rezolvarea fiecărei cerințe s-au obținut 30 de puncte. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

tai.in

1
5
2 13 21 17 1

tai.out

17

Explicație

Numere prime din șir sunt 2, 13 și 17, iar maximul este 17.

Exemplul 2

tai.in

2
3
23 196 27

tai.out

19

Explicație

Din 23 se obțin două numere 2 și 3, din 196 se pot obține numerele 1 și 96 sau 19 și 6, iar din 27 se obțin numerele 2 și 7. Cel mai mare număr prim care se poate obține este 19.

Exemplul 3

tai.in

3
3
1234 17119 5678

tai.out

71

Explicație

Din numărul 1234 se pot obține numerele: 1, 2, 34 sau 1, 23, 4 sau 12, 3, 4.

Din numărul 17119 se pot obține numerele: 1, 7 și 119 sau 1, 71 și 19 sau 1, 711 și 9 sau 17, 1 și 19 sau 17, 11 și 9.

Din numărul 5678 se pot obține numerele: 5, 6 și 78 sau 5, 67 și 8 sau 56, 7 și 8.

Cel mai mare număr prim care se poate obține este 71.

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

#include <fstream>
using namespace std;
ifstream f("tai.in");
ofstream g("tai.out");
int N,i,x,nd,d,C,aux,y1,y2,y3,z,t,w,p,max1,x1,x2,q;
int main()
{
    f>>C;
    if (C==1)
    {
        f>>N;
        max1=0;
        for (i=1;i<=N;i++)
        {
            f>>x;
            for (d=2;d*d<=x;d++)
                if (x%d==0) break;
            if (x>1&&d*d>x&& x>max1)
                max1=x;
        }
        g<<max1<<"
";
    }
    else
        if (C==2)
    {
        max1=0;
        f>>N;
        for (i=1;i<=N;i++)
        {
            f>>x;
            aux=x;
            p=10;
            while (aux>=p)
            {
                x1=aux%p;
                x2=aux/p;
                //g<<x<<"="<<x2<<" "<<x1<<endl;
                p=p*10;
                for (d=2;d*d<=x1;d++)
                    if (x1%d==0) break;
                if (x1>1&&d*d>x1&& x1>max1)
                    max1=x1;
                for (d=2;d*d<=x2;d++)
                    if (x2%d==0) break;
                if (x2>1&&d*d>x2&& x2>max1)
                    max1=x2;
            }
        }
        g<<max1<<"
";
    }
    else
    {
        f>>N;
        max1=0;
        for (i=1;i<=N;i++)
        {
            f>>x;
            aux=x;
            p=10;
            while (aux>p*10)
                p=p*10;
            for (t=10;t*10<=p;t=t*10)
                for (q=10;q*t<=p;q=q*10)
            {
                    y1=x%t;
                    z=x/t;
                    y2=z%q;
                    y3=z/q;
                    for (d=2;d*d<=y1;d++)
                        if (y1%d==0) break;
                    if (y1>1&&d*d>y1&& y1>max1)
                        max1=y1;
                    for (d=2;d*d<=y2;d++)
                        if (y2%d==0) break;
                    if (y2>1&&d*d>y2&& y2>max1)
                        max1=y2;
                    for (d=2;d*d<=y3;d++)
                        if (y3%d==0) break;
                    if (y3>1&&d*d>y3&& y3>max1)
                        max1=y3;
            }
        }
        g<<max1<<"
";
    }
    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 #3432 Tai

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