Rezolvare PBinfo #1615

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.