Rezumat problemă

Biperm

#1041

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.

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ă.

OJI 2013, clasele XI-XII

Fișiere Candale Silviu (silviu) Zoltan Szabo concurs

Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate

Rezolvă

Detalii

Problema	Biperm	Operații I/O	biperm.in/biperm.out
Limita timp	1 secunde	Limita memorie	Total: 128 MB / Stivă 64 MB
Id soluție	#56130445	Utilizator	Herman Ioan (HermanIoan)
Fișier	biperm.cpp	Dimensiune	1.47 KB
Data încărcării	06 Februarie 2025, 22:15	Scor/rezultat	100 puncte

Evaluare

Mesaj compilare

biperm.cpp: In function 'int main()':
biperm.cpp:7:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("biperm.in","r",stdin);

                                   ^
biperm.cpp:8:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("biperm.out","w",stdout);

                                     ^
biperm.cpp:9:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);

                   ^
biperm.cpp:10:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++){scanf("%d",&j);a[i][0]=a[i][2]=j;if(f[j])s[j]=i;else f[j]=i;}

                                     ^
biperm.cpp:11:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++){scanf("%d",&j);a[i][1]=a[i][3]=j;if(f[j])s[j]=i;else f[j]=i;}

                                     ^

Rezultat evaluare

Cum funcționează evaluarea?