unificare

Time limit: 0.2s Memory limit: 64MB Input: unificare.in Output: unificare.out

Prin operația de unificare a două numere naturale aa și bb înțelegem obținerea celui mai mare număr care se poate forma din cifrele distincte din scrierea numărului aa și cifrele distincte din scrierea numărului bb. De exemplu, unificând a=727952a = 727952 cu b=92868b = 92868 vom obține numărul 9987652299876522, deoarece din aa vom utiliza cifrele 2,5,7,92, 5, 7, 9, iar din bb cifrele 2,6,8,92, 6, 8, 9. Cel mai mare număr pe care îl putem forma cu aceste cifre este 9987652299876522.

Operația de unificare poate fi aplicată și pentru kk numere, respectând aceeași regulă: pentru fiecare număr din cele kk identificăm cifrele distincte care apar în scrierea lui, apoi determinăm cel mai mare număr care se poate forma utilizând toate aceste cifre. De exemplu, unificând numerele 112112, 223223 și 1233412334 vom obține 4332221143322211.

Se dau două numere naturale, nn și kk, și un șir de nn numere naturale a1,a2,...,ana_1, a_2, ..., a_n.

Cerințe

Determinați și afișați:

  1. cel mai mare număr de exact kk cifre din șirul dat;
  2. cel mai mare număr care poate fi obținut prin unificarea a două valori aflate pe poziții alăturate în șirul dat;
  3. cel mai mare număr care se poate obține prin unificarea a kk valori aflate pe poziții consecutive în șirul dat.

Date de intrare

Fișierul de intrare unificare.in conține pe prima linie un număr natural CC, reprezentând cerința ce trebuie rezolvată (11, 22 sau 33), pe a doua linie nn și kk, cu semnificația din enunț, iar pe a treia linie cei nn termeni ai șirului precizațîn ordinea din șir. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire unificare.out:

  • dacă C=1C = 1, se va afișa pe prima linie cel mai mare număr de kk cifre din șirul dat;
  • dacă C=2C = 2, se va afișa pe prima linie cel mai mare număr obținut prin unificarea a două numere alăturate în șir;
  • dacă C=3C = 3, se va afișa pe prima linie valoarea maximă obținută prin unificarea a kk valori aflate pe poziții consecutive.

Restricții și precizări

  • C{1,2,3}C \in \{1,2,3\}; 1n100 0001 \leq n \leq 100 \ 000; 1kn/21 \leq k \leq n/2;
  • 0ai100 000 0000 \leq a_i \leq 100 \ 000 \ 000, pentru oricare 1in1 \leq i \leq n;
  • Pentru 2020 de puncte, C=1C = 1 și k8k \leq 8;
  • Pentru 55 puncte, C=2C = 2 și n=2n = 2;
  • Pentru 1010 puncte, C=2C = 2 și 0ai90 \leq a_i \leq 9, pentru oricare 1in1 \leq i \leq n;
  • Pentru 3535 de puncte, C=2C = 2 și nu există restricții suplimentare;
  • Pentru 1515 puncte, C=3C = 3 și k8k \leq 8;
  • Pentru 1515 puncte, C=3C = 3 și kn/2k \leq n / 2.

Exemplul 1

unificare.in

1
5 3
112 223 12334 561 289

unificare.out

561

Explicație

C=1C = 1, n=5n = 5 și k=3k = 3. În șir sunt 44 numere care au exact 33 cifre: 112112, 223223, 561561 și 289289, cel mai mare dintre ele fiind 561561.

Exemplul 2

unificare.in

2
5 3
112 223 12334 561 289

unificare.out

6543211

Explicație

C=2C = 2, n=5n = 5 și k=3k = 3, nu utilizăm valoarea lui kk și unificând a3a_3 cu a4a_4 vom obține cea mai mare valoare: 65432116543211.

Exemplul 3

unificare.in

3
5 3
112 223 12334 561 289

unificare.out

9865432211

Explicație

C=3C = 3, n=5n = 5 și k=3k = 3. Cea mai mare valoare care se poate obține este 98654322119865432211 și o obținem unificând a3a_3 cu a4a_4 și cu a5a_5.

Log in or sign up to be able to send submissions!