Input File: curryin.txt
Output File: curryout.txt
Time Limit: 1 second
You are at a very fancy dinner party with some very good friends, trying to eat a very hot curry. On your plate is a pile of curry, rice and vegetables. You are finding it quite difficult to eat, since the curry is too hot, the rice is too sticky and you don't like vegetables.
To work around this problem, you eat in such a way that each mouthful includes a scoop of two different items. For example, the first mouthful might include a scoop of curry with a scoop of rice. The next mouthful might include a scoop of rice with a scoop of vegetables. You cannot eat three scoops all at once, since your spoon is too small.
The danger with your plan is that you might not be able to finish your meal. At last week's dinner party you started off by eating all your curry and rice, which meant that you could not finish your vegetables since there was nothing left to eat them with. It was most embarrassing. Determined not to be humiliated again, you pull your laptop out of your bag and tap away secretly beneath the table, hoping to solve your eating problems for once and for all.
Your task is to work out how to eat your meal so that you eat as much total food as possible.
There will be only one line of input. This line will contain the three integers c r v (each separated by a single space), representing the number of scoops of curry, rice and vegetables on your plate. You are guaranteed that 0 <= c,r,v <= 100,000.
The output must be a single line containing the integers x, y and z (separated by spaces), where:
5 6 9
5 4 1
You begin the meal with 5 scoops of curry, 6 scoops of rice and 9 scoops of vegetables. You start by taking five mouthfuls of rice with vegetables, leaving you with 5, 1 and 4 scoops of curry, rice and vegetables respectively. You then take four mouthfuls of curry with vegetables, leaving you with 1, 1 and 0 scoops of curry, rice and vegetables respectively. Finally you take one mouthful of curry with rice, and the meal is completely finished.
1 2 5
2 1 0
Your second meal has 1, 2 and 5 scoops of curry, rice and vegetables respectively. This is a lot of vegetables, and you can't possibly finish them all. The solution above involves two mouthfuls of rice with vegetables and one mouthful of curry with vegetables. This completely finishes your curry and rice, but leaves you with two scoops of vegetables remaining. There is no other way of eating the meal that leaves less food at the end, and so 2 1 0 is your final output.
The score for each input file will be 100% if a correct solution is written to the output file and 0% otherwise.