RebecaBud: Pagină nouă: == 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 brosc...

2024-06-03T16:16:49Z

Pagină nouă: == 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 brosc...

New page

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

1499 - Broscute - Revision history