Se consideră un şir x₁, x₂, …, x_n de n numere naturale distincte, două câte două. Pentru o secvenţă de k numere (x_p, x_p+1, ..., x_p+k-1), care începe cu numărul de pe poziţia p din şirul dat, definim gradul său ca fiind numărul de numere din secvenţă, care rămân pe aceleaşi poziţii după ordonarea crescătoare a secvenţei. De exemplu, pentru n=7 şi şirul format din numerele: 1, 5, 7, 4, 6, 2, 9, secvenţa formată din numerele 7, 4, 6, 2 (corespunzătoare lui p=3 şi k=4) are gradul egal cu 2 deoarece, după ordonarea crescătoare a numerelor din secvenţă, aceasta devine 2, 4, 6, 7, numerele 4 şi 6 rămânând pe aceleaşi poziţii.

Cerinţă

Scrieţi un program care citeşte numerele n, k, x₁, x₂, …, x_n, cu semnificaţia din enunţ, şi apoi determină:

a) gradul întregului şir de numere;
b) poziţia primului element din prima secvenţă de lungime k ce are gradul maxim, precum şi gradul acestei secvenţe.

Date de intrare

Fișierul de intrare grad1.in conține pe prima linie numerele n şi k, separate printr-un spaţiu, iar pe linia următoare n numere naturale distincte x₁, x₂, …, x_n, corespunzătoare şirului de numere, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire grad1.out va conține pe prima linie un număr natural reprezentând gradul întregului şir de numere, iar pe următoarea linie două numere naturale, separate printr-un singur spaţiu, primul număr reprezentând poziţia primului element din prima secvenţă de lungime k ce are grad maxim şi cel de-al doilea număr reprezentând gradul acestei secvenţe.

Restricții și precizări

0 < n < 10001
0 < k < n+1
Numerele din şir sunt numere naturale strict mai mici decât 32000.
O secvenţă de numere din şir reprezintă o succesiune de numere din acel şir, aflate pe poziţii consecutive.
Gradul întregului şir de numere este egal cu gradul secvenţei de n numere care începe cu numărul de pe poziţia 1 şi conţine toate cele n numere din şir.
Pentru rezolvarea corectă a subpunctului a) se obţine 40% din punctaj.
Pentru rezolvarea corectă a subpunctului b) se obţine 60% din punctaj.

Exemplu

grad1.in

7 4
1 5 7 4 6 2 9

grad1.out

3
3 2

Explicație

După ordonare, şirul 1 5 7 4 6 2 9 devine 1 2 4 5 6 7 9, pe aceleaşi poziţii rămân 1, 6 şi 9, deci gradul întregului şir este 3.

Avem patru secvenţe cu câte 4 elemente:

1 5 7 4, care are gradul 1
5 7 4 6, care are gradul 0
7 4 6 2, care are primul număr pe poziţia 3 și gradul 2.
4 6 2 9, care are gradul 1.

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

#include <fstream>
using namespace std;
int x[10002],y[10002],g,n,k,pmax,gmax,aux;
ifstream fin("grad1.in");
ofstream fout("grad1.out");
void cit(){
 int i;
 fin>>n>>k;
 for(i=1;i<=n;i++)
  fin>>x[i];
 fin.close();
}
void ordonare(int n){
 int i,sw,aux;
 do{
  sw=0;
  for(i=1;i<n;i++)
   if(y[i]>y[i+1])
   {
    aux=y[i];y[i]=y[i+1];y[i+1]=aux;sw=1;
   }
   //n--;
 }while(sw);
}
int main(){
int i,j,gr;
cit();
for(i=1;i<=n;i++)
 y[i]=x[i];
ordonare(n);
g=0;
for(i=1;i<=n;i++)
 if(x[i]==y[i])
  g++;
fout<<g<<'\n';
for(i=1;i<=k;i++)
 y[i]=x[i];
ordonare(k);
gmax=0;
for(i=1;i<=k;i++)
 if(x[i]==y[i])
  gmax++;
pmax=1;
for(i=2;i<=n-k+1;i++)
 {
  for(j=1;j<=k;j++)
   if(y[j]==x[i-1])
    break;
  y[j]=x[i+k-1];//ducem y[j] pe pozitia corespunzatoare a. i. y sa ramana ord. cresc.
  while(j>1&&y[j-1]>y[j]){
   aux=y[j];y[j]=y[j-1];y[j-1]=aux; j--;
  }
  while(j<k&&y[j]>y[j+1]){
   aux=y[j];y[j]=y[j+1];y[j+1]=aux;j++;
  }
  //determin gradul secventei care incepe cu x[i]
  gr=0;
  for(j=1;j<=k;j++)
   if(y[j]==x[i+j-1])
    gr++;
  if (gr>gmax){
   gmax=gr;pmax=i;
  }
 } 
fout<<pmax<<" "<<gmax;
fout.close();
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 #1075 Grad1

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