Rezolvare PBinfo #1499

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