1499 - Broscute

Enunt

Pe un lac cu apă termală se află n+1 frunze de nuferi. Pe n dintre ele stau la soare n broscuțe. Evident, o frunză este liberă și broscuţele au început să se joace. În fiecare moment o broscuță sare de pe frunza ei pe frunza liberă din acel moment.

Cerinţa

Numerotând frunzele de la 1 la n+1, broscuțele de la 1 la n, şi cunoscându-se ordinea inițială a broscuțelor pe cele n+1 frunze, să se determine numărul minim de sărituri ale broscuțelor de pe o frunză pe alta, astfel încât ele să se găsească într-o ordine finală, dată, precum şi săriturile realizate.

Date de intrare

Fișierul de intrare broscute.in conține pe prima linie un număr natural n reprezentând numărul de broscuțe separat printr-un spațiu de un număr natural t, care reprezintă cerința: 1, dacă se cere numărul de sărituri, respectiv 2 dacă se cere ordinea săriturilor. Linia a doua conține n+1 numere naturale reprezentând configurația inițială a broscuțelor pe cele n+1 frunze, iar linia a treia conține n+1 numere naturale reprezentând configurația finală a broscuțelor pe cele n+1 frunze.

Date de ieșire

Fișierul de ieșire broscute.out va conține pe prima linie un număr natural k ce reprezintă numărul minim de sărituri, dacă cerința este 1. Dacă cerința este 2 fișierul de ieșire va conține mai multe linii, pe fiecare dintre ele existând 3 numere naturale b s d, separate prin câte un spațiu, care descriu săritura, reprezentând numărul broscuței b, frunza de pe care sare s și frunza pe care sare d. În cazul în care la cerința 2 broscuțele nu fac nici o săritură se va afișa pe prima linie mesajul 'broscutele nu se joaca.

Restricţii şi precizări

• 2 ≤ n ≤ 1000
• În descrierea configurațiilor din fișierul de intrare frunza liberă este reprezentată prin valoarea 0
• Pentru cerința 1 se acordă 50% din punctaj, iar pentru cerința 2 tot 50% din punctaj.
• În cazul în care cerința este 2 și numărul de sărituri afișate nu este minim dar realizează ajungerea la configurația finală se acordă doar 30% din punctaj.

Exemplul 1

broscute.in

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

broscute.out

 3 1 3
 1 4 1
 4 5 4

Explicație

Sunt 4 broscuţe, deci 5 frunze de nufăr. Cerinţa este 2.

• Broscuţele vor face 3 sărituri:
• broscuţa 3 sare de pe frunza 1 pe frunza 3
• broscuţa 1 sare de pe frunza 4 pe frunza 1
• broscuţa 4 sare de pe frunza 5 pe frunza 4

Exemplul 2

broscute.in

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

broscute.out

 3

Exemplul 3

broscute.in

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

broscute.out

 broscutele nu se joaca

Rezolvare

<syntaxhighlight lang="python" line> def min_jumps_or_order(n, initial_config, final_config, request):

   if request == 1:
       return min_jumps(n, initial_config, final_config)
   elif request == 2:
       return min_jumps_order(n, initial_config, final_config)

def min_jumps(n, initial_config, final_config):

   jumps = 0
   for i in range(n+1):
       if initial_config[i] != final_config[i]:
           jumps += 1
   return jumps

def min_jumps_order(n, initial_config, final_config):

   jumps = []
   for i in range(n+1):
       if initial_config[i] != final_config[i]:
           for j in range(i+1, n+1):
               if final_config[i] == initial_config[j]:
                   jumps.append((j, initial_config.index(final_config[i]), i))
                   initial_config[j], initial_config[i] = initial_config[i], initial_config[j]
                   break
   if not jumps:
       return "broscutele nu se joaca"
   return jumps

def main():

   with open("broscute.in", "r") as fin:
       n, request = map(int, fin.readline().split())
       initial_config = list(map(int, fin.readline().split()))
       final_config = list(map(int, fin.readline().split()))

   result = min_jumps_or_order(n, initial_config, final_config, request)

   with open("broscute.out", "w") as fout:
       if request == 1:
           fout.write(f"{result}\n")
       elif request == 2:
           if isinstance(result, str):
               fout.write(result)
           else:
               fout.write('\n'.join([' '.join(map(str, jump)) for jump in result]))

if __name__ == "__main__":

   main()

</syntaxhighlight>