Durante la gara ho speso almeno mezz’ora inutile per cercare di capire i casi di esempio del testo coats e in particolare non ho capito da dove esce il 0.6 del terzo caso. Qualcuno potrebbe spiegarmelo??
Nel terzo caso di esempio la giacca si potrebbe trovare in cinque posizioni diverse, di cui due all’indice 0, due all’indice 2 e una all’indice 3. Per prima cosa possiamo escludere tutti gli indici ai quali è associato il valore zero, perchè la iacca non potrà trovarsi certamente lì. Poi puoi notare anche che se la giacca si trova in cima ad una pila, ovvero si trova in una pila di altezza uno oppure si trova in una pila di altezza due ed è in cima alla pila, non sarà necessario alzare nessuna giacca d’altri. L’unico caso in cui sarà necessario alzare altre giacche è quando la giacca che stiamo cercando è in fondo ad una pila da due.
Da qui non dovrebbe essere troppo difficile trovare come calcolare il numero medio di ghiacche da spostare.
Riporto il caso d’esempio per comodità:
4
2 0 2 1
Dario
3 Mi Piace
Scusa, ma io veramente non riesco ancora a capire 
Caso medio = somma di tutti i casi possibili / numero di casi possibili
Quindi, tutti i casi possibili sono:
0 -> se è la prima in posizione 0 ne tocco 0
0 -> se è la prima in posizione 2 ne tocco 0
0 -> se è la prima in posizione 3 ne tocco 0
1 -> se è la seconda in posizione 0 ne tocco solo 1
1 -> se è la seconda in posizione 2 ne tocco solo 1
2 -> se è la seconda in posizione 0 ma sono un attimo sfortunato ne tocco 2
2 -> se è la seconda in posizione 2 ma sono un attimo sfortunato ne tocco 2
Quindi 6/7
Dove sbaglio? 
Considera che ci sono due casi in cui dovrai alzare le giacche:
2 0 2 1
Se fosse nel primo appendino devi alzare una giacca, se fosse nel terzo dovresti alzare sia quella nel primo appendino sia quella nel terzo, quindi tre giacche alzate su cinque giacche totali.
I casi in cui la giacca è in seconda posizione non vanno suddivisi in “sono fortunato” / “sono un po’ meno fortunato”, ma devi considerare come casi possibili solo le possibili posizioni della giacca. Se la giacca è in seconda posizione da qualche parte devi poi calcolare, in media, quante giacche dovrai alzare prima di trovarla.
Se cerchi un elemento lo troverai dopo in media ceil(N / 2) tentativi.
Per calcolarlo, con N intero, puoi usare (N + 1) / 2
2 Mi Piace
Forse ho capito male, ma mi sembra che tu stia implicando che le giacche d’altri vengano alzate una dopo l’altra a partire dalla prima a sinistra, mentre in questo caso si tratta di selezione casuale. In entrambi i casi (primo e terzo appendino) verranno alzate in media lo stesso numero di giacche
1 Mi Piace
Si, in realtà volevo dire quello, l’idea non mi è chiarissimo perché l’idea risolutiva l’ha avuta un mio compagno di squadra, mi sono limitato a traslare in codice…
Questo qui non poteva essere risolto come ois_scrigni vero? Lì bastava una formula mentre qui ho usato un ciclo che ogni volta conta quante giacche vengono alzate ad ogni possibile appendino con due giacche (partendo da sinistra).
Il modo in cui ho fatto il calcolo io è questo:
Se ho N posizioni da “scoprire”, allora può succedere che io ne scopra 1, oppure 2, …, oppure N. Quindi, in media, ne devo scoprire (1+2+\dots+N)/N.
(1+2+\dots+N)/N = (N(N+1)/2)/N = (N+1)/2
Applicando al task, calcolo due numeri A (numero di cappotti nascosti) e B (numero di cappotti visibili), e faccio questo ragionamento:
- con una probabilità A/(A+B) il mio cappotto è nascosto (e in quel caso pago (A+1)/2 in media)
- con una probabilità B/(A+B) il mio cappotto è visibile (e in quel caso pago 0 in media)
Quindi la formula finale sarebbe: \frac{A}{A+B} \cdot \frac{A+1}{2} + \frac{B}{A+B} \cdot 0
Il secondo addendo si può togliere: \frac{A(A+1)}{2(A+B)}
Lascio anche il codice Python che avevo scritto 
#!/usr/bin/env python3
N = int(input())
v = list(map(int, input().split()))
nascosti = 0
totali = 0
for x in v:
if x == 2:
nascosti += 1
totali += x
expected = (nascosti + 1) / 2
print(expected * (nascosti / totali))
3 Mi Piace
Ciao, io non riesco a capire da dove venga quel (N+1)/2…potresti spiegarmelo?
^ Qui c’è il passaggio dopo il quale per semplificazione si arriva a (N+1)/2.
O forse chiedevi come si arriva a (N(N+1)/2)/N ?
Non c’entra nulla, ma… Non sarebbe interessante accettare anche Python (2 e/o 3) sia in gara che nella piattaforma di allenamento? Ovviamente ci saranno alcuni problemi in cui con python non si riesce a stare nei limiti di tempo e in tutti i problemi non si riuscirà a fare il tempo migliore, ma spesso in gara é preferibile rapidità nel scrivere codice è flessibilità delle strutture dati e in questo python farebbe un lavoro egregio
Si, chiedevo come si arriva a quella formula
Se ho N posizioni da “scoprire”, allora può succedere che io ne scopra 1, oppure 2, …, oppure N. Quindi, in media, ne devo scoprire (1+2+\dots+N)/N.
Per esempio, se ho 6 posizioni, può succedere che io ne scopra 1, oppure 2, …, oppure 6. In media, ne scoprirò 3.5 (la media tra 1, 2, 3, 4, 5, 6). Fin qui ci sei?
Quindi devo calcolarmi prima in media quanti ne dovrò scoprire e dopo?
Il problema chiede esattamente “in media quanti ne dovrò scoprire” quindi non c’è niente da fare dopo 
Tornando all’esempio che ti facevo, l’unica cosa che manca è notare che la risposta è 3.5 con una certa probabilità (se il cappotto non è visibile) oppure è 0 con probabilità opposta (se il cappotto è visibile). Chiama p questa probabilità (tieni conto che p è un numero reale compreso tra 0 e 1), la risposta sarà:
p \cdot 3.5 + (1 - p) \cdot 0
ovvero p \cdot 3.5
Ora, la probabilità p che il cappotto non sia visibile è data da num_cappotti_non_visibili / num_cappotti_totali.
Se hai altri dubbi chiedi
Il ragionamento che hai applicato è molto interessante!
Sai cosa potrei studiare per approfondire maggiormente questa tipologia di argomento e, magari, riuscire ad arrivare a queste soluzioni da solo? 
