Editing 1123 - Iepurasi

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

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

Pornind de la aceste numere, Liv a inventat un joc interactiv: <code>N</code> 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 <code>1</code>.

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

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 <code>TAP</code> pe un iepuraş. Când se aplică operaţia <code>TAP</code> unui iepuraş  atunci secvenţa de iepuraşi,  începând de la cel pe care s-a făcut <code>TAP</code> ş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 <code>N</code> (reprezentând numărul de iepuraşi) şi <code>a<sub>1</sub></code>, <code>a<sub>2</sub></code>,…, <code>a<sub>N</sub></code>  (reprezentând, în ordine,  numerele inscripţionate pe feţele gri) și care să determine:

'''a)''' Numărul minim de operaţii <code>TAP</code> 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 <code>iepurasi.in</code> conține pe prima linie numărul natural <code>N</code> reprezentând numărul de iepuraşi. A doua linie a fişierului conţine, în ordine, cele <code>N</code> numere: <code>a<sub>1</sub></code>, <code>a<sub>2</sub></code><sub>a<code>N</code>, separate prin câte un spaţiu, reprezentând în ordine, numerele inscripţionate pe feţele gri ale cartonașelor.</sub>

= Date de ieșire =
Fișierul de ieșire <code>iepurasi.out</code> va conține pe prima linie un număr reprezentând numărul minim de operaţii <code>TAP</code> 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 =

* <code>2 ≤ N ≤ 10000</code>;
* <code>1 ≤ a<sub>i</sub> ≤ 10000</code> (<code>1≤i≤N</code>);
* <code>N, a<sub>1</sub></code>, <code>a<sub>2</sub></code>, …, <code>a<sub>N</sub></code> sunt numere naturale;
* pentru rezolvarea cerinţei a) se acordă 50% din punctaj, iar pentru cerinţa b) se acordă 50% din punctaj.

= Exemplu: =
<code>iepurasi.in</code>
 5 
 14 5 8 9 10
<code>iepurasi.out</code>
 1
 999

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

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
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()
</syntaxhighlight>