Connection Status:
Competition Arena > CanidsSeesaw

CanidsSeesaw

TCO17 Round 2C · 2017-03-31 · by cgy4ever

TCO17 Round 2C · 2017-03-31 · by cgy4ever · Simulation
Class Name: CanidsSeesaw
Return Type: int[]
Method Name: construct
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

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.

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 }

Submissions are judged against all 162 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CanidsSeesaw with a public method vector<int> construct(vector<int> wolf, vector<int> fox, int k) · 162 test cases · 2 s / 256 MB per case

Submitting as anonymous