Problema "scrigni" OIS 2016 - Seconda gara

Aiuto
1

Ciao a tutti!
Qualcuno potrebbe illuminarmi per come prendere l’ultimo Subtask del problema “scrigni”? Il mio programma fa 90/100 e non riesco a pensare ad un modo per prendere gli ultimi 10 punti.

Durante la seconda gara avevo preso 90 punti facendo return (N *(N - 1) / 4.0);, solo che se provo a sottomettere un programma che fa questo non mi dà giusto nessun testcase.

2

Ciao
dopo molti tentativi falliti sono riuscito a capire perché non ti da giusto nessun testcase
ho scoperto che a seconda se è un numero,5 o un numero intero devi stampare un valore diverso

io ho risolto aggiungendo un if con condizione per determinare ciò
quindi a seconda che N%4==0 oppure no farai un fprintf %.0f oppure %.1f

in atre parole è “sensibile agli zeri di troppo” :stuck_out_tongue:

3

Ciao! Sei riuscito anche a prendere l’ultimo subtask?

4

Se posso intromettermi io ho risolto ipottizzando che lo spazio riservato alle double non fosse sufficiente per contenere i risultati dei testcase.
Ho quindi lavorato semplicemente con delle long int e aggiungendo “a mano” il ‘.5’ quando necessario…

 scosse=(n*(n-1))/4;
    
    if ((n*(n-1))%4==0)
        out << scosse;
    else
        out << scosse << ".5";

Non so quanto possa risultare formalmente corretto, ma solo cosi sono riuscito a raggiungere i 100 punti.

1 Mi Piace
5

Avevo già provato utilizzando long solo che mi veniva sbagliato. Ora ho riprovato e me l’ha dato giusto xD Grazie a tutti e due per l’aiuto :smile:

6

Mi sono appena reso conto che per questo task non era attivo il correttore semantico, per cui venivano considerate corrette solo le sottoposizioni che producevano lo stesso identico output della soluzione ufficiale.

Ho rivalutato tutte le sottoposizioni, stavolta considerando l’output corretto in base all’errore relativo (come descritto nel testo).

P.S. nella gara vera il correttore era attivo :stuck_out_tongue:

2 Mi Piace
7

Fantastico
adesso nelle mie 12 sottoposizioni c’è una serie di 90/100 fin dal secondo tentativo :joy:

8

Ciao a tutti!
Qualcuno potrebbe spiegarmi il perchè la soluzione è questa? Non riesco a capire…[quote=“xYinXiao, post:1, topic:404”]
return (N *(N - 1) / 4.0);
[/quote]`

9

Il modo con cui Giorgio era arrivato a quella formula è il seguente. Considera l’apertura degli n scrigni “separatamente”. Per come è strutturato il problema, all’inizio non puoi far altro che cercare qual è il primo scrigno e, una volta che l’hai trovato, sei punto e a capo (nel senso che durante la “ricerca” fatta non avrai guadagnato alcuna informazione su dove può essere il secondo scrigno). Quindi:

  • Per trovare il primo scrigno prenderai in media \frac{n-1}{2} scosse (se ti va bene ne prendi 0 perché trovi subito lo scrigno corretto, se ti va male ne prendi n-1 e capisci per esclusione che l’unico che non hai ancora provato deve essere quello corretto, quindi il risultato sarà la media tra 0 e n-1).
  • Per trovare il secondo scrigno prenderai in media \frac{n-2}{2} scosse (puoi far finta di buttare via il primo scrigno e “ricominciare da capo”).
  • E così via…

A questo punto rimane solo da fare un po’ di semplificazioni (raccogliendo il fattore \frac12 e usando la formula della sommatoria di Gauss) per trovare che \frac{n(n-1)}{4} = \frac{n-1}{2} + \frac{n-2}{2} + \dots

3 Mi Piace
10

Ho capito. Ti ringrazio :grinning:

11

Mi va in timeout nell’ultimo testcase. Non ho capito come avete fatto ad ottenere 100/100.
Il mio codice:

double scosse(int N) {
    double totale = 0.0;
    for (int i=1; i<=N; i++)
        totale += (N-i)/2.0;
    return totale;
}
12

Ciao, guarda io l’ho scritto così e mi dà il punteggio pieno.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	long long N;
	cin >> N;
	
	cout << N*(N-1)/4.0;
	return 0;
}

spero di essere stato utile
Thomas Leihkauf