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 N dale. Dalele din tunel sunt numerotate începând cu 1, 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 P, 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 X, Sindbad poate sări fie pe dala numerotată cu X + 1, consumând o picătură de poțiune magică, fie pe dala numerotată cu 2 * X, consumând două picături de poțiune magică.

Cerința

Scrieți un program care citește valorile N și P 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 T, reprezentând numărul minim de picături de poțiune magică necesare pentru deschiderea porții.

Date de intrare

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

Date de ieșire

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

Restricții și precizări

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

Explicație

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

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

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

– de pe dala numerotată cu 8 pe cea numerotată cu 9 (consumă 1 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>