Rezolvare completă PbInfo #1694 Norocos

Un număr natural nenul m se numește norocos dacă pătratul lui se poate scrie ca sumă de m numere naturale consecutive. Un număr natural m se numește k-norocos, dacă este egal cu produsul a exact k numere prime distincte. Observați că între cele două proprietăți definite nu există nicio legătură.

Cerința

Dându-se k și N numere naturale, scrieți un program care să determine:

a) Cel mai mic și cel mai mare număr norocos dintre cele N numere citite
b) Câte numere k-norocoase sunt în șirul de N numere citite

Date de intrare

Fișierul de intrare norocos.in conține pe prima linie un număr natural C. Pentru toate testele de intrare, numărul C are una din valorile 1 sau 2. Pe linia a doua a fișierului se găsesc numerele naturale N și k, cu semnificația din enunț, iar pe a treia linie se găsesc N numere naturale, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire este norocos.out.

Dacă C=1, se va rezolva numai punctul a). În acest caz, în fişierul de ieşire se vor scrie, separate printr-un spațiu, în această ordine, cel mai mic și cel mai mare număr norocos dintre cele N numere citite. Dacă nu există niciun număr norocos se va afișa valoarea 0. Dacă există un singur număr norocos, acesta se va afișa de două ori.

Dacă C=2, se va rezolva numai punctul b). În acest caz, în fişierul de ieşire se va scrie un singur număr reprezentând numărul de numere k-norocoase citite.

Restricții și precizări

  • 1 ≤ N ≤ 1000
  • 2 ≤ k ≤ 30
  • 1 ≤ numerele citite de pe a treia linie a fișierului ≤ 2 000 000 000
  • Pentru rezolvarea corectă a primei cerinţe se acordă 40 de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60 de puncte.

Exemplul 1

norocos.in

1
9 3
165 12 33 30 5 18 105 15 4

norocos.out

5 165

Explicație

Atenție, C=1, deci se va rezolva doar prima cerință.

Cel mai mic număr norocos este 5
52=25=3+4+5+6+7

Cel mai mare număr norocos este 165
1652=27225=83+84+85+…+246+247
Observați faptul că, deși se citește valoarea lui k, aceasta nu este folosită în rezolvarea cerinței 1.

Exemplul 2

norocos.in

2
5 3
165 31 165 105 44

norocos.out

3

Explicație

Atenție, C=2, deci se va rezolva doar a doua cerință.

Cele trei numere k-norocoase sunt 165, 165, 105

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

#include <fstream>
#include <cmath>

using namespace std;

int t, n, k, a, sol, d, e, nr, i, x, ok, r, amax = 0, amin = 2000000000;

int main () {
    ifstream fin ("norocos.in");
    ofstream fout("norocos.out");

    fin>>t>>n>>k;
    for (i=1;i<=n;i++) {
        fin>>x;
        if (t == 1 && x%2 == 1) {
            a++;
            if (x < amin) {
                amin = x;
            }
            if (x > amax) {
                amax = x;
            }
        }
        if (x == 1)
            continue;
        if (t == 2) {
            ok = 1;
            r = (int)sqrt(x);
            d = 2;
            nr = 0;
            while (x != 1 && d <= r) {
                if (x%d == 0) {
                    e = 0;
                    while (x%d == 0) {
                        x /= d;
                        e++;
                    }
                    if (e != 1) {
                        ok = 0;
                        break;
                    }
                    nr++;
                    if (nr > k) {
                        ok = 0;
                        break;
                    }
                }
                d++;
            }
            if (x!=1)
                nr++;
            if (nr != k)
                ok = 0;
            if (ok) {
                sol++;
            }
        }
    }

    if (t == 1) {
        if (a == 0) {
            fout<<a<<"
";
        } else {
            fout<<amin<<" "<<amax<<"
";
        }

    } else
        fout<<sol<<"
";

    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 #1694 Norocos

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