Nombre de persones amb monedes X38065

Heu d’implementar un programa que manegui un conjunt de persones, i cuantes monedes té cada persona. El conjunt està inicialment buit. Tindrem instruccions per afegir una persona al conjunt i una indicació de cuantes monedes té. També tindrem instruccions per a eliminar una persona del conjunt. I també tindrem instruccions que ens demanen que escrivim per la sortida cuantes persones hi ha en un moment donat en el conjunt amb una certa cuantitat de monedes fixada. Fixeu-vos en la descripció de l’entrada i la sortida d’aquest exercici per a veure’n els detalls.

Observació: Podeu seguir l’enfoc que considereu oportú, i podeu utilitzar qualsevol de les estructures de dades presentades al curs (string, vector, stack, queue, list, map) de la manera que considereu oportuna. Però tingueu en compte que la vostra elecció pot afectar a l’eficiència de la vostra solució, i per tant al fet de poder superar tots els jocs de proves o només els públics (cosa que us deixarà amb la meitat de la nota).

Entrada

Cada linia de l’entrada consisteix en una instrucció del següent tipus, a on name és un string no buit qualsevol de menys de 20 caràcters, i numcoins és un natural positiu qualsevol que cap en una variable de tipus int:

• ADD name numcoins

• DELETE name

• NUMPEOPLE numcoins

La instrucció ADD name numcoins ens demana que afegim algú anomenat name al conjunt, i que aquesta persona nova té numcoins monedes.

La instrucció DELETE name ens demana que eliminem algú anomenat name del conjunt.

La instrucció NUMPEOPLE numcoins ens demana que escrivim per la sortida el nombre actual de persones del conjunt que tenen exactament numcoins monedes.

Podem suposar que les entrades son tals que els noms de persones s’utilitzen com a molt un cop i de forma coherent, és a dir: donat un name concret, podem suposar que hi haurà com a molt una instrucció ADD name numcoins i com a molt una instrucció DELETE name. A més a més, si apareix una instrucció DELETE name, necessàriament haurà aparegut abans un ADD name numcoins amb el mateix name.

Sortida

Per a cada instrucció NUMPEOPLE numcoins, s’escriurà una línia per la sortida amb el nombre actual de persones que tenen numcoins monedes.

Observació

Avaluació sobre 10 punts:

• Solució lenta: 5 punts.

• solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost $n\log(n)$ o inferior, i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.