This Weeks Problems
Week #1
Curry:[INDENT] [BANANA]
Input File: curryin.txt Output File: curryout.txt Time Limit: 5 seconds[/BANANA]
[/INDENT][INDENT] 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.
[/INDENT][INDENT]
Input:[INDENT] 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.
[/INDENT]
Output:[INDENT] The output must be a single line containing the integers x, y and z (separated by spaces), where:
- x is the number of mouthfuls containing a scoop of rice with a scoop of vegetables;
- y is the number of mouthfuls containing a scoop of curry with a scoop of vegetables;
- z is the number of mouthfuls containing a scoop of curry with a scoop of rice.
You must choose x, y and z so that you eat the maximum total number of scoops possible. If there is more than one way of doing this, any solution will do. [/INDENT]
From: Sample Input #1
Sample Input:[INDENT] 5 6 9
[/INDENT]Sample Output:[INDENT] 5 4 1
[/INDENT]Explanation:[INDENT] 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. [/INDENT]
From: Sample Input #2
[INDENT]Sample Input:[INDENT] 1 2 5
[/INDENT] Sample Output:
[/INDENT][INDENT][INDENT] 2 1 0
[/INDENT][/INDENT][INDENT] Explanation:[INDENT] 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. [/INDENT][/INDENT]
Scoring:[INDENT] The score for each input file will be 100% if a correct solution is written to the output file and 0% otherwise.
[/INDENT][/INDENT]
Chimpanzee:
[INDENT][BANANA]
Input File: chimpin.txt Output File: chimpout.txt Time Limit: 2 seconds[/BANANA]
It has been a long hard day trekking through the jungle, and it is almost dark. Exhausted, you sit down to rest and pull a book from your backpack for some light reading. Suddenly, with an excited cry, a chimpanzee leaps from a nearby tree and snatches the book from your hands.
In horror you watch as the chimpanzee runs through the jungle in a spiral pattern, ripping pages from your book as it goes. Soon your horror gives way to curiosity as you contemplate the very precise spiral pattern that the chimpanzee is following.
Consider the jungle to be a grid of squares in a coordinate system, where you are sitting at square (0,0). The chimpanzee follows a tight spiral out from (0,0) as illustrated below:
The pages of your book are numbered from 0 upwards. At each square on the spiral, the chimpanzee tears a new page from your book. Thus page 0 is left at square (0,0), page 1 is at square (1,0), page 2 is at square (1,1), page 3 is at square (0,1), page 4 is at square (-1,1) and so on.
Fortunately you have also brought your laptop on your jungle trek. Pulling it from your bag and plugging it into a nearby power point, you sit down to write a program that will help you put the pages together in the correct order.
Your specific task is to write a program that reads in a pair of (x,y) coordinates and outputs which page the chimpanzee has left in that square.
Input:[INDENT] The input will consist of a single line containing integers x and y separated by a single space (-1000 <= x,y <= 1000).
[/INDENT]
Output:[INDENT] Your output must be a single line containing a single integer, which is the page number that the chimpanzee left in square (x,y). You may assume that your book is very thick and the chimpanzee does not run out of pages.
[/INDENT]
From: Sample Input #1
Sample Input:[INDENT] -1 1
[/INDENT]Sample Output:[INDENT] 4[/INDENT]
From: Sample Input #2
Sample Input:[INDENT] 2 1
[/INDENT]Sample Output:[INDENT] 11[/INDENT]
Scoring:[INDENT] The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.[/INDENT][/INDENT]
