2645 - minlex

Se consideră un cuvânt format numai din litere mici și un număr natural nenul K.

Cerința

Să se determine cuvântul minim lexicografic obținut prin eliminarea a exact K litere din cuvântul inițial.

Date de intrare

Programul citește de la tastatură numărul K, apoi cuvântul.

Date de ieșire

Programul va afișa pe ecran cuvântul rămas după eliminarea a exact K litere, minim lexicografic.

Restricții și precizări

• 3 ≤ lungimea cuvântului ≤ 1.000.000
• Cuvântul este format numai din litere mici ale alfabetului englez.
• 1 ≤ K < lungimea cuvântului
• Literele rămase după eliminare nu-și pot schimba ordinea în cuvânt.

Exemplul 1:

Intrare

5 zyizxtnfo

Ieșire

Datele de intrare corespund restrictiilor impuse

info

Exemplul 2:

Intrare

0

Ieșire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

def validare(litera_k, word): # functia de validare a datelor de intrare

   if 1 > litera_k or litera_k >= len(word) or len(word) > 1000000:
       raise ValueError
   if not word.islower():
       raise ValueError
   print("Datele de intrare corespund restrictiilor impuse\n")

def elimina_litere(litera_k, word): # functia de rezolvare

   stiva = []
   for litera in word:
       while litera_k > 0 and stiva and stiva[-1] > litera:
           stiva.pop()
           litera_k -= 1
       stiva.append(litera)
   while litera_k > 0:
       stiva.pop()
       litera_k -= 1
   return .join(stiva)

if __name__ == '__main__':

   try:
       k, cuvant = input("Introduceți numărul K și cuvântul, separate printr-un spațiu: ").split()
       k = int(k)
       validare(k, cuvant)
       rezultat = elimina_litere(k, cuvant)
       print(str(rezultat) + '\n')
   except ValueError:
       print("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       print("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>