Dramatic chipmunks P22418
These mischievous long-toothed chewers spend all day looting the tree’s pears and plotting schemes to steal them from each other. Mr William and Mr Christopher must put up in martyrdom with their high-pitched rodent-voiced discussions:
– Oh, Rosencrantz, thou long-tailed knave!
Wherefore doeth thou steal mine pears?
– Nay, Guilderstern! Voltemand stole thy pears,
that cockered motley-minded hugger-mugger.
– Ah, the churlish rascal…And he also stole from
that dismal-dreaming low-classed fustilarian, Laertes!
– This mustn’t be true…Laertes stole from Horatio, and Horatio stole from Voltemand himself.
For nut’s sake, this impudent stravaganza of debauchery
shall not be tolerated in this hallowed tree!
After all plundering, larceny, and bickering, at the end of the day the
chipmunks indulge in gluttony and consume the fruits of their
pillaging before falling asleep inebriated from their vice.
Can you help Mr William and Mr Christopher figure out how many of their precious pears fall victims of all this unnecessary daily drama?
Input
Input consists of several cases. Each case starts with the number of thefts n and the number of pears p each chipmunk will eat at the end of the day. Both n and p are between 1 and 104. Follow n triples s t x indicating that s stole x pears from t, where s and t are words made up of between 1 and 20 letters, and x is an integer between 1 and 104. The robberies are not necessarily given in chronological order. All chipmunks are at least either the subject or the object of an intended theft.
A chipmunk that steals from another one will be considered of lower class than the former. Chipmunks acknowledge this classist relationship transitively, and a higher-class chipmunk should never steal from a lower-class one. When a chipmunks identifies that it could engage in a stealing cycle, it will leave the tree before thefts start, to avoid shaming—even if all other chipmunks are also leaving.
Output
For each case, print the minimum number of pears that would make it possible for the described thefts to happen, and still allow for each chipmunk which did not take part in any cycle to eat (at least) p pears after that.
Input
1 1 Voltemand Guilderstern 3 1 3 Voltemand Guilderstern 3 3 2 Voltemand Guilderstern 3 Cornelius Guilderstern 1 Cornelius Rosencrantz 1 4 3 Voltemand Guilderstern 1 Voltemand Laertes 1 Laertes Horatio 1 Horatio Voltemand 1 3 3 Voltemand Laertes 1 Laertes Horatio 1 Horatio Voltemand 1
Output
4 6 9 3 0
- Author
- Edgar Gonzalez
- Language
- English
- Official solutions
- C++
- User solutions
- C++