1123 - Iepurasi

Se construieşte un şir de numere naturale care respectă restricţiile:

• primul număr din şir este 9;
• numerele se generează în ordine strict crescătoare;
• şirul conţine toate numerele formate doar cu cifrele 7, 8 şi 9 cu proprietatea că numărul cifrelor 9 este mai mare sau egal decât numărul cifrelor 8 şi numărul cifrelor 8 este mai mare sau egal decât numărul cifrelor 7. Primii 14 termeni ai şirului, în ordine, sunt: 9, 89, 98, 99, 789, 798, 879, 897, 899, 978, 987, 989, 998, 999.

Pornind de la aceste numere, Liv a inventat un joc interactiv: N iepuraşi sunt aşezaţi în şir, fiecare având câte un cartonaş. Fiecare cartonaş are două feţe, o faţă albă pe care este inscripţionat un număr din acest şir şi o faţă gri, pe care este inscripţionată poziţia acelui număr în şir, poziţii numerotate în ordine, începând cu valoarea 1.

Exemple. Cartonaşul care are pe faţa gri inscripţionat numărul 1 va avea pe faţa albă inscripţionat numărul 9, iar cartonaşul care are pe faţa gri inscripţionat numărul 5 va avea pe faţa albă inscripţionat numărul 789.

Iepuraşii sunt aşezaţi într-o ordine oarecare şi ţin cartonaşele astfel încât să se vadă faţa gri. Jocul constă în a rearanja iepuraşii de la stânga la dreapta, descrescător după numerele inscripţionate pe feţele gri, având la dispoziţie doar operaţia TAP pe un iepuraş. Când se aplică operaţia TAP unui iepuraş atunci secvenţa de iepuraşi, începând de la cel pe care s-a făcut TAP şi până la sfârşitul şirului (spre dreapta), este oglindită (ca în imaginea de mai sus). După oglindire, toţi iepuraşii din acea secvenţă ţin cartonaşele astfel încât să se vadă faţa albă. Se doreşte aplicarea unui număr cât mai mic de operaţii TAP pentru rearanjarea iepuraşilor.

Cerinţe

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de iepuraşi) şi a1, a2,…, aN (reprezentând, în ordine, numerele inscripţionate pe feţele gri) și care să determine:

a) Numărul minim de operaţii TAP necesare rearanjării iepuraşilor;

b) Cel mai mic număr aflat pe o faţă albă care nu se vede, în cazul în care au rămas cartonaşe neîntoarse. Dacă toate cartonaşele au fost întoarse (la toate fiind vizibilă faţa albă) se va afişa cel mai mare număr aflat pe o faţă albă a unui cartonaş.

Date de intrare

Fișierul de intrare iepurasi.in conține pe prima linie numărul natural N reprezentând numărul de iepuraşi. A doua linie a fişierului conţine, în ordine, cele N numere: a1, a_{2aN, separate prin câte un spaţiu, reprezentând în ordine, numerele inscripţionate pe feţele gri ale cartonașelor.}

Date de ieșire

Fișierul de ieșire iepurasi.out va conține pe prima linie un număr reprezentând numărul minim de operaţii TAP necesare rearanjării iepuraşilor. A doua linie va conține un număr reprezentând cel mai mic număr aflat pe o faţă albă care nu se vede (în cazul în care au rămas cartonaşe neîntoarse), respectiv cel mai mare număr aflat pe o faţă albă a unui cartonaş, în cazul în care toate cartonaşele au fost întoarse (la toate fiind vizibilă faţa albă).

Restricții și precizări

• 2 ≤ N ≤ 10000;
• 1 ≤ ai ≤ 10000 (1≤i≤N);
• N, a1, a2, …, aN sunt numere naturale;
• pentru rezolvarea cerinţei a) se acordă 50% din punctaj, iar pentru cerinţa b) se acordă 50% din punctaj.

Exemplu:

iepurasi.in

5 
14 5 8 9 10

iepurasi.out

1
999

Explicație

Se aplică o singură operaţie TAP pe iepuraşul cu numărul de ordine 5. Cartonaşul neîntors are numărul de ordine 14 (999).

Încărcare soluție

Lipește codul aici

import sys

f = open("iepurasi.txtin", "r")
g = open("iepurasi.txtout", "w")

toate = [0] * 200001
ncurent = 0
N = 0
a = [0] * 10001
dim_sir = 0
TAP = 0
nr1 = 0
nr2 = 0
viz = [False] * 10001
fr7 = [0] * 200001
fr8 = [0] * 200001
fr9 = [0] * 200001

def main():
    global N, a, TAP, viz
    i = 0
    j = 0
    k = 0
    maxi = 0
    imax = 0
    aux = 0
    c7 = 0
    c8 = 0
    c9 = 0

    #citire
    N = int(f.readline())
    a = list(map(int, f.readline().split()))

    #sortare descrescatoare
    for i in range(1, N + 1):
        imax = i
        maxi = a[i]
        for j in range(i + 1, N + 1):
            if a[j] > maxi:
                maxi = a[j]
                imax = j
        if imax != i:
            if a[N] != maxi:
                TAP += 1
                #TAP pe iepurasul imax
                for j in range(imax, k, -1):
                    aux = a[j]
                    a[j] = a[k]
                    a[k] = aux
                    viz[j] = True
                    viz[k] = True
            #TAP pe iepurasul i
            if a[i] != maxi:
                TAP += 1
                for j in range(i, k, -1):
                    aux = a[j]
                    a[j] = a[k]
                    a[k] = aux
                    viz[j] = True
                    viz[k] = True

    #det cartonas minim/maxim
    if viz[1]:
        k = a[1]
    else:
        i = 1
        while not viz[i] and i <= N:
            i += 1
        k = a[i - 1]

    #constructie sir de numere cu cifrele 7,8,9 pana la numarul de pe pozitia k
    fr7[1] = 1
    fr8[2] = 1
    fr9[3] = 1
    toate[1] = 7
    toate[2] = 8
    toate[3] = 9
    dim_sir = 0
    nr1 = 1
    nr2 = 3
    while dim_sir < k:
        c7 = fr7[nr1]
        c8 = fr8[nr1]
        c9 = fr9[nr1]
        ncurent = toate[nr1]
        nr1 += 1
        nr2 -= 1
        if c7 <= c8 and c8 <= c9:
            dim_sir += 1
        fr7[nr1 + nr2] = c7 + 1
        fr8[nr1 + nr2] = c8
        fr9[nr1 + nr2] = c9
        toate[nr1 + nr2] = 10 * ncurent + 7
        nr2 += 1
        fr7[nr1 + nr2] = c7
        fr8[nr1 + nr2] = c8 + 1
        fr9[nr1 + nr2] = c9
        toate[nr1 + nr2] = 10 * ncurent + 8
        nr2 += 1
        fr7[nr1 + nr2] = c7
        fr8[nr1 + nr2] = c8
        fr9[nr1 + nr2] = c9 + 1
        toate[nr1 + nr2] = 10 * ncurent + 9
        nr2 += 1

    #afisare
    g.write(str(TAP) + "\n" + str(ncurent) + "\n")
    f.close()
    g.close()
    sys.exit(0)

if __name__ == "__main__":
    main()