3356 - Alfa

Cerinţa

Se dă un șir format din n numere naturale. Se mai dă o valoare x și se garantează că șirul începe și se termină cu valoarea x. Transformați șirul astfel:

• Elementele cu valoarea x rămân pe pozițiile lor;
• Secvențele de elemente diferile de x aflate între două poziții cu valoarea x se ordonează crescător (între aceleași două elemente cu valoarea x se vor afla aceleași elemente ca la început dar în ordine crescătoare).

Date de intrare

Fișierul alfain.txt conține pe prima linie un număr natural n reprezentând dimensiunea șirului și un număr x cu semnificația de mai sus. Pe linia a doua n numere naturale, separate prin câte un spațiu, reprezentând elementele șirului.

Date de ieşire

Fișierul alfaout.txt conține cele n elemente ale șirului în ordinea cerută.

Restricții și precizări

• 2 <= n <= 1000
• Elementele șirului dat sunt naturale nenule formate din maximum 4 cifre
• Pentru 40 de puncte șirul conține doar două elemente cu valoarea x (primul și ultimul).

Exemplul 1

alfain.txt

10 3

3 4 1 2 3 7 9 8 3 3

alfaout.txt

Datele introduse corespund restricțiilor impuse.

3 1 2 4 3 7 8 9 3 3

Exemplul 2

alfain.txt

1 3

3 4 1 2 3 7 9 8 3 3

alfaout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line> def validare(lungime_intrare1, numar_tinta1, lista_numere1): # functia de validare a datelor de intrare

   if lungime_intrare1 > 1000 or lungime_intrare1 < 2:
       raise ValueError
   if len(lista_numere1) != lungime_intrare1:
       raise ValueError
   if lista_numere1[0] != numar_tinta1 or lista_numere1[-1] != numar_tinta1:
       raise ValueError
   for numar in lista_numere1:
       if not (0 < numar < 10000):
           raise ValueError
   return "Datele de intrare corespund restrictiilor impuse."

def transforma_lista(lungime_intrare1, numar_tinta1, lista_numere1):

   i = 0
   while i < lungime_intrare1:
       if lista_numere1[i] == numar_tinta1:
           j = i + 1
           while j < lungime_intrare1 and lista_numere1[j] != numar_tinta1:
               j += 1
           if j < lungime_intrare1:
               lista_numere1[i + 1:j] = sorted(lista_numere1[i + 1:j])
           i = j
       else:
           i += 1
   return lista_numere1

if __name__ == '__main__':

   file_in = open("alfain.txt", "r")         # declararea fisierelor
   file_out = open("alfaout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       lungime_intrare, numar_tinta = map(int, file_in.readline().split())
       lista_numere = list(map(int, file_in.readline().split()))

       mesaj_validare = validare(lungime_intrare, numar_tinta, lista_numere)   # apelul functiei de validare
       lista_numere = transforma_lista(lungime_intrare, numar_tinta, lista_numere)     # apelul functiei de rezolvare

       file_out.write(mesaj_validare + '\n')
       file_out.write(' '.join(map(str, lista_numere)) + '\n')

   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>