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 alfa.in 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 alfa.out 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).

Exemplu

alfa.in

10 3

3 4 1 2 3 7 9 8 3 3

alfa.out

3 1 2 4 3 7 8 9 3 3

Rezolvare

def transforma_sir(n, x, sir):
    i = 0
    while i < n:
        if sir[i] == x:
            j = i + 1
            while j < n and sir[j] != x:
                j += 1
            if j < n:
                sir[i+1:j] = sorted(sir[i+1:j])
            i = j
        else:
            i += 1
    return sir

if __name__ == "__main__":
    n = 10
    x = 3
    sir = [3, 4, 1, 2, 3, 7, 9, 8, 3, 3]
    print(transforma_sir(n, x, sir))