Domino massimale subtask 6,9,15,17

Antonio_Prisco · 2 Febbraio 2019, 6:07pm

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:

v.bizzarri · 5 Febbraio 2019, 9:54am

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;

Antonio_Prisco · 5 Febbraio 2019, 7:23pm

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

v.bizzarri · 5 Febbraio 2019, 8:46pm

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?

v.bizzarri · 5 Febbraio 2019, 9:54pm

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.

Antonio_Prisco · 6 Febbraio 2019, 9:27pm

Prima di tutto posto l’ultima versione del programma:

#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++)
	{
		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.

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

v.bizzarri · 6 Febbraio 2019, 10:39pm

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

v.bizzarri · 6 Febbraio 2019, 11:02pm

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

Antonio_Prisco · 7 Febbraio 2019, 7:42pm

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

Antonio_Prisco · 30 Marzo 2019, 5:11pm

Qualche suggerimento per modificare la funzione e adattarla al problema?

v.bizzarri · 9 Aprile 2019, 4:31pm

Mi rifaccio vivo dopo un certo periodo di assenza.
Suggerisco di usare un procedura ricorsiva che segue l’idea della maxitessera a tavola fatta dalla concatenazione di tutte le tessere messe a tavola questa funzione ha tre parametri:

il numero sul lato sinistro della tessera
il numero sul lato destro della tessera
di quante tessere è composta
Dato il numero esiguo di tessere non ho usato la memoizzazione.
Se aggiungo una tessera a sin prima di procedere aggiorno il numero a sin (il primo parametro etc…)
e così per l’altro lato.
Ci sono quattro casi da gestire ogni volta.
Il tutto ripetuto per tutte le tessere (ogni volta iniziando con una tessera diversa).
Posso suggerirti qualcosa anche sulle missioni di Topolino, che è più semplice.

Antonio_Prisco · 9 Aprile 2019, 4:45pm

Accidenti avevo dimenticato il problema del domino . Stasera o domani ci lavoro su.

Nel frattempo mi farebbe piacere se potessi aiutarmi anche con missioni, non riesco ad ottenere quei 30 punti che mi servono per totalizzare 100/100

v.bizzarri · 9 Aprile 2019, 4:47pm

fra un po’ ti rispondo su quel topic comunque si può risolvere iterativamente.