Question

https://www.pbinfo.ro/?pagina=probleme&id=401
Într-un depozit foarte mare există un raft cu n+1 spații de depozitare, numerotate de la 1 la n+1. Primele n spatii de depozitare sunt ocupate cu n pachete numerotate cu valori între 1 și n, iar spațiul de depozitare n+1 este golAdministratorul depozitului decide mutarea pachetelor, astfel încât pentru orice i, pachetul numerotat cu i să se afle în spațiul de depozitare i. Pentru aceasta se va folosi spațiul de depozitare suplimentar, n+1, singura manevră validă fiind mutarea unui pachet dintr-un spațiu de depozitare în altul, cu condiția ca acesta să fie gol.

Determinați o succesiune de manevre prin care fiecare pachet să fie în spațiul corect.

Answer 1

Răspuns:

#include <iostream>

#include <fstream>

using namespace std;

ifstream in("pachete.in");

ofstream out("pachete.out");

int v[1005];

struct rasp

{

   int poz1,poz2;

} m[1005];

int main()

{

   int n,pozg,c=0;

   in >> n;

   for (int i = 1; i<=n; i++)

       in >> v[i];

   pozg = n+1;

   v[pozg] = 0;

   for (int i = 1; i<=n; i++)

   {

       if (v[i]!=i)

       {

           if (i!=pozg)

           {

               c++;

               swap(v[i],v[pozg]);

               m[c].poz1 = i;

               m[c].poz2 = pozg;

               pozg = i;

           }

           for (int j = 1; j<=n+1; j++)

               if (v[j] == i)

               {

                   c++;

                   m[c].poz1 = j;

                   m[c].poz2 = pozg;

                   swap(v[pozg],v[j]);

                   pozg = j;

                   break;

               }

       }

   }

   out << c << "\n";

   for (int i = 1; i<=c; i++)

       out << m[i].poz1 << " " << m[i].poz2 << "\n";

}

Explicație: