ZOJ Problem Set - 1345
Tom, a young explorer, visited an Indian tribe and fell in love with the Chief's daughter. Tom asked the Chief to marry his daughter to him. But the Chief would accept his proposal only if he could provide 10000 golden coins as the engagement gift. Tom couldn't make it, so he pled for a reduction. The Chief said:" OK, I would then request 8000 golden coins if you could get me the fur coat of the Pontiff. Or, if you could get me his crystal, I could drop to 5000 golden coins."
Tom then went to the Pontiff for his fur coat or crystal. The Pontiff too requested some amount of golden coins as the exchange, or a possible reduction of price if Tom could get him some other things. Tom continued to visit other people and found that all of them would either request some golden coins for exchange, or drop the price down for something else.
Now Tom needs your help on trading to marry the girl he loves.
An important rule Tom has to tell you is: the hierachical system is so strict in this tribe that two people will never contact each other in any way if the difference of the two levels they belong to is larger than a certain threshold. Tom is an outsider so he is beyond this restriction. However, if he trades with someone in a lower level, then others in a higher level will not trade with him anymore since otherwise they would be indirectly contacting the lower levels, and vice versa. Therefore your best suggestion to him must have all the situations considered.
For the sake of convenience, let us mark all the trading objects by numbers starting from 1. The Chief's approval is as well considered an object and is always marked 1. Each object has a price P, the owner's level L, and a sequence of substitutions Ti and the corresponding "voucher" price Vi. There must be no "indirect trading" if the difference between two levels is greater than M. You must calculate the least number of golden coins Tom needs to marry the daughter of the Chief.
1 4 10000 3 2 //The Chief's approval 2 8000 3 5000 1000 2 1 //The Pontiff's fur coat 4 200 3000 2 1 //The Pontiff's crystal 4 200 50 2 0 //Another object
Source: Zhejiang University Local Contest 2002