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ă cuX + 1
, consumând o picătură de poțiune magică, fie pe dala numerotată cu2 * 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 mult1000
de cifre; pentru o parte dintre teste, valorând în total 60 de puncte,P
are cel mult18
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ă maximum30
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
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()