JOIN
Get Time

   Problem Statement  

 Problem Statement for CanidsSeesaw

Problem Statement

    There are n wolves and n foxes. Both wolves and foxes are numbered 0 through n-1. You are given the int[]s wolf and fox. Here, wolf[i] is the weight of wolf i and fox[i] is the weight of fox i.



The wolves and the foxes are playing on a seesaw. Initially both sides of the seesaw are empty. Then, there will be n rounds. In each round a new wolf will sit on the left side of the seesaw and a new fox will sit on the right side of the seesaw. The wolves and foxes stay on the seesaw also for all future rounds. Thus, after x rounds there will be x wolves on the left side of the seesaw and x foxes on its right side.



After each round, the side of the seesaw that touches the ground scores a point. All animals sit very close to the ends of the seesaw, hence the side that touches the ground is always the side where the total weight of animals is greater. (The constraints guarantee that there will never be a draw: one side will always be heavier than the other.)



The wolves will go sit on the seesaw in numerical order: wolf 0 first, wolf 1 second, and so on. The foxes may choose any order in which to go on the seesaw.



You are given an int k. The foxes want to score exactly k points. Can they do that? If yes, in what order should they go on the seesaw?



Find and return a int[] containing a permutation of 0 through n-1: an order in which the foxes should go on the seesaw in order to score exactly k points. That is, return a int[] p such that fox p[0] should go on the seesaw first, fox p[1] second, and so on.



If there are multiple solutions, you may return any of them. If there is no solution, return an empty int[] instead.
 

Definition

    
Class:CanidsSeesaw
Method:construct
Parameters:int[], int[], int
Returns:int[]
Method signature:int[] construct(int[] wolf, int[] fox, int k)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 50, inclusive.
-wolf will contain exactly n elements.
-fox will contain exactly n elements.
-Each element in wolf will be between 1 and 3000, inclusive.
-Each element in fox will be between 1 and 3000, inclusive.
-k will be between 0 and n, inclusive.
-For every permutation of the foxes, after each round the weights on both sides of the seesaw will be different.
 

Examples

0)
    
{3,1}
{4,2}
1
Returns: {1, 0 }
First, note that after two rounds the wolves on the seesaw will have a total weight of 3+1 = 4, and the foxes will have a total weight of 4+2 = 6. At that moment the foxes will score a point. As they want to score exactly one point, they have to make sure that after the first round the wolves score a point. In order to do that, fox 1 should go on the seesaw first.
1)
    
{1,3}
{4,2}
1
Returns: { }
This time the foxes will surely score both points, so there is no solution.
2)
    
{10,10,10,10,10,10,10,10,10,10}
{1,100,1,100,1,100,1,100,1,100}
7
Returns: {0, 2, 4, 1, 6, 3, 5, 7, 9, 8 }
3)
    
{10,10,10,10,10,10,10,10,10,10}
{1,100,1,100,1,100,1,100,1,100}
4
Returns: { }
4)
    
{2}
{1}
0
Returns: {0 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2017 TCO Algorithm Round 2C - Division I, Level One
       2017 TCO Algorithm Parallel Round 2C - Division I, Level One