Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-03-15 13:36:35.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cuvinte.in, cuvinte.outSursăStelele Informaticii 2003, clasele 9-10
AutorMihai StroeAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.05 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Cuvinte

Doi prieteni, Marius si Andrei, s-au gandit la un joc. Marius scrie pe o foaie un sir de N numere. Sub fiecare numar, el scrie cate o litera: sub primul numar litera A, sub al doilea numar litera B, si tot asa, in ordine lexicografica. Marius si Andrei folosesc un alfabet cu cateva mii de litere, cunoscut numai de ei si care incepe cu literele de la A la Z (pentru a putea fi folosit si in comunicarea cu alti oameni). Literele sunt deci folosite ca indici pentru numerele din sir. Andrei cauta apoi toate cuvintele posibile care respecta urmatoarele conditii:

  • un cuvant reprezinta un sir de litere, ordonat lexicografic
  • numerele din sir, corespunzatoare literelor dintr-un cuvant si scrise in ordinea data de acestea, sunt in ordine strict crescatoare

De exemplu, pentru sirul 2 1 3 5 4, scriind dedesubt literele A B C D E, cateva dintre cuvintele valide sunt AC, ACD, ACE, dar AB, ED sau BDE nu sunt cuvinte valide. Apoi, Andrei alege dintre aceste cuvinte pe cele de lungime maxima si le scrie in ordine lexicografica. Dintre aceste cuvinte de lungime maxima, el i-l spune lui Marius pe al K-lea. Daca Andrei spune corect (si repede) cuvantul, el castiga jocul.

Cerinta

Scrieti un program care determina cuvantul cerut si il ajuta pe Andrei sa castige jocul.

Date de intrare

Fisierul de intra cuvinte.in contine pe prima linie doua numere N si K, separate printr-un spatiu, reprezentand numarul de numere din sir, respectiv numarul de ordine al cuvantului cerut. Pe a doua linie se afla N numere intregi separate printr-un spatiu, numerele scrise de Marius pe foaie.

Date de iesire

In fisierul cuvinte.out se va scrie cuvantul cerut. Deoarece nu se cunosc literele care urmeaza dupa Z in alfabetul celor doi, in locul literelor cuvantului se vor scrie numerele de ordine ale acestora in alfabet. Astfel, de exemplu cuvantul ACZ ar fi scris ca 1 3 26.

Restrictii

  • 2 ≤ N ≤ 200
  • 1 ≤ K ≤ 2 000 000 000
  • Numere din sir sunt intregi cuprinse intre 0 si 10 000 inclusiv
  • Se garanteaza ca exista solutie si se pot forma cel mult 2 000 000 000 de cuvinte de lungime maxima

Exemplu

cuvinte.incuvinte.out
5 3
2 1 3 5 4
2 3 4

Explicatie

Numerele din fisierul de iesire corespund pozitiilor 2, 3 si 4 din sir pe care se afla numerele 1, 3 si 5.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?