Pentru un număr natural nenul n, să considerăm toate numerele naturale nenule mai mici sau egale cu n, luând fiecare număr de câte două ori: 1, 1, 2, 2, 3, 3, ... , n, n. Aceste numere le amestecăm aleator, şi le aranjăm pe două linii a câte n elemente. Structura astfel obţinută o vom numi o bipermutare. În figurile 1, 2 şi 3 avem câte un exemplu de bipermutare pentru n=5.
O bipermutare este perfectă, dacă ambele linii ale structurii reprezintă câte o permutare (vezi figurile 2 şi 3).
Prin mutare pe poziţia p, înţelegem interschimbarea elementelor de pe aceeaşi coloană p. În exemplele de mai jos, bipermutarea perfectă din figura 2 s-a obţinut din bipermutarea din figura 1, aplicând o mutare pe poziţa 2. Bipermutarea perfectă din figura 3 s-a obţinut din bipermutarea din figura 1, aplicând mutări pe poziţiile 1, 2, 4 şi 5.
Cerința
Cunoscând o bipermutare, determinaţi:
- numărul bipermutărilor perfecte distincte ce se pot obţine prin mutări;
- numărul minim de mutări prin care se poate obţine o bipermutare perfectă;
- o bipermutare perfectă obţinută din bipermutarea iniţială.
Date de intrare
Fișierul de intrare biperm.in conține pe prima linie valoarea lui n. Următoarele două linii conţin, fiecare, câte n elemente separate prin câte un spaţiu, formând o bipermutare.
Date de ieșire
Fișierul de ieșire biperm.out va conține:
- pe prima linie două numere naturale separate printr-un spaţiu, reprezentând numărul bipermutărilor perfecte distincte ce se pot obţine din bipermutarea dată, respectiv numărul minim de mutări prin care se poate obţine o bipermutare perfectă;
- pe următoarele două linii se vor tipări câte
nnumere separate prin spaţiu, reprezentând o bipermutare perfectă obţinută din bipermutarea dată.
Restricții și precizări
2 < n ≤ 10 000;- calculul corect al numărului bipermutărilor perfecte distincte valorează
30%din punctaj; - calculul corect al numărului minim de mutări valorează
10%din punctaj; - tipărirea unei bipermutări perfecte valorează
60%din punctaj. Pot exista mai multe soluţii, se va admite orice soluţie corectă; - se garantează că numărul bipermutărilor perfecte distincte nu depăşeşte
2 000 000 000pentru niciun test. - pentru
40%din testen ≤ 20 - pentru
40%din teste20 < n ≤ 400 - pentru
20%din teste400 < n ≤ 10 000
Exemplu
biperm.in
5 1 5 5 3 4 3 2 2 4 1
biperm.out
4 1 1 2 5 3 4 3 5 2 4 1
Explicație
Sunt 4 permutări perfecte. Numărul minim de mutări este 1 şi există două soluţii cu număr minim de mutări:
1 2 5 3 4 1 5 2 3 4 3 5 2 4 1 şi 3 2 5 4 1
Celelalte două soluţii, ce nu se obţin din număr minim de mutări sunt:
3 2 5 4 1 3 5 2 4 1 1 5 2 3 4 şi 1 2 5 3 4
Pentru a treia cerinţă oricare dintre cele 4 soluţii este acceptată.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Biperm:
// prof. Szabo Zoltan - Mures
// 100 puncte
#include <fstream>
#include <iostream>
using namespace std;
int viz[2][10003],a[2][10003],b[2][10003];
int main()
{ int n,i,j,p,nrmin,invers,l,poz,ant,aux,urmviz;
ifstream fin("biperm.in");
ofstream fout("biperm.out");
fin>>n;
for (i=0;i<2;++i) // matricea viz[x][i] are semnificatia:
for (j=1;j<=n;++j)
{
fin>>a[i][j]; // numarul i apare in bipermutare pe pozitiile
if (viz[0][a[i][j]]==0) // viz[0][i] si viz[1][i]
viz[0][a[i][j]]=j;
else
viz[1][a[i][j]]=j;
}
p=1; // p - numarul solutiilor distincte, produs, putere a lui 2
nrmin=0; // nrmin - va numara interschimbarile efectuate pentru cazul optim
for (i=1;i<=n;++i)
if (b[0][i]==0)
{ l=1; invers=0;poz=i; // reconstruim ciclurile: l lungimea ciclului
// invers= cate arce sunt in ciclu cu sensul invers
b[0][poz]=a[0][poz]; // poz = pozitia curenta in ciclu
b[1][poz]=a[1][poz]; // ant = pozitita anterioara in ciclu
ant=poz; // in b se construieste permutarea dubla ceruta
urmviz=b[1][poz]; // urmatorul nod spre vizitare in lant
if (viz[0][urmviz]==poz) //
poz=viz[1][urmviz];
else
poz=viz[0][urmviz]; // lant continua este muchia a[0][poz] si a[1][poz]
while (!b[0][poz])
{
if (a[0][poz]==b[1][ant])
{
b[0][poz]=a[0][poz];
b[1][poz]=a[1][poz];
l++;
ant=poz;
urmviz=b[1][poz];
if (viz[0][urmviz]==poz)
poz=viz[1][urmviz];
else
poz=viz[0][urmviz];
}
else
{
b[0][poz]=a[1][poz];
b[1][poz]=a[0][poz];
l++;invers++; // am gasit un nou arc invers
ant=poz; //
urmviz=b[1][poz];
if (viz[0][urmviz]==poz)
poz=viz[1][urmviz];
else
poz=viz[0][urmviz];
}
}
if (l>1)
p*=2;
if (invers>l-invers)
nrmin+=l-invers;
else
nrmin+=invers;
}
fout<<p<<" "<<nrmin<<"
";
for(i=0;i<2;++i)
{ for(j=1;j<n;++j)
fout<<b[i][j]<<" ";
fout<<b[i][n]<<"
";
}
fin.close();
fout.close();
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1041 Biperm
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1041 Biperm de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!