Editing 2977 - Poarta 1


Sindbad a descoperit un recipient care conține o poțiune magică și o inscripție care descrie cum se poate deschide poarta unui templu. Urmând instrucțiunile din inscripție, Sindbad a ajuns la un tunel acoperit cu dale pătrate, aliniate astfel încât formează linii și coloane. Tunelul are mai multe linii, iar pe fiecare linie sunt câte <code>N</code> dale. Dalele din tunel sunt numerotate începând cu <code>1</code>, astfel încât, parcurgându-le linie cu linie și fiecare linie de la stânga la dreapta, se obține un șir strict crescător de numere naturale consecutive. Sindbad se află la intrare, înaintea primei linii. Pentru a deschide poarta templului, el trebuie să ajungă pe dala numerotată cu <code>P</code>, călcând pe un număr minim de dale. Dacă există mai multe astfel de soluții, o va alege pe cea pentru care consumul total de picături de poțiune magică este minim. Pe parcursul deplasării el trebuie să respecte următoarele reguli:

* de la intrare, poate sări pe orice dală aflată pe prima line, fără a consuma poțiune magică;
* de pe o dală numerotată cu <code>X</code>, Sindbad poate sări fie pe dala numerotată cu <code>X + 1</code>, consumând o picătură de poțiune magică, fie pe dala numerotată cu <code>2 * X</code>, consumând două picături de poțiune magică.

= Cerința =
Scrieți un program care citește valorile <code>N</code> și <code>P</code> cu semnificația din enunț și rezolvă următoarele cerințe:

1. afișează numărul minim de dale pe care trebuie să calce pentru a deschide poarta;

2. afișează numărul natural <code>T</code>, reprezentând numărul minim de picături de poțiune magică necesare pentru deschiderea porții.

= Date de intrare =
Fișierul de intrare <code>poarta.in</code> conține pe prima linie un număr natural <code>C</code> reprezentând cerința din problemă care trebuie rezolvată (<code>1</code> sau <code>2</code>). Pe a doua linie se află numărul natural <code>N</code>, iar pe a treia linie se află numărul natural <code>P</code> cu semnificația din enunț.

= Date de ieșire =
Fișierul de ieșire <code>poarta.out</code> va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerința <code>C</code>.

= Restricții și precizări =

* <code>2 ≤ N < 10.000</code>
* <code>P</code> este număr natural nenul cu cel mult <code>1000</code> de cifre; pentru o parte dintre teste, valorând în total 60 de puncte, <code>P</code> are cel mult <code>18</code> cifre.
* Recipientul conține o cantitate suficientă de poțiune magică.
* Pentru rezolvarea '''cerinței 1''' se acordă maximum <code>60</code> de puncte, iar pentru rezolvarea '''cerinței 2''' se acordă maximum <code>30</code> de puncte.
* În concurs s-au acordat <code>10</code> puncte din oficiu. Aici se acordă pentru exemplele din enunț.

=== Explicație ===
Tunelul are <code>5</code> dale pe fiecare linie. Sindbad trebuie să ajungă pe dala numerotată cu <code>9</code>. Numărul minim de dale pe care trebuie să calce pentru a ajunge pe dala <code>9</code> pentru a deschide poarta este <code>3</code>. De pe margine poate sări:

– pe dala numerotată cu <code>4</code> (consumă <code>0</code> picături de poțiune magică);

– de pe dala numerotată cu <code>4</code> pe cea numerotată cu <code>8</code> (consumă <code>2</code> picături de poțiune magică);

– de pe dala numerotată cu <code>8</code> pe cea numerotată cu <code>9</code> (consumă <code>1</code> picătură de poțiune magică).

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
def main():
    i = 0
    k = 1
    ck = 0
    nv = 0
    j = 0
    v = [0] * 1001
    nk = 0
    gata = False
    cer = 0
    pas = 0
    n = 0
    ok = 0
    T = 0
    c = ''
    f = open("poarta.in", "r")
    g = open("poarta.out", "w")
    cer, n = map(int, f.readline().split())
    nv = 0
    ok = 0
    while True:
        c = f.read(1)
        if not c:
            break
        if c >= '0' and c <= '9':
            nv += 1
            v[nv] = int(c)
    f.close()
    ck = n
    while ck:
        nk += 1
        ck = ck // 10
    while not gata:
        j = 0
        k += 1
        if v[nv] % 2 == 0:
            T += 2
            pas = 2
            for i in range(1, nv + 1):
                j = j * 10 + v[i]
                v[i] = j // 2
                j = j % 2
        else:
            T += 1
            pas = 1
            v[nv] -= 1
        if v[1] == 0:
            i = 1
            j = 1
            while v[i] == 0:
                i += 1
            nv = nv - i + 1
            while j <= nv:
                v[j] = v[i]
                j += 1
                i += 1
        if nv <= nk:
            ck = 0
            for i in range(1, nv + 1):
                ck = ck * 10 + v[i]
            if ck <= n:
                gata = True
    if pas == 2 and ck * 2 == n + 1:
        ck = n
        T = T - 1
    if cer == 1:
        g.write(str(k) + "\n")
    else:
        g.write(str(T) + "\n")
    g.close()
    return 0

if __name__ == "__main__":
    main()

</syntaxhighlight>