Question

Adrian este pasionat de matematică. El utilizează denumirea maxdiv pentru numărul care are cei mai mulţi divizori, dintre numerele unui şir dat. Adrian ştie că o secvenţă este un subşir de numere care apar pe poziţii consecutive într-un şir. El denumeşte secvenţă maxdiv o secvenţă din şir, formată din cel puţin două numere, ce începe şi se încheie cu un număr maxdiv şi nu conţine alte numere maxdiv în interior. Având la dispoziţie un şir de n numere naturale, doreşte să afişeze cea mai lungă secvenţă maxdiv şi numărul de secvenţe maxdiv din şir. Dacă şirul de numere dat conţine mai multe secvenţe maxdiv de aceeaşi lungime maximă, se va afişa prima secvenţă de acest tip din şir.

Cerinţă
Scrieţi un program care afişează, pentru un şir dat format din n numere naturale numărul de secvenţe maxdiv şi cea mai lungă secvenţă maxdiv.

Date de intrare
Fişierul de intrare maxdiv.in conţine pe prima linie numărul n separat printr-un spaţiu de un număr natural t, care reprezintă cerinţa: 1, dacă se cere numărul de secvenţe maxdiv, respectiv 2 dacă se cere cea mai lungă secvenţă maxdiv . Linia a doua din fişier conţine cele n numere naturale ale şirului dat.

Date de ieşire
Fişierul de ieșire maxdiv.out va conţine pe prima linie un număr natural ce reprezintă numărul de secvenţe maxdiv, pentru şirul de numere dat, dacă cerinţa este 1. Dacă cerinţa este 2, fişierul de ieşire va conţine un şir de numere naturale, separate între ele prin câte un spaţiu, ce reprezintă cea mai lungă secvenţă maxdiv din şirul dat.

Restricţii şi precizări
· 2 ≤ n ≤ 1000
· 2 ≤ xi ≤ 1000000, unde xi reprezintă un număr din şirul dat
· Şirul de numere conţine cel puţin o secvenţă care începe şi se încheie cu un număr maxdiv
· Pentru cerința 1 se acordă 40% din punctaj, iar pentru cerința 2 se acordă 60% din punctaj.

Exemple

Cerinţa 1
Şirul de numere dat conţine 3 numere maxdiv: 60, 315 şi 150 (au fiecare 12 divizori) și 2 secvenţe maxdiv :
60, 64, 125, 315 şi 315,24,150.

7 2
22 60 64 125 315 24 150

Cerinţa 2
Şirul de numere dat conţine 2 secvenţe maxdiv: 60, 64, 125, 315 şi 315, 24, 150. Cea mai lungă secvenţă este 60, 64, 125, 315.

Answer 1

#include <fstream>

using namespace std;

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

int n, nrdiv[1010], x, nrd, nrdivmax, d, p1, i, cate, cerinta, V[1010];
int stanga, dreapta, stangamax, dreaptamax, lung, lungmax;
int main()
{
   fin >> n >> cerinta;
   for (i = 1; i <= n; i++)
   {
      fin >> x;          //citire un element
      V[i] = x;          //retin in vector pentru cerinta 2
      nrd = 1;           //initializez cu 1 produsul (nrd = (p1+1)*(p2+1)*...*(pk+1))
      p1 = 0;            //calculez puterea lui 2 separat (2 - singurul prim par)
      while (x % 2 == 0)
      {
         p1++;
         x /= 2;         //determin puterea si impart
      }
      nrd *= (p1 + 1);   //inmultesc la nrd
      d = 3;             //pentru ceilalti factori primi plec de la 3
      while (x > 1)      //impart cat se poate
      {
         p1 = 0;           //initializez puterea
         while (x % d == 0)//cat timp se poate
         {
            p1++;
            x /= d;  //impart si contorizez
         }
         nrd *= (p1 + 1); //inmultesc la nrd
         d += 2;          //trec la alt posibil factor prim
         if (d * d > x )  //daca am trecut de radical => x este prim
            d = x;         //este ultimul posibil factor prim
      }
      nrdiv[i] = nrd;     //retin nr de divizori
      if (nrd > nrdivmax) //si determin maximul
      {
          nrdivmax = nrd;
          cate = 1;
      }
      else
            if (nrd == nrdivmax) cate++;
   }
    if (cerinta == 1)
        fout << cate - 1 << '\n';
    else
    {
        i = 1;
        while (nrdiv[i] != nrdivmax) i++;
        stanga = i;
        i++;
        while (i <= n)
        {
            if (nrdiv[i] == nrdivmax)   //am gasit inca unul
            {
                dreapta = i;
                lung = dreapta - stanga + 1;
                if (lung > lungmax)      //am gasit o secv mai mare
                {
                    stangamax = stanga;
                    dreaptamax = dreapta;
                    lungmax = lung;
                }
                stanga = dreapta;
            }
            i++;
        }
        for (i = stangamax; i <= dreaptamax; i++)
            fout << V[i] << ' ';
        fout << '\n';
    }
   return 0;
}

Iei 100p pe ea.