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

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()