Buongiorno,
sono nuovo al linguaggio C++ e a questo tipo di problemi, quindi sono ancora alle basi.
Ho provato a risolvere “Super Mario” e il mio punteggio non va oltre a 90/100 e non capisco perché.
Questo è il mio codice, grazie in anticipo per il chiarimento:
#include <stdio.h>
#include <assert.h>
double scosse(int N) {
double volte = 0;
for (double i = N;i > 0;i--) {
volte = volte + (i-1)/2.0;
}
return volte;
}
int main() {
FILE *fr, *fw;
int N;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(1 == fscanf(fr, "%d", &N));
fprintf(fw, "%.6f\n", scosse(N));
fclose(fr);
fclose(fw);
return 0;
}
Il tuo codice va fuori tempo. Serve una soluzione più efficiente. Prova a pensare se c’è un modo per calcolare il risultato senza cicli… La media è (caso migliore + caso peggiore) / 2. Il caso milgiore è banale: Non prende nessuna scossa. Il caso peggiore è che prenda tutte le scosse possibili che sono al primo turno N-1, al secondo N-2 etc. C’è un modo per calcolare questo senza un ciclo for? Sommatoria di Gauss. Se hai domande chiedi pure.
Per prima cosa grazie perché effettivamente il codice poteva essere molto più semplice e il tuo consiglio mi ha aiutato molto. Ho provato a cambiarlo e mi sembrava di aver trovato una soluzione corretta, invece continua a darmi 90/100 e non capisco perché .
#include <stdio.h>
#include <assert.h>
double scosse(int N) {
return (N*(N-1))/4.0;
}
int main() {
FILE *fr, *fw;
int N;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(1 == fscanf(fr, "%d", &N));
fprintf(fw, "%.6f\n", scosse(N));
fclose(fr);
fclose(fw);
return 0;
}
Grazie in anticipo per l'aiuto
Volendo puoi non dichiarare la funzione, ma puoi semplicemente dichiarare N come float e scrivere la risposta come N=N(N-1)/4
Il template è sbagliato. N dovrebbe essere un long long int
Ciao, mi sto allenando perché recentemente ci sono state le prove territoriale delle olimpiadi di informatiche e se passo per le nazionali voglio essere preparato, dunque sto svolgendo molti degli allenamenti che ci sono per le territoriale, ho visto il tuo codice però non riesco a comprendere quella formula, la sommatoria di gaus è N*(N+1)/2 ciò che più non capisco è quel /4. Ti ringrazio in anticipo per la risposta
Ciao, la formula presentata nel codice (ovvero N \times (N - 1) / 4) è la formula per calcolare la media di volte in cui il personaggio prende la scossa. La formula per calcolare ciò è data dalla metà della somma tra caso migliore e caso peggiore.
È possibile individuare come caso migliore la situazione in cui gli scrigni vengano aperti nell’ordine giusto, commettendo dunque 0 errori. Il caso peggiore, invece, è la situazione in cui, ad ogni tentativo, gli scrigni vengono aperti nella maniera meno efficiente possibile (ovvero, il personaggio apre tutti gli scrigni ogni tentativo, facendo così N - 1 errori la prima volta, N - 2 la seconda, N - 3 la terza e così via). Per calcolare il numero di casi di questo ultimo scenario, è necessario ricorrere alla sommatoria di Gauss, la cui formula – come dicevi nel messaggio – è \frac{x \times (x + 1)}{2}. Applicando questa formula allo scenario peggiore, ovvero la somma di tutti i numeri da 0 a N - 1, otterrai come risultato \frac{(N - 1) \times [(N - 1) + 1]}{2} = \frac{(N - 1) \times N}{2}.
Considerato che il numero medio di volte in cui il personaggio sbaglia ad aprire lo scrigno è pari alla media tra i due casi sopra citati, è possibile dire che tale media è pari a \frac{0 + [(N - 1) \times N]}{2 \times 2} = \frac{(N - 1) \times N}{4}.
Spero di essere riuscito a chiarire il tuo dubbio, nel caso avessi problemi con l’implementazione, ti suggerirei di creare un nuovo post allegando anche il tuo codice, in modo da capire direttamente dove possano esserci criticità.
2 Mi Piace