# PBinfo #4775 – traseu4 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

De a lungul unui traseu se află mai multe obiective turistice identificate printr un număr natural numit cod. Popularitatea unui obiectiv turistic este dată de numărul divizorilor primi din descompunerea în factori primi a codului său. Cu cât un cod are mai mulți divizori primi, cu atât obiectivul cu acel cod este mai popular. Numim secvență populară o succesiune de obiective turistice care conține un singur obiectiv cu popularitate maximă, iar acesta se află fie la începutul, fie la finalul secvenței. Lungimea unei secvențe populare este dată de numărul său de obiective.

Cerința
Cunoscând numărul N de obiective turistice din traseu și cele N coduri ale lor (c[1], c[2], …, c[N]), să se determine:
1) Obiectivele turistice de popularitate maximă
2) Lungimea maximă a unei secvențe populare de forma (c[i],c[i+1], ..., c[j]), 1 ≤ i ≤ j ≤ N

Date de intrare
Fișierul de intrare traseu.in conține pe prima linie numărul N de obiective și cerința C, (separate printr-un spațiu), iar pe al doilea rând N numere naturale separate prin câte un spațiu, reprezentând codurile obiectivelor turistice.

Date de ieșire
Fișierul de ieșire traseu.out va conține:
- pentru cerința 1): un șir de numere separate prin câte un spațiu reprezentând codurile celor mai populare obiective turistice, în ordinea apariției lor în fișierul de intrare,
- pentru cerința 2): o singură valoare reprezentând lungimea maximă a unei secvențe de numere succesive din șirul dat, care conține un singur obiectiv de popularitate maximă aflat la unul din capetele sale.

Restricții și precizări

1 ≤ N ≤ 1000
Numerele de pe al doilea rând din fișierul de intrare sunt nenule și mai mici sau egale cu 1.000.000
Pentru cerința 1 se acordă 45 de puncte
Pentru cerința 2 se acordă 45 de puncte
Se acordă 10 puncte pentru exemple

Exemplul 1:
traseu.in

8 1
12 6 30 18 10 50 15 70
traseu.out

30 70
Explicație
Cerința este 1. Dintre cele 8 obiective turistice cele mai populare sunt cele cu codurile 30 și 70, fiecare având 3 divizori primi.

Exemplul 2:
traseu.in

8 2
12 6 30 18 10 50 15 70
traseu.out

5
Explicație
Secvențele populare de lungime maximă pot fi 30 18 10 50 15 sau 18 10 50 15 70.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream fin("traseu.in");
ofstream fout("traseu.out");
# define NRMAX 1000000
int ciur[NRMAX+1], c[1001], n, maxi, lgmax, i, poz, j, cer;
int main()
{
    fin>>n>>cer;
    for(i=1; i<=n;i++) fin>>c[i];
    for(i=2; i<=NRMAX; i++)
        if (ciur[i]==0)
            for(j=i; j<=NRMAX; j+=i)
                ciur[j]++;
    for(i=1; i<=n;i++)
        if (ciur[c[i]]>maxi)maxi=ciur[c[i]];
     if(cer==1){
        for(i=1; i<=n;i++)
            if(ciur[c[i]]==maxi) fout<<c[i]<<" ";
                }
    else {
        lgmax=0;
        for(i=1; i<=n;i++)
            if(ciur[c[i]]==maxi){
                if(lgmax==0)lgmax=i;
                else if(i-poz>lgmax)lgmax=i-poz;
                poz=i;
                }
        if (ciur[c[n]]!=maxi)
            if(n-poz+1>lgmax) lgmax=n-poz+1;
        fout<<lgmax;
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4775)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4775/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4775/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)