Soluzione monete GATOR 2016

qualcuno sa la soluzione dell’algoritmo monete?
monete (it).pdf (220,9 KB)

Io l’ho risolto facendo un ragionamento del tipo: se analizzo tutti i contenitori che stanno sotto ad un nodo qualsiasi, sono nel complesso in eccesso o difetto di monete, allora tutte le monete che devo aggiungere/togliere per mette a posto tutto quello che sta sotto devono “passare” per forza dal nodo che sto considerando.
Non so se mi sono spiegato bene, fammi sapere se hai capito :slight_smile:

potresti postare il codice sorgente?

Magari prova a ragionarci un po’ su prima di guardare il codice :grin:, volendo puoi provare a sottoporlo nell’ambiente di gara, dato che è aperto di nuovo e si può sottomettere ancora.

Comunque ecco il codice: https://ideone.com/SRPvdH

Un’altra soluzione, sicuramente più lunga da implementare ma che si basa su un concetto forse più immediato da capire, si basa sul fatto che se una foglia ha un numero di monete diverso da 1, sicuramente lo spostamento di monete riguarderà il nodo padre (sia che si tratti di monete in eccesso che in difetto).
In particolare, se abbiamo un numero di monete maggiore di 1, aggiungeremo le monete in eccesso al numero di monete del padre mentre se il numero è minore di 1 le sottrarremo.

(Anche se in input ciascun nodo ha minimo 0 monete, seguendo questo ragionamento è possibile avere anche dei nodi con peso temporaneamente negativo)

Lascio a te la parte divertente, ovvero come capire quali nodi sono le foglie e come simulare la rimozione delle foglie già considerate :slight_smile:

Puoi usare un array per memorizzare quanti figli ha ciascun nodo e aggiornarlo man mano che “elimini” le foglie.
Ogni volta che aggiorni un nodo, controlli se è diventato una foglia.