Se construieşte un şir de numere naturale care respectă restricţiile:

primul număr din şir este 9;
numerele se generează în ordine strict crescătoare;
şirul conţine toate numerele formate doar cu cifrele 7, 8 şi 9 cu proprietatea că numărul cifrelor 9 este mai mare sau egal decât numărul cifrelor 8 şi numărul cifrelor 8 este mai mare sau egal decât numărul cifrelor 7.
Primii 14 termeni ai şirului, în ordine, sunt: 9, 89, 98, 99, 789, 798, 879, 897, 899, 978, 987, 989, 998, 999.

Pornind de la aceste numere, Liv a inventat un joc interactiv: N iepuraşi sunt aşezaţi în şir, fiecare având câte un cartonaş. Fiecare cartonaş are două feţe, o faţă albă pe care este inscripţionat un număr din acest şir şi o faţă gri, pe care este inscripţionată poziţia acelui număr în şir, poziţii numerotate în ordine, începând cu valoarea 1.

Exemple. Cartonaşul care are pe faţa gri inscripţionat numărul 1 va avea pe faţa albă inscripţionat numărul 9, iar cartonaşul care are pe faţa gri inscripţionat numărul 5 va avea pe faţa albă inscripţionat numărul 789.

Iepuraşii sunt aşezaţi într-o ordine oarecare şi ţin cartonaşele astfel încât să se vadă faţa gri. Jocul constă în a rearanja iepuraşii de la stânga la dreapta, descrescător după numerele inscripţionate pe feţele gri, având la dispoziţie doar operaţia TAP pe un iepuraş. Când se aplică operaţia TAP unui iepuraş atunci secvenţa de iepuraşi, începând de la cel pe care s-a făcut TAP şi până la sfârşitul şirului (spre dreapta), este oglindită (ca în imaginea de mai sus). După oglindire, toţi iepuraşii din acea secvenţă ţin cartonaşele astfel încât să se vadă faţa albă. Se doreşte aplicarea unui număr cât mai mic de operaţii TAP pentru rearanjarea iepuraşilor.

Cerinţe

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de iepuraşi) şi a₁, a₂,…, a_N (reprezentând, în ordine, numerele inscripţionate pe feţele gri) și care să determine:

a) Numărul minim de operaţii TAP necesare rearanjării iepuraşilor;
b) Cel mai mic număr aflat pe o faţă albă care nu se vede, în cazul în care au rămas cartonaşe neîntoarse. Dacă toate cartonaşele au fost întoarse (la toate fiind vizibilă faţa albă) se va afişa cel mai mare număr aflat pe o faţă albă a unui cartonaş.

Date de intrare

Fișierul de intrare iepurasi.in conține pe prima linie numărul natural N reprezentând numărul de iepuraşi. A doua linie a fişierului conţine, în ordine, cele N numere: a₁, a₂a_N, separate prin câte un spaţiu, reprezentând în ordine, numerele inscripţionate pe feţele gri ale cartonașelor.

Date de ieșire

Fișierul de ieșire iepurasi.out va conține pe prima linie un număr reprezentând numărul minim de operaţii TAP necesare rearanjării iepuraşilor. A doua linie va conține un număr reprezentând cel mai mic număr aflat pe o faţă albă care nu se vede (în cazul în care au rămas cartonaşe neîntoarse), respectiv cel mai mare număr aflat pe o faţă albă a unui cartonaş, în cazul în care toate cartonaşele au fost întoarse (la toate fiind vizibilă faţa albă).

Restricții și precizări

2 ≤ N ≤ 10000;
1 ≤ a_i ≤ 10000 (1≤i≤N);
N, a₁, a₂, …, a_N sunt numere naturale;
pentru rezolvarea cerinţei a) se acordă 50% din punctaj, iar pentru cerinţa b) se acordă 50% din punctaj.

Exemplu

iepurasi.in

5 
14 5 8 9 10

iepurasi.out

1
999

Explicație

Se aplică o singură operaţie TAP pe iepuraşul cu numărul de ordine 5. Cartonaşul neîntors are numărul de ordine 14 (999).

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

//Ana Intuneric
#include <fstream>
using namespace std;
ifstream f("iepurasi.in");
ofstream g("iepurasi.out");

long long toate[200001],ncurent;
int N,a[10001],dim_sir,TAP,nr1,nr2;
bool viz[10001];
char fr7[200001],fr8[200001],fr9[200001];

int main()
{
  int i,j,k,maxi,imax,aux,c7,c8,c9;;
  //citire
  f>>N;
  for(i=1;i<=N;i++)f>>a[i];

  //sortare descrescatoare
  for(i=1;i<=N;i++)
  {
       imax=i;maxi=a[i];
       for(j=i+1;j<=N;j++)
         if(a[j]>maxi)maxi=a[j],imax=j;
       if(imax!=i)
       {
           if(a[N]!=maxi)
           {
               TAP++;
               //TAP pe iepurasul imax
               for(j=imax,k=N;j<k;j++,k--)aux=a[j],a[j]=a[k],a[k]=aux,viz[j]=true,viz[k]=true;
           }
           //TAP pe iepurasul i
           if(a[i]!=maxi)
           {
               TAP++;
               for(j=i,k=N;j<k;j++,k--)aux=a[j],a[j]=a[k],a[k]=aux,viz[j]=true,viz[k]=true;
           }
       }
   }

  //det cartonas minim/maxim
  if(viz[1])k=a[1];
  else
  {
      i=1;while(!viz[i] && i<=N)i++;
      k=a[i-1];
  }

  //constructie sir de numere cu cifrele 7,8,9 pana la numarul de pe pozitia k
  fr7[1]=1;fr8[2]=1;fr9[3]=1;
  toate[1]=7;toate[2]=8;toate[3]=9;
  dim_sir=0;nr1=1;nr2=3;
  while(dim_sir<k)
  {
    c7=fr7[nr1];c8=fr8[nr1];c9=fr9[nr1];
    ncurent=toate[nr1];nr1++;nr2--;
    if(c7<=c8 && c8<=c9) dim_sir++;
    fr7[nr1+nr2]=c7+1;fr8[nr1+nr2]=c8;fr9[nr1+nr2]=c9;toate[nr1+nr2]=10*ncurent+7;nr2++;
    fr7[nr1+nr2]=c7;fr8[nr1+nr2]=c8+1;fr9[nr1+nr2]=c9;toate[nr1+nr2]=10*ncurent+8;nr2++;
    fr7[nr1+nr2]=c7;fr8[nr1+nr2]=c8;fr9[nr1+nr2]=c9+1;toate[nr1+nr2]=10*ncurent+9;nr2++;
  }

  //afisare
  g<<TAP<<endl<<ncurent<<endl;
  f.close();g.close();return 0;
  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 #1123 Iepurasi

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