Inaugurazione con tartarughe...
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!
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;
}
Pyv ha scritto:Ciao e scusate l'intromissione, il forum matematica non e' posto che mi spetterebbe
Ciao Pyv. Anche da parte mia, benvenuto. Non ti preoccupare, siamo abituati a vedere sbagli di ogni tipo e non ci scandalizziamo facilmente...Pyv ha scritto: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!
E non ti fare scrupolo a tornare: come vedi, non è affatto vero, che questo Forum non "ti spetterebbe". E perché mai?
Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
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.
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.
Ultima modifica di bh3u4m il 13 mar 2005, 19:37, modificato 1 volta in totale.
un po' come lo zainoMindFlyer ha scritto: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.
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)...
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.
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.
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.