Demonstration Task 3: Fruit

Jack and Jill are driving from Niagara Falls to Waterloo. Along the way, they pass several fruit stands. Each fruit stand sell baskets of cherries at one price, and baskets of peaches at another price. Jack wants to buy a basket of cherries, and Jill wants to buy a basket of peaches. They wish to stop at only one fruit stand. Which fruit stand should they stop at to minimize the total cost?

You are to implement a procedure stopat(N,C,P). N is the number of fruit stands. The fruit stands are numbered from 0 to N-1. C and P are arrays representing the prices of cherries and peaches at each fruit stand, in dollars. C[i] is the price of a basket of cherries at the fruit stand numbered i. P[i] is the price of a basket peaches at the fruit stand numbered i. stopat(N,C,P) must return the number of the first fruit stand that has the lowest possible total price for a basket of cherries and a basket of peaches.

Subtask 1 [50 points]

Assume N≤10. The prices for baskets of cherries and peaches will be between 1 and 100 dollars each.

Subtask 2 [50 points]

Assume that N≤1000. The prices for baskets of cherries and peaches will be between 1 and 1000 dollars each.

Implementation Details

• Use the RunC programming and test environment
• Implementation folder: /home/ioi2010-contestant/fruit/ (download prototype here)
• To be implemented by contestant: fruit.c or fruit.cpp or fruit.pas
• Contestant interface: fruit.h or fruit.pas
• Grader interface: none
• Sample grader: grader.c or grader.cpp or grader.pas and graderlib.pas
• Sample grader input: grader.in.1 grader.in.2
  Note: The grader reads a sequence of pairs (C[0],P[0]), (C[1],P[1]), ... (C[N-1],P[N-1]), where N is the number of pairs.
• Expected output for sample grader input: grader.expect.1 grader.expect.2
• Compile and run (command line): runc grader.c or runc grader.cpp or runc grader.pas
• Compile and run (gedit plugin): Control-R, while editing any implementation file.
• Submit (command line): submit grader.c or submit grader.cpp or submit grader.pas
• Submit (gedit plugin): Control-J, while editing any implementation or grader file.
• CPU time limit: 10 seconds
• Memory limit: 256 MB