Lumea este în pericol. Încălzirea globală are efecte profunde în cele mai diferite domenii. Ea determină apariția extremelor climatice, topirea ghețarilor, ridicarea nivelului mărilor și, cel mai grav, dispariția a numeroase specii de animale. Cercetătorii au observat că cele mai afectate sunt furnicile.

Pentru a stabili cât de rapid este procesul de dispariție, ei și-au propus să le studieze timp de n zile, notând în fiecare zi numărul de furnici lucrătoare care ies după hrană. Ei au constatat că ele sunt afectate dacă, în zile consecutive, numărul de divizori ai numărului de furnici lucrătoare descrește. Vor lua în considerare doar perioadele de cel puțin două zile consecutive de descreșteri.

Pentru finalizarea studiului, trebuie să știe câte astfel de perioade au existat. Pentru că la calculele matematice pot greși, vă roagă să-i ajutați.

Cerința

Dându-se un număr natural n, reprezentând numărul de zile în care se face studiul și apoi un șir x de n numere naturale, ce reprezintă șirul numerelor de furnici lucrătoare care ies după hrană, unde x_i reprezintă numărul de furnici lucrătoare din ziua i. Se cere să se determine numărul de secvențe maximale, ordonate strict descrescător după numărul de divizori, de lungime minim 2.

Date de intrare

Fișierul de intrare furnici.in conţine două linii. Pe prima linie este scris numărul natural n, cu semnificația din cerință iar pe linia a doua, elementele șirului x, cu semnificația din cerință.

Date de ieșire

Fișierul de ieșire furnici.out va conţine un număr natural reprezentând numărul de secvențe maximale, de lungime minim 2, ordonate strict descrescător după numărul de divizori.

Restricții și precizări

2 ≤ n ≤ 100000
10 ≤ x_i ≤ 1.000.000.000

Exemplu

furnici.in

10
719  169 4065  813  289  101 123  516  516  1017

furnici.out

Explicație

Șirul numărului de divizori este: 2 3 8 4 3 2 4 12 12 6.
Se observă că sunt două secvențe maximale, de lungime minim doi, strict descrescătoare 8 4 3 2 și 12 6.

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

#include <fstream>

using namespace std;

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

int nr_divizori(int x)
{
    int d, e=0,p=1;
    for(d=2;d*d<=x;d++)
    {
        for(e=0;x%d==0;x=x/d)
            ++e;
        p=p*(e+1);
    }
    if(x!=1)
        p=p*2;
    return p;
}

int main()
{
    int n, x, k=0, d1, d2,l;

    fin>>n>>x;
    d1=nr_divizori(x);
    l=1;
    for(int i=2;i<=n;++i)
    {
        fin>>x;
        d2=nr_divizori(x);
        if(d1>d2)
            l++;
        else
            if(l>1){
                ++k;
                l=1;
        }
        d1=d2;
    }
    if(l>1)
        ++k;
    fout<<k;
    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 #2347 Furnici

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

Rezolvare completă PbInfo #2347 Furnici