În fața palatului Prințesei Mofturoase se află n pețitori așezați la coadă, unul în spatele celuilalt. Fiecare poartă sub mantie un număr de pietre prețioase pe care dorește să le ofere prințesei ca dar de nuntă. Pentru a nu semăna vrajbă în rândurile lor, prințesa a decis să-i determine ca n-1 dintre ei să renunțe în chip pașnic, pețitorul rămas devenind alesul prințesei (indiferent de numărul de pietre prețioase deținute de acesta). Doi pețitori vecini la coadă se pot înțelege între ei astfel: cel care are mai puține pietre prețioase pleacă de la coadă primind de la celălalt un număr de pietre astfel încât să plece acasă cu un număr dublu de pietre față de câte avea. Dacă doi pețitori au același număr de pietre, unul din ei (nu contează care) pleacă luând toate pietrele vecinului său. Un pețitor se poate înțelege la un moment dat cu unul singur dintre cei doi vecini ai săi. După plecarea unui pețitor, toți cei din spatele lui avansează.
De exemplu: pentru configurația de mai jos de 5 pețitori, un șir posibil de negocieri care conduc la reducerea cozii la un singur pețitor este: se înțeleg vecinii 4 cu 5 și pleacă 4, se înțeleg apoi 1 cu 2 și pleacă 1, se înțeleg apoi 3 cu 2 și pleacă 3, se înțeleg 2 cu 5 și pleacă 5. Astfel pețitorul 2 câștiga mâna preafrumoasei prințese, oferindu-i 0 pietre prețioase ca dar de nuntă.
Fie P numărul de pietre prețioase pe care le are pețitorul care va deveni alesul prințesei.
Cerința
Se cer valorile distincte ale lui P la care se poate ajunge prin toate succesiunile de negocieri posibile.
Date de intrare
Fișierul de intrare nunta1.in conține pe prima linie numărul de pețitori n, iar pe a doua linie n numere naturale din intervalul [0,20], reprezentând numărul de pietre prețioase pe care le dețin pețitorii, în ordinea în care stau la coadă.
Date de ieșire
Fișierul de ieșire nunta1.out va conține pe prima linie numărul m de valori distincte ce pot fi obținute, iar pe a doua linie cele m valori ordonate crescător, reprezentând valorile care se pot obține.
Restricții și precizări
1 ≤ n ≤ 50- numerele de pe a doua linie a fișierului de intrare vor fi cuprinse între
0și20
Exemplu
nunta1.in
4 1 4 2 6
nunta1.out
3 1 3 5
Explicație
De exemplu, suma 1 se poate obține astfel: al doilea nuntaș dă o piatră primului și rămân ultimii trei nuntași cu valorile 3 2 6. Apoi ultimul nuntaș dă penultimului 2 pietre și rămân doi nuntași cu valorile 3 4. Acum nuntașul cu 4 pietre dă trei pietre celuilalt și rămâne singur cu o piatră.
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 nunta1:
/**
Programare dinamica metoda mixta:
dp[i,j]=valorile distincte posibile care se obtin daca din sirul de
petitori i, i+1, ..., j ramane unul singur
dp[i,j]= este un vector de aparitii de lungime 20, dp[i,j,k]=1
daca se poate obtine suma k (k=0..20)
Solutia se afla in dp[1][n], afisandu-se indicii bitilor setati cu 1
Complexitate O(n x n x n), cu o constanta 21 x 21.
*/
#include <bits/stdc++.h>
#define nmax 52
#define inFile "nunta1.in"
#define outFile "nunta1.out"
using namespace std;
int a[nmax], n;
bitset<22> dp[nmax][nmax];
inline int Modul(int x)
{
if (x < 0) return -x;
return x;
}
void Citire()
{
ifstream fin(inFile);
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i];
fin.close();
}
void Seteaza(int p, int k, int q)
{
int i, j;
for (i = 0; i <= 20; i++)
for (j = 0; j <= 20; j++)
if (dp[p][k][i] == 1 && dp[k+1][q][j] == 1)
dp[p][q][Modul(i-j)] = 1;
}
void Rezolva()
{
int i, j, pas, k;
/// initializare diagonala principala
for (i = 1; i <= n; i++)
dp[i][i][a[i]] = 1;
/// initializare urmatoarea diagonala
for (i = 1; i < n; i++)
dp[i][i + 1][Modul(a[i]-a[i + 1])] = 1;
/// procesarea restului matricei
for (pas = 2; pas < n; pas++)
for (i = 1; i <= n - pas; i++)
{
j = i + pas;
for (k = i; k < j; k++)
Seteaza(i, k, j);
}
}
void Afisare()
{
int i;
ofstream fout(outFile);
fout << dp[1][n].count() << "\n";
for (i = 0; i <= 20; i++)
if (dp[1][n][i] == 1) fout << i << " ";
fout << "\n";
fout.close();
}
int main()
{
Citire();
Rezolva();
Afisare();
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 #2137 nunta1
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2137 nunta1 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!