Buongiorno a tutti,
ho in mente un problema non collegato alle Olimpiadi (per lo meno io non ho mai trovato un esercizio simile) ma che potrebbe essere interessante risolvere.
Il problema è comune e provo a spiegarlo con un esempio:
4 amici sono appassionati di calcio e si condividono le figurine. Ad esempio FB può comprare delle figurine e condividerle con tutti. Il giorno dopo AC fa lo stesso. La sera DI esce con SR, compra delle le figurine che vengono suddivise solo fra loro due. E così via.
Alla fine, ovviamente, ci sarà qualcuno che ha pagato più figurine di quante ne abbia, qualcun altro meno.
Secondo voi qual è la struttura dati e l’algoritmo più adatto per restituire i soldi nel minore numero di “transazioni” possibili? (se FB paga 10€ e regala tutte le figurine ad AC e AC fa lo stesso con DI, alla fine DI dovrà restituire 10€ a FB senza passare da AC).
Spero di essere stato abbastanza chiaro.
Grazie e tutti e buon ragionamento.
Quest’altro paper (6 pagine) sempre dello stesso autore ma molto più corto mostra alcuni “casi” e secondo me anche solo questo paper è sufficiente a capire l’algoritmo, il quale ha complessità O(N!) dove N è il numero di persone coinvolte.
@lukecavabarrett mi raccontò una volta di un modo per ridurre la complessità, ma solo lui sa spiegarlo!
Aggiungo che esistono diverse app per smartphone, tra le quali una piuttosto popolare è Splitwise, che fanno questo “conto” per te. Dato che il numero di persone che potresti dare in pasto all’app può ovviamente essere troppo alto (già con 20 la soluzione classica è lentissima) queste app fanno uso di euristiche per ridurre i tempi a discapito dell’ottimalità della soluzione.
