Rezolvare completă PbInfo #1615 AXYZ

Se consideră numerele naturale A (format din două sau trei cifre, toate distincte și nenule) și X (format din N cifre, toate nenule).

Din numărul X, folosind toate cele N cifre ale sale, se poate construi un cel mai mare număr natural Y strict mai mic decât X. De exemplu, pentru X=121621 se construiește Y=121612.

Tot din numărul X, se poate obține numărul A prin ștergerea unor cifre din scrierea lui X și alipirea celor rămase, fără a le schimba ordinea. De exemplu, dacă X=121621 și A=12, există Z=3 posibilități distincte prin care să obținem numărul A din X și anume: 1) 121621; 2) 121621; 3) 121621.

Cerința

Cunoscându-se numerele A, N și cele N cifre ale lui X, să se determine:

1. cel mai mare număr natural Y, strict mai mic decât X, care se poate obține rearanjând cifrele lui X;
2. numărul maxim Z de posibilități distincte prin care se poate obține numărul A din numărul X prin ștergerea unor cifre și alipirea celor rămase, fără a le schimba ordinea.

Date de intrare

Fișierul de intrare axyz.in conține:

  • pe prima linie un număr natural p; pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2;
  • pe a doua linie, numărul A, cu semnificația din enunț;
  • pe a treia linie numărul de cifre ale numărului X;
  • pe a patra linie, un șir de N cifre, separate prin câte un spațiu, reprezentând cifrele numărului X, în această ordine.

Date de ieșire

  • Dacă valoarea lui p este 1, atunci se va rezolva numai cerința 1. În acest caz, fişierul de ieşire axyz.out va conţine pe prima linie un șir de cifre reprezentând numărul natural Y determinat (răspunsul la cerința 1).
  • Dacă valoarea lui p este 2, atunci se va rezolva numai cerința 2. În acest caz, fişierul de ieşire axyz.out va conține pe prima linie un număr natural reprezentând numărul Z determinat (răspunsul la cerința 2).

Restricții și precizări

  • 12 ≤ A ≤ 987
  • 10 ≤ N ≤ 30000
  • Pentru toate datele de test, numerele Y și A pot fi obținute din numărul X
  • Pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.

Exemplul 1

axyz.in

1
12
6
1 2 1 6 2 1

axyz.out

121612

Explicație

Se rezolvă cerința 1.
A=12, N=6, X=121621
Cel mai mare număr Y strict mai mic ca X este: Y=121612

Exemplul 2

axyz.in

2
12
6
1 2 1 6 2 1

axyz.out

3

Explicație

Se rezolvă cerința 2. A=12, N=6, X=121621
Sunt Z=3 posibilități distincte prin care se obține numărul A din X:
1) 121621; 2) 121621; 3) 121621.

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

#include <fstream>

using namespace std;

int x[30001];
ifstream f("axyz.in");
ofstream g("axyz.out");

int main()
{
    int N,A,B,C,NB,Z,i,k,j, poz, t,cer;
    f>>cer>>A>>N;
    for(i=1; i<=N; i++)
        f>>x[i];
///cerinta 1) - problema are solutie pentru toate testele propuse
    if(cer==1)
    {
        k=N-1;
        while(k>0 && x[k]<=x[k+1])k--;
        poz=N;
        while(poz>k && x[poz]>=x[k])poz--;
        swap(x[k],x[poz]);
        for(i=1; i<=k; i++)g<<x[i];
        for(i=N; i>k; i--)g<<x[i];
    g<<'\n';
    }
    else ///cerinta 2
    if(A<100){
        B=A%10;
        A=A/10;
        Z=0;
        NB=0;
        for(i=N; i>=1; i--)
            if(x[i]==B)NB++;
            else if(x[i]==A)Z+=NB;
        g<<Z<<'\n';
    }
    else
        { int i,C,NC=0,NBC=0,Z=0;
          C=A%10; A/=10; B=A%10; A/=10;
          for (i=N; i>=1;i--)
            if(x[i]==C)NC++;
            else if(x[i]==B)NBC+=NC;
                else if(x[i]==A)Z+=NBC;
          g<<Z<<'\n';
        }
    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 #1615 AXYZ

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