• Problema triunghiului: se da un triunghi cu n linii de numere. Exista un „pion calator” care pleaca din casuta cea mai de sus a triunghiului si care se poate deplasa fie pe verticala in jos, fie pe diagonala la dreapta. Sa se gaseasca succesiunea de pasi realizati de pion, astfel incat suma numerelor din casutele vizitate de pion sa fie maxima.

  • N piese de domino sunt aliniate pe un covor. Sa se extraga dintre acestea cat mai putine, astfel incat cele care raman sa formeze un sir care respecta regula acestui joc.

Ex: 1-2 3-5 2-7 3-4 7-3
  • Se dau n cuburi de diverse culori si laturi. Sa se afiseze cel mai lung turn care se poate construi astfel incat 2 cuburi alaturate sa aiba culori diferite si un cub sa se aseze doar pe unul mai mare decat el.


  • Se da o multime de n numere naturale. Sa se imparta multimea in doua submultimi astfel incat sa se minimizeze |S1 –S2|, unde S1 si S2 sunt sumele elementelor celor 2 submultimi.
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
struct piesa { int st, dr;} x[100];
int n;
int z[100];
void citire ()
{
ifstream fin("date.in");
fin>>n;
for(int i=0;i<n;i++)
fin>>x[i].st>>x[i].dr;
fin.close ();
}
int main ()
{
int i,j,max,y[100],maxt=0,pmax=-1;
citire ();
y[n-1]=1;
for(i=n-2;i>=0;i--)
{
max=0;
for(j=i+1;j<n;j++)
{
if(x[i].dr==x[j].st && y[j]>max)
{
max=y[j];
}
}
y[i]=max+1;
if(maxt<max+1)
{
maxt=max+1;
pmax=i;
}
}
cout<<"Maxt="<<maxt <<" pmax= "<<pmax<<endl;
for(i=0;i<n;i++)
cout<<setw(3)<<x[i].st<<"-"<<x[i].dr;
cout<<endl;
for(j=0;j<n;j++)
cout<<setw(5)<<y[j];
cout<<endl;
cout<<"se extrag "<<n-maxt<<" piese"<<endl;
maxt--;
z[pmax]=1;
for(i=0;i<n&&maxt;i++)
if(y[i]==maxt&& x[pmax].dr==x[i].st)
{
z[i]=1;
maxt--;
pmax=i;
}
for(i=0;i<n;i++)
if(z[i]==0)
cout<<setw(3)<<x[i].st<<"-"<<x[i].dr;

}