Domino massimale subtask 6,9,15,17


#1

Non capisco perché il punteggio è solo 78/100. I subtask sbagliati sono 06,09,15,17

#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
const int MAX=10;
int sx[MAX],dx[MAX],v[MAX],appsx[MAX],appdx[MAX];
int path(int ind,int sx[],int dx[],int n);
bool conc(int& sx1,int& dx1,int& sx2,int& dx2);
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>sx[i]>>dx[i];
		v[i]=false;
		appsx[i]=sx[i];
		appdx[i]=dx[i];
	}
	
	int max=-INT_MAX;
	for(int i=0;i<n;i++)
	{
		if(path(i,sx,dx,n)>max)
			max=path(i,sx,dx,n);
		for(int i=0;i<n;i++)
		{
			v[i]=false;
			sx[i]=appsx[i];
			dx[i]=appdx[i];
		}
	}
	if(max==0) cout<<max;
	else
	cout<<max+1;
}
int path(int ind,int sx[],int dx[],int n)
{
	int somm=0,max=-INT_MAX,temp=ind;
	for(int cont=0;cont<n;cont++)
	{
		somm=0;
		ind=temp;
		for(int i=cont;i<n;i++)
		{
			if(conc(sx[ind],dx[ind],sx[i],dx[i])==true and v[i]==false and i!=ind) //cambia forma vettore
			{
				somm++;
				v[ind]=true;
				ind=i;
				i=-1;
			}
		}
		if(somm>max)
			max=somm;
		for(int i=0;i<n;i++)
		{
			v[i]=false;
			sx[i]=appsx[i];
			dx[i]=appdx[i];
		}
	}
	return max;
}
bool conc(int& sx1,int& dx1,int& sx2,int& dx2)
{
	int temp;
	if(dx1==sx2)
	{
		//
		return true;
	}
	else if(dx1==dx2)
	{
		temp=sx2;
		sx2=dx2;
		dx2=temp;
		return true;
	}
	else if(sx1==sx2)
	{
		temp=sx1;
		sx1=dx1;
		dx1=temp;
		return true;
	}
	else if(sx1==dx2)
	{
		temp=sx1;
		sx1=dx1;
		dx1=temp;
		
		temp=sx2;
		sx2=dx2;
		dx2=temp;
		return true;
	}
	return false;
}

Input:

6 3 0 4 0 2 6 4 4 0 1 1 0

Output:

5

#2

Prova con questo semplice input:

3
3 0
0 2
0 1

Il tuo programma da 3 in output! Credo che sia dovuto al fatto che la conc()…
A parte questo perché fare:

cioè chiamare due volte la funzione.
suggerirei
int max1=path( );
if(max1>max)
max=max1;


#3

Ti ringrazio per avermi fatto notare che il programma chiama due volte la funzione path();:smile:
Per quanto riguarda il tuo input, il mio programma da 2 in output, quindi funziona correttamente :face_with_raised_eyebrow:


#4

Meglio così però sul mio computer il tuo programma mi da 3 in output
e con l’input sotto mi da 5 ma dovrebbe dare 6

6
3 0
4 0
3 6
4 4
0 1
1 0

Forse la versione che hai postato non è l’ultima?


#5

Non ho ben chiaro come funziona il tuo programma ma qui è dove ho il dubbio più grosso:

if(conc(sx[ind],dx[ind],sx[i],dx[i])==true && v[i]==false && i!=ind) //cambia forma vettore

se ho ben capito tu confronti il valori dx e sx di ind (l’ultima tessera inserita nella sequenza o la prima all’inizio) con quelli una delle altre non ancora utilizzate, però dopo il primo inserimento o il sx o il dx di ind è interno alla sequenza di tessere e non da controllare da lì in poi.
Cerco di spiegare meglio il mio dubbio con un esempio:
supponiamo di avere queste 3 tessere : 3 0, 4 0, 4 2
dopo l’unione della prima con la seconda (3 0-0 4) avremo sostanzialmente una maxi-tessera da due con a sx 3 e a dx 4 e la conc ora dovrebbe, almeno credo, controllare 3,4 con 4,2 ma a quello che ho visto in debug, alla conc vengono invece passati 0,4 e 4,2 nella prima coppia sx/dx ci sono i valori sx e dx di una tessera semplice (l’ultima aggiunta?) e non i veri estremi della sequenza di tessere finora creata.


#6

Prima di tutto posto l’ultima versione del programma:

#include
#include
#include <limits.h>
using namespace std;
const int MAX=10;
int sx[MAX],dx[MAX],v[MAX],appsx[MAX],appdx[MAX];
int path(int ind,int sx[],int dx[],int n);
bool conc(int& sx1,int& dx1,int& sx2,int& dx2);
int main()
{
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>sx[i]>>dx[i];
v[i]=false;
appsx[i]=sx[i];
appdx[i]=dx[i];
}

int max=-INT_MAX;
for(int i=0;i<n;i++)
{
	int max1=path(i,sx,dx,n);
	if(max1>max)
	max=max1;
	for(int i=0;i<n;i++)
	{
		v[i]=false;
		sx[i]=appsx[i];
		dx[i]=appdx[i];
	}
}
cout<<max+1;

}
int path(int ind,int sx[],int dx[],int n)
{
int somm=0,max=-INT_MAX,temp=ind;
for(int cont=0;cont<n;cont++)
{
somm=0;
ind=temp;
for(int i=cont;i<n;i++)
{
if(conc(sx[ind],dx[ind],sx[i],dx[i])==true and v[i]==false and i!=ind) //cambia forma vettore
{
somm++;
v[ind]=true;
ind=i;
i=-1;
}
}
if(somm>max)
max=somm;
for(int i=0;i<n;i++)
{
v[i]=false;
sx[i]=appsx[i];
dx[i]=appdx[i];
}
}
return max;
}
bool conc(int& sx1,int& dx1,int& sx2,int& dx2)
{
int temp;
if(dx1==sx2)
{
//
return true;
}
else if(dx1==dx2)
{
temp=sx2;
sx2=dx2;
dx2=temp;
return true;
}
else if(sx1==sx2)
{
temp=sx1;
sx1=dx1;
dx1=temp;
return true;
}
else if(sx1==dx2)
{
temp=sx1;
sx1=dx1;
dx1=temp;

	temp=sx2;
	sx2=dx2;
	dx2=temp;
	return true;
}
return false;

}

L’input di cui mi parli- cioè l’esempio proposto- dovrebbe dare output 5 e non 6, quindi funziona correttamente.:+1:

Non credo che la “maxi tessera” sia proprio quello che si viene a formare. Io avvicino le tessere fra di loro poi però se confronto gli estremi devo sempre tener conto del fatto che ho unito le tessere, non posso mica fonderle cancellando i medi.
Fammi sapere se ho capito male io: potrebbe essere questo l’errore :face_with_raised_eyebrow:


#7

Anche facendolo a mano mi sembra che si possano allineare tutte e 6:
6-3,3-0,0-1,1-0,0-4,4-4


#8

Metti da parte la programmazione e pensa di giocare a domino:
esempio:hai queste 3 tessere 0-5, 3-0, 3-4
supponiamo di cominciare mettendo a tavola la 0-5, ora poi puoi solo mettere alla sua sinistra la 3-0 (senza ruotarla).
Ora puoi aggiungere solo una tessera che ha o un 3 o un 5 perchè la sequenza creata ora è 3-00-5.
Effettivamente ora è come se avessimo a tavola una unica tessera 3-5 (con i medi fusi o eliminati) alla fine avremo una unica maxi tessera 4…5


#9

Allora sarà proprio questo l’errore. Provo a correggere e posto il codice :+1: