Fişierul intrare/ieşire:calandrinon.in, calandrinon.outSursăFMI No Stress 6
AutorAndrei Cristian LambruAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Calandrinon

Problema spune că avem un şir de caractere de lungime N format doar din litere mici ale alfabetului englez. Pasărea cea albă vă roagă să eliminaţi o parte din aceste caractere astfel încât şirul rezultat în urma tuturor eliminărilor să aibe concomitent următoarele proprietăţi:

  1. Să conţină numai elemente distincte
  2. Să fie de lungime maximă posibilă
  3. Să fie minim lexicografic in comparaţie cu orice alt şir care ar respecta primele 2 condiţii după o posibilă serie de eliminări

De exemplu, dacă aţi avea şirul alblb, o posibilă serie de eliminări ar fi alegerea primului l şi a primului b astfel încât şirul rezultat în final va fie alb. Acest şir respectă primele două proprietăţi, dar nu şi pe cea de-a treia deoarece există o altă serie de eliminări care rezultă într-un şir din punct de vedere lexicografic mai mic şi anume şirul abl prin eliminarea primului l şi a celui de-al doilea b. Aceasta din urmă este şi soluţia acceptată de pasărea cea albă în cazul şirului dat ca exemplu.

Date de intrare

Fişierul de intrare calandrinon.in va conţine pe prima linie o singură valoare, N, reprezentând numărul de caractere al şirului.
Pe cea de-a doua linie a fişierului se vor afla N caractere reprezentând şirul iniţial.

Date de ieşire

Pe prima şi singura linie a fişierului de ieşire calandrinon.out se vor afla caracterele şirului rezultat în urma eliminărilor.

Restricţii

  • 1 ≤ N ≤ 106
  • Spunem că un şir de caractere a1,a2...aM este mai mic lexicografic decât un şir b1, b2...bM dacă există o poziţie 1iM astfel încât a1 = b1, a2 = b2 ... ai-1 = bi-1 şi ai < bi.
  • Pentru 25% din teste, sirul va putea conţine doar caracterele (a, b, c, d, e, f, g)

Exemplu

calandrinon.incalandrinon.out
29
vinefarasochemiiauzibatengeam
vefarsochiuzbtngm
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?