Editing 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
<br>

== Exemplul 2 ==
; broscute.in

  4 1
  3 2 0 1 4
  1 2 3 4 0
; broscute.out

  3

<br>

== Exemplul 3 ==
; broscute.in

  4 2
  3 2 0 1 4
  3 2 0 1 4
; broscute.out

  broscutele nu se joaca

<br>

== 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>