Inaugurazione con tartarughe...

[MindFlyer]

Sì!

[Pyv]

Vi ricordo comunque che c'e' il forum delle Olimpiadi Italiane di Informatica appena nato su cui potete postare i vostri dubbi e vedere nuovi problemi:

http://81.208.32.83:8889/ioi-site/pn/ht ... file=index

Tra l'altro la' io sono il moderatore Sciocchezze a parte, visto che quel forum verra' utilizzato dai Probabili Olimpici informatici, e' possibile confrontarsi con quelli che saranno gli olimpionici del 2005.

Almeno fateci una visitina, in cambio di questo codice Non garantisco che sia giusto, ma dovrebbe... Se e' toppato non fatene uno scandalo, capita a tutti di sbagliare!

Codice: Seleziona tutto

#include	<iostream>
#include	<algorithm>

using namespace std;

#define	MAXTARTA	6000

int		T;
int		peso[MAXTARTA], forza[MAXTARTA];
int		pesomin[2][MAXTARTA+1];

int		L;

void leggi()
{
	int		p, f;

	while (cin >> p >> f)
	{
		peso[T] = p;
		forza[T] = f;
		T++;
	}
}

void risolvi()
{
	int		t, l, p;

	fill(*pesomin, *pesomin+2*(MAXTARTA+1), -1);
	pesomin[0][0] = 0;

	for (t=T-1; t>=0; t--)
	{
		for (l=0; l<=T-t; l++)
		{
			if (pesomin[0][l] == -1)	continue;
			p = pesomin[0][l] + peso[t];

			if (forza[t] >= p)
				if ((pesomin[1][l+1] == -1) || (p < pesomin[1][l+1]))		pesomin[1][l+1] = p;
		}

		copy( pesomin[1], pesomin[1]+MAXTARTA+1, pesomin[0]);
	}

	L = T;
	while (pesomin[0][L] == -1)	L--;
}

inline void scrivi()
{
	cout << L << endl;
}

int main()
{
	leggi();
	risolvi();
	scrivi();

	return 0;
}

[Marco]

Ciao e scusate l'intromissione, il forum matematica non e' posto che mi spetterebbe

Almeno fateci una visitina, in cambio di questo codice Non garantisco che sia giusto, ma dovrebbe... Se e' toppato non fatene uno scandalo, capita a tutti di sbagliare!

Ciao Pyv. Anche da parte mia, benvenuto. Non ti preoccupare, siamo abituati a vedere sbagli di ogni tipo e non ci scandalizziamo facilmente...

E non ti fare scrupolo a tornare: come vedi, non è affatto vero, che questo Forum non "ti spetterebbe". E perché mai?

Ciao. M.

[manub]

l'unico "consiglio" che mi sento di proporre è quello di scrivere algoritmi in pseudo-codice, restando lontani dalle differenze implementative dei vari linguaggi di programmazione. cosa ne dite?

[MindFlyer]

Dipende dal contesto.
Forse in questo caso era meglio lo pseudo-codice.

[bh3u4m]

Nel codice manca l'inizializzazione di T se non sbaglio... meglio metterla che alcuni compilatori non inizializzano da soli le variabili.

[bh3u4m]

Bene, ho verificato il programma... è l'algoritmo che avevo in mente all'inizio.
E' difficile capire se sia giusto, però sembra esserlo, ho provato a fare una verifica manuale con 4 tartarughe e non sembrava avere problemi.

Credo che si possa evitare di usare due vettori per il pesomin servendosi di una variabile che memorizza l'elemento del vettore che dev'essere sostituito per un successivo uso, così si evita di dover chiamare la funzione copy che rallenta l'esecuzione del programma.

[MindFlyer]

Ok, ho letto il programma, e mi sembra toppato in almeno 2 punti (la T non inizializzata non è un problema, perché si considera inizializzata a 0).
Nessuno scandalo, ma pregherei Pyv di correggerlo quando passa di qua, perché non sono riuscito a capire cosa dovrebbe fare l'algoritmo.

[MindFlyer]

bheuam, se hai capito l'algoritmo, mi fai la cortesia di provarlo su questa configurazione?

Pesi: 0, 0, 1, 2
Capacità: 1, 1, 2, 0

(ho elencato pesi e capacità dalla tartaruga più "in basso" a quella più "in alto")

[MindFlyer]

Ah, finalmente ho capito cosa deve fare l'algoritmo!
Però la versione di Pyv va cambiata in vari punti...
In pratica, scorre le tartarughe dalla più in alto alla più in basso, tenendosi il peso minimo delle pile di ogni lunghezza, e questo funziona!!
Ottimo lavoro.

[manub]

Ah, finalmente ho capito cosa deve fare l'algoritmo!
Però la versione di Pyv va cambiata in vari punti...
In pratica, scorre le tartarughe dalla più in alto alla più in basso, tenendosi il peso minimo delle pile di ogni lunghezza, e questo funziona!!
Ottimo lavoro.

un po' come lo zaino

scusate la domanda... ma questo è un problema NP-completo? sono un po' ignorante in materia, ma dato che anche in altri post lo si paragona allo zaino (0/1, ovviamente, se fosse frazionario non sarebbe NP-completo)...

[bh3u4m]

E' comunque un algoritmo $ O (N^2) $, se non mi sbaglio (ma due cicli for uno dentro l'altro lo dovrebbero essere).

[manub]

E' comunque un algoritmo $ O (N^2) $, se non mi sbaglio (ma due cicli for uno dentro l'altro lo dovrebbero essere).

riguardando l'algoritmo sembra anche a me così. quindi lo zaino non c'entra nulla...

[Pyv]

Anzitutto: la mancata inizializzazione di T non e' un errore, perche' tutte le variabili globali vengono inizializzate a 0. O almeno questo e' quello che dice il C/C++ standard, se poi usate un compilatore scadente che non lo rispetta io non posso farci niente

Lo so comunque che il copy rallenta il programma, sarebbe stato meglio (ma meno chiaro) usare i due vettori circolarmente (cioe' usando qualcosa del tipo pesomin[t%2] e pesomin[1-(t%2)]). L'ho fatto per farvi capire meglio le cose.

Gradirei che mi diceste i punti esatti in cui pensate il programma sia sbagliato... se mi dite solo "e' sbagliato in 2 punti" non so cosa intendete.

[bh3u4m]

La teoria dice però che si tratta di un algoritmo $ O (N \log N ) $ nella normalità, con caso peggiore $ O ( N^2 ) $, infatti non è necessario tenersi un vettore lungo quanto le tartarughe, è sufficiente incrementare il vettore quando si offre la possibilità di una pila con una tartaruga in più del solito, il secondo ciclo for (quello annidato) perciò sarà chiamato un numero molto minore di volte rispetto al primo.