infooo domino

Enunt:

Se dau n piese de domino.Fiecare piesa poate fi rotita cu 180°.

Se cere:

Determinati subsirul de piese de lungime maxima astfel incat  oricare 2 piese alaturate sa aiba un numar in comun.

 

Exemplu:

vp.first: 5 1 2 3 1 6 5 5 2 1 5 5 3

vp.second:6 1 5 2 5 4 1 3 1 4 5 2 3

v.0:6 5 5 3 4 2 3 2 2 1 2 1 1

v.1:6 5 5 4 4 1 3 3  2 1 2 1 1

v.next.0:6 5 5 9 7 10 9 13 10 0 12 0 0

v.next.1:3 5 4 8 7 0 8 11 12 0 12 0 0

 

Rezolvare:

#include<iostream.h>
#include<fstream.h>
typedef struct {int first,sec;}PIESA;
PIESA v[100];
int d[2][100],poz[2][100],n;
void citire()
{
n=0;
ifstream f(“domino.in”);
while(!f.eof())
{
f>>v[++n].first>>v[n].sec;
}
f.close();
}
void dinamica()
{
int i,j,max0,max1,p0,p1;
d[0][n]=d[1][n]=1;
poz[0][n]=poz[1][n]=0;
for(i=n-1;i>=1;i–)
{
max0=max1=0;
p0=p1=0;
for(j=i+1;j<=n;j++)
{
if(v[i].sec==v[j].first&&d[0][j]>max0)
{
max0=d[0][j];p0=j;}
if(v[i].sec==v[j].sec&&d[1][j]>max0)
{
max0=d[1][j];p0=j;}
if(v[i].first==v[j].sec&&d[1][j]>max1)
{
max1=d[1][j];p1=j;}
if(v[i].first==v[j].first&&d[0][j]>max1)
{
max1=d[0][j];p1=j;}
}
d[0][i]=max0+1;
d[1][i]=max1+1;
poz[0][i]=p0;
poz[1][i]=p1;
}
}
void afisare()
{
int k,p,aux,i,max;
for(i=1;i<=n;i++)
{
if(d[0][i]>max){max=d[0][i];k=0;p=1;}
if(d[1][i]>max){max=d[1][i];k=1;p=i;}
}
if(k==0)
{
cout<<v[p].first<<” “<<v[p].sec;
aux=v[p].sec;}
else {cout<<v[p].sec<<” “<<v[p].first;
aux=v[p].first;}
p=poz[k][p];
while(p>0)
{
if(aux==v[p].first){cout<<v[p].first<<” “<<v[p].sec;k=0;aux=v[p].sec;}
else{cout<<v[p].sec<<” “<<v[p].first;k=1;aux=v[p].first;
}
p=poz[k][p];
}
}
int main()
{
int max=0,i,k,p;
citire();
dinamica();
for(i=1;i<=n;i++)
{
if(d[0][i]>max){max=d[0][i];k=0;p=i;}
if(d[1][i]>max){max=d[1][i];k=1;p=i;}
}
cout<<max;
return 0;
}

Advertisements
Posted in Uncategorized | Leave a comment

Cakes & Cookies :)

1. Red Velvet Cake

A Red Velvet Cake is very dramatic looking with its bright red color that is offset by a creamy white frosting. There are many theories as to its origin. Some say it comes from the South, others say it originated in the North. All we really know is that it has been a favorite for decades, not only in the States but also in Canada (it used to be sold in Eaton’s Department Stores). It is really a Devil’s Food Cake that has red food coloring added to it. John Mariani tells us in his book “The Dictionary of American Food and Drink” that the name ‘Devil’s Food Cake’ is so called “because it is supposedly so rich and delicious that it must, to a moralist, be somewhat sinful.”

2. Checkerboard Cake

The striking black and white squares of this melt-in-your-mouth butter cake will make it a favorite when you are looking to bake something a little different.

3. Meringue Mushrooms

What is amazing is how these Meringue Mushrooms actually look like real mushrooms. They start with just two ingredients, egg whites and sugar, that are beaten until stiff and glossy. The meringue is then placed in a pastry bag and piped into shapes that look like mushroom ‘caps’ and ‘stems’. After baking in a slow oven the stems are attached to the caps in one of two ways; a little meringue is used as a ‘glue’ to attach the stems to the caps or you can use a little melted chocolate to ‘glue’ them together (used here). Either way is delicious. The finishing touch to make them look like real mushrooms, is to dust the tops of the meringue mushrooms with a light sprinkling of cocoa powder. The beauty of these meringue mushrooms is that they will keep, in dry humidity, several weeks. Serve the mushrooms standing upright on a platter or they also look wonderful placed in a basket. Meringue mushrooms are especially popular at Christmas time when they are used to garnish the Buche de Noel (Yule Log).

Sursa: joyofbaking.com

Posted in sweets | Leave a comment

Holograf – Viata are gust

Posted in Muzica | Leave a comment

Catalin Josan – Vrei nu vrei, esti doar a mea

Posted in Muzica | Leave a comment

Bruno Mars – Just The Way You Are

Posted in Muzica | Leave a comment

Claudia

Buna !

Posted in Uncategorized | Leave a comment

Hello world!

Welcome to my blog! 😀

Posted in Uncategorized | Leave a comment