1213 - Iepuras

Enunt

Iepurașul Coconaș vrea să ajungă la grădina cu morcovi. Pentru aceasta el trebuie să traverseze prin salturi o zonă cu proprietăți speciale. Zona este formată din N căsuțe numerotate de la 1 la N, dispuse una după cealaltă, iar fiecare căsuță conține un număr natural ce reprezintă cantitatea de energie necesară iepurașului pentru a sări într-o altă căsuță.

Iepurașul pleacă dintr-o anumită căsuță și se deplasează, de la stânga la dreapta, spre grădina cu morcovi după următoarele reguli:

• numărul înscris în căsuța în care se află iepurașul reprezintă numărul de căsuțe peste care el va sări;

dacă numărul înscris în căsuța în care se află iepurașul este număr prim, atunci energia lui se dublează şi va sări peste un număr dublu de căsuţe; numărarea căsuțelor peste care va sări se face de la stânga la dreapta și începe cu căsuța imediat următoare.

• Astfel, dacă iepurașul se află în căsuța a treia și numărul înscris în această căsuță este 5, iepurașul va ajunge în căsuța cu numărul de ordine 13 (13=3+2*5).

dacă iepurașul ajunge într-o căsuță care conține numărul 0, el rămâne acolo pentru că nu mai are energie să sară mai departe, altfel el continuă să sară după regulile descrise mai sus; iepurașul ajunge la grădina cu morcovi dacă ultimul salt pe care îl face depășește căsuța N.

Cerinţa

Scrieți un program care citește trei numere naturale P, N și K iar apoi N numere naturale și determină:

1) dacă iepurașul poate ajunge sau nu, la grădina cu morcovi pornind din căsuța K și numărul de salturi pe care le face iepurașul pornind din căsuța K; 2) căsuța de pornire a iepurașului, astfel încât drumul parcurs de el să traverseze un număr maxim de căsuțe. Pentru a determina numărul de căsuțe se vor lua în calcul: căsuța de pornire, toate căsuțele peste care iepurașul a sărit și toate căsuțele în care a ajuns în urma salturilor. Iepurașul poate porni din oricare căsuță. În cazul în care există două sau mai multe căsuțe de pornire care conduc la același număr maxim de căsuțe traversate se va lua în considerare căsuța cu numărul de ordine cel mai mic.

Date de intrare

Fişierul de intrare iepuras.in conţine pe prima linie un număr natural P. Pentru toate testele de intrare, numărul P poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie a fișierului iepuras.in se găsesc, în această ordine, numerele naturale N și K, separate prin câte un spațiu. Pe a treia linie se găsesc N numere naturale separate prin câte un spațiu, reprezentând valorile din fiecare căsuță în ordine de la 1 la N.

Date de ieșire

Dacă valoarea lui P este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire iepuras.out va conține pe prima linie cuvântul DA în cazul în care iepurașul a ajuns în grădina cu morcovi , respectiv cuvântul NU în caz contrar, iar pe a doua linie va conține un număr natural reprezentând numărul de salturi pe care le face iepurașul pornind din căsuța K.

Dacă valoarea lui P este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire iepuras.out va conține pe prima linie două numere naturale separate printr-un spaţiu reprezentând, în ordine, căsuța de pornire și numărul maxim de căsuțe determinat, iar pe a doua linie, un șir de numere naturale separate prin câte un spațiu reprezentând numerele din căsuțele în care iepurașul nu s-a aflat sau nu a sărit pe parcursul drumului, de la stânga la dreapta, începând cu căsuța 1. Dacă numărul maxim de căsuțe traversate este chiar N linia a doua nu va conține niciun număr.

Restricţii şi precizări

• 1 ≤ N ≤ 7000
• 1 ≤ K ≤ N
• 0 ≤ numerele conţinute în căsuţe ≤ 100
• Pentru rezolvarea corectă a primei cerinţe se acordă 30 de puncte, pentru rezolvarea corectă a celei de a doua cerințe se acordă 70 de puncte.

Exemplul 1

iepuras.in

 1
 14 3
 2 3 4 0 1 1 2 1 4 0 0 2 1 1

iepuras.out

 NU
 2

Explicație

• P = 1, pentru acest test, se rezolva cerința 1).

Exemplul 2

iepuras.in

 2
 14 3
 2 3 6 0 1 1 2 1 4 0 0 2 3 1

iepuras.out

 2 13
 2 6 0 1 1 2 0 0 2 1

Explicație

• P = 2, pentru acest test, se rezolvă cerința 2).

Pentru a traversa un număr maxim de căsuțe, iepurașul pleacă din căsuța cu numărul de ordine 2 și sare, pe rând, în căsuțele cu numerele de ordine 8, 9, 13, și apoi în grădină, traversând astfel 13 căsuţe (de la căsuța 2 la căsuța 14).

Iepurașul nu s-a aflat sau nu a sărit în căsuţele de pe poziţiile 1, 3, 4, 5, 6, 7, 10, 11, 12 și 14.

Rezolvare

<syntaxhighlight lang="python" line> def can_reach_garden(N, K, houses):

   energy = houses[K - 1]
   jumps = 0

   while K <= N:
       jumps += 1
       K += energy
       if K > N:
           return True, jumps
       energy = houses[K - 1] if houses[K - 1] > 1 else energy * 2

   return False, jumps

def find_starting_house(N, houses):

   max_houses = 0
   starting_house = 0

   for i in range(1, N + 1):
       energy = houses[i - 1]
       jumps = 1
       current_house = i

       while current_house + energy <= N:
           jumps += 1
           current_house += energy
           energy = houses[current_house - 1] if houses[current_house - 1] > 1 else energy * 2

       if jumps > max_houses:
           max_houses = jumps
           starting_house = i

   return starting_house, max_houses

def main():

   with open("iepuras.in", "r") as fin:
       P = int(fin.readline().strip())
       N, K = map(int, fin.readline().split())
       houses = list(map(int, fin.readline().split()))

   if P == 1:
       can_reach, jumps = can_reach_garden(N, K, houses)
       with open("iepuras.out", "w") as fout:
           fout.write("DA\n" if can_reach else "NU\n")
           fout.write(str(jumps))
   elif P == 2:
       starting_house, max_houses = find_starting_house(N, houses)
       not_visited_houses = [i for i in range(1, N + 1) if i != starting_house]

       with open("iepuras.out", "w") as fout:
           fout.write(f"{starting_house} {max_houses}\n")
           fout.write(" ".join(map(str, not_visited_houses)))

if __name__ == "__main__":

   main()

</syntaxhighlight>