# PBinfo #1499 – Broscute – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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

## Cod sursă C++

```cpp
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("broscute.in");
ofstream fout("broscute.out");
#define DIM 1004
struct mutari {
    int b, s, d;                   // b - nr broscutei   s - de unde a plecat    d - unde a ajuns
} Mutari[DIM * 10];
int n, c, pozA[DIM], pozB[DIM], V[DIM], Final[DIM];
/*
    V - Configuratia actuala
    Final - Configuratia finala
    PozA[i] - pozitia broscutei i din configuratia actuala
    PozB[i] - pozitia broscutei i din configuratia finala
*/
int main() {
    fin >> n>> c;                  // Citim numarul de broscute si tipul cerintei
    ++n;                           // Nr de Frunze = Nr de Broscute + 1
    for(int i = 1; i <= n; ++i) {
        fin >> V[i];               // Citim configuratia initiala
        pozA[V[i]] = i;            // Si construim vectorul PozA
    }
    for(int i = 1; i <= n; i++){   // Citim configuratia finala
        fin >> Final[i];           // si construim vectorul PozB
        pozB[Final[i]] = i;
    }
    int okey = 1;                  // Presupunem ca inca n-am ajuns la configuratia finala
    int mutari = 0;                // Initial, numarul de mutari este 0
    while(okey == 1) {             // Cat timp n-am ajuns la configuratia finala
        okey = 0;
        if(Final[pozA[0]] != 0) {  // Daca pozitiile frunzei libere nu corespund in cele doua configuratii
            okey = 1;
            ++mutari;
            Mutari[mutari].b = Final[pozA[0]],        //
            Mutari[mutari].s = pozA[Final[pozA[0]]],  //
            Mutari[mutari].d = pozA[0];               // --> Aducem pe pozitia frunzei libere din configuratia noastra
            swap(pozA[0], pozA[Final[pozA[0]]]);      //     broscuta care trebuia sa fie pe acea pozitie in configuratia
            swap(V[pozA[0]], V[pozA[Final[pozA[0]]]]);//     finala
        }
        else {                                        // Daca pozitiile frunzei libere din cele doua configuratii corespund
            for(int i = 1; i < n; ++i) {              // Verificam daca avem broscute care nu sunt pe pozitiile corespunzatoare
                if(pozA[i] != pozB[i]) {              // Daca broscuta i se afla pe o alta pozitie decat cea care ar trebui
                    okey = 1;
                    ++mutari;
                    Mutari[mutari].b = V[pozA[i]],    //
                    Mutari[mutari].s = pozA[i],       //
                    Mutari[mutari].d = pozA[0];       // ---> O mutam pe pozitia frunzei libere
                    swap(pozA[0], pozA[i]);           //
                    swap(V[pozA[0]], V[pozA[i]]);     //
                    break;
                }
            }
        }
    }
    if(c == 1) {                                      // Daca tipul de cerinta este 1
        fout << mutari << '\n';                       // Afisam numarul de mutari
    }
    else {                                            // Daca tipul de cerinta este 2
        if(mutari == 0) {
            fout << "broscutele nu se joaca\n";
        }
        else {
            for(int i = 1; i <= mutari; ++i) {        // Afisam mutarile
                fout << Mutari[i].b << ' ' << Mutari[i].s << ' ' << Mutari[i].d << '\n';
            }
        }
    }
    fin.close();
    fout.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1499)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1499/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1499/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)