TopCoder problem "ApplePie" used in TCHS SRM 18 (Division I Level One)



Problem Statement

    

You have decided to make an apple pie. For this you need howMany apples. You are going to gather the apples from your garden. An apple can only be gathered once it falls on the ground. Unfortunately, you discovered that some apples are going to fall on your neighbors' garden, because your tree has grown out of your garden's bounds.

Given the exact coordinates where each apple falls (x[i] and y[i] are the coordinates for the i-th apple), and the exact day when it will fall (day[i] is the day for the i-th apple), determine the day on which you will have all the apples you need to make your pie. If it's impossible to gather howMany apples, return -1.

Your garden is a rectangle with corners (0,0), (0,100), (100,100) and (100,0). If an apple falls within, or on the border of your garden, you can gather it. Apples that fall outside your garden belong to your neighbors.

 

Definition

    
Class:ApplePie
Method:getApples
Parameters:int[], int[], int[], int
Returns:int
Method signature:int getApples(int[] x, int[] y, int[] day, int howMany)
(be sure your method is public)
    
 

Notes

-Don't worry that your apples fall during the whole year. You will be able to find them in snow.
 

Constraints

-x, y and day will all contain the same number of elements, between 1 and 50, inclusive.
-Each element of x and y will be between -1000 and 1000, inclusive.
-Each element of day will be between 1 and 365, inclusive.
-Elements of day will be in non-descending order (that is, day[i] will be less than or equal to day[i+1] for all i).
-howMany will be between 1 and the number of elements in x, inclusive.
 

Examples

0)
    
{0,50,600,50}
{0,-400,100,40}
{1,4,6,8}
2
Returns: 8
You can take the apples that fall on days 1 and 8.
1)
    
{14,-958,38,32,69}
{48,485,58,76,75}
{1,2,3,6,15}
3
Returns: 6
2)
    
{-1}
{100}
{5}
1
Returns: -1
The only apple falls outside your garden.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6772

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10070&pm=6772

Writer:

rusolis

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Geometry, Sorting