Statistics

Problem Statement for "BalancingGame"

Problem Statement

NOTE: This problem statement contains subscripts and superscripts that may not appear correct when viewed outside of the contest applet.

You are playing a game with a flat board on top of a thin post. On this board are items of various weights, placed in a such a manner that the board balances on top of the post. You and your opponent take turns removing items from the board. If at any time the board falls off the post, whoever removed the last item causing the board to fall loses. If all objects are removed without the board falling, the player who moved first loses.

The board balances if the magnitude of the total torque due to the weight of all objects upon it does not exceed a given threshold. The torque due to a single object is a vector in the plane of the board, computed as: 


    (Tx,Ty) = (-y*w,x*w)

Where x and y are the position of the object, and w is its weight. Assume the board is centered on the post, and that the torque due to its own weight is zero. The total torque is the sum of the torque vectors for each object, and the magnitude is the length of that sum.

The position and weight of the objects will be given by three int[] parameters: x, y, and w. x[i], y[i] gives the position of object i, and w gives its weight. The x,y coordinates are relative to the origin, the point where the board rests on the post. Multiple objects can not have the same position on the board.

Return a list of all the objects that the first player could remove on his first turn in order to win the game, assuming that both players play optimally. The return value should be a int[], where each element corresponds to an entry in the x, y, and w int[]s. The elements should be sorted in ascending order. If there are no possible winning moves, return an empty int[].

If the initial state of the board is unbalanced, it will fall before the first player has a chance to make a move. In this case, return { -1 }.

Definition

Class:
BalancingGame
Method:
winningMoves
Parameters:
int[], int[], int[], int
Returns:
int[]
Method signature:
int[] winningMoves(int[] x, int[] y, int[] w, int threshold)
(be sure your method is public)

Notes

  • (x1, y1) + (x2, y2) = (x1 + x2, y1 + y2).
  • The square of the length of (x, y) is x2 + y2.

Constraints

  • x will contain between 1 and 20 elements, inclusive.
  • x, y, and w will all contain the same number of elements.
  • Each element of x and y will be between -100 and 100, inclusive.
  • Each element of w will be between 1 and 100, inclusive.
  • threshold will be between 0 and 1000000000, inclusive.
  • No two objects will occupy the same position.

Examples

  1. { -10, 0, 10 }

    { 0, 0, 0 }

    { 5, 5, 5 }

    1

    Returns: {1 }

    There are three objects, one in the center of the board and two others at equal distances and opposite directions from the center. If the first player removes the center object first, the board will continue to balance perfectly. But, the board will fall if the second player removes either of the remaining objects. Therefore, this is a winning move for the first player. The other two possible moves for the first player are losing moves, because the board will fall immediatly if either of the other two objects are removed first.

  2. { 1, -1, 1, -1 }

    { -1, -1, 1, 1 }

    { 2, 3, 4, 5 }

    10000

    Returns: { }

    With such a high threshold, the objects can be removed in any order without the board ever falling. Since all moves lead to an empty board, the first player always loses.

  3. { 0 }

    { 10 }

    { 50 }

    15

    Returns: {-1 }

  4. { -20, -21, 60 }

    { 0, 0, 0 }

    { 20, 20, 10 }

    300

    Returns: {0, 1 }

    The initial torque on the board is the sum of the vectors (0,-400) + (0,-420) + (0,600) = (0,-220). The magnitude of the torque, 220, is less than the threshold, so the board initially balances. If the first player removes either of the objects with a weight of 20, the resulting torque will be (0,180) or (0,200), which also balances. The second player loses, because removing either of the two remaining objects causes the board to fall. If the first player removes the object with a weight of 10, the resulting torque will be (0,-820), and the board will fall.

  5. { -3, -30, 0, 0, 3, 30 }

    { -2, 20, 3, -30, -2, 20 }

    { 6, 50, 7, 51, 8, 52 }

    1000

    Returns: {0, 2, 4 }

  6. { 0 }

    { -100 }

    { 100 }

    10000

    Returns: { }

  7. { 0 }

    { -100 }

    { 100 }

    9999

    Returns: {-1 }

  8. { 0 }

    { -100 }

    { 100 }

    50000

    Returns: { }

  9. { 67, 79, -16, -2, -12, -2, -99, -43, 59, 81, -58, -31, 10, 1, 12, 12, 10, -77, 62, -58 }

    { -20, -34, 45, 96, 70, 37, 37, -69, 15, 74, -48, 17, -94, -46, 71, -21, 22, -7, -94, -58 }

    { 30, 38, 42, 10, 34, 29, 97, 18, 60, 86, 51, 12, 32, 90, 74, 86, 85, 39, 53, 5 }

    5834

    Returns: {0, 1, 2, 3, 4, 5, 8, 9, 16 }

  10. { -46, -24, 28, -16, -59, 61, -24, -52, -10, -56, -92, -26, 34, 21, -8, 44, -73, 5, 32, 44 }

    { -19, -45, 54, 32, 26, 90, -71, 55, -27, -94, -49, 8, 31, 55, 39, -23, 7, -42, 50, -10 }

    { 29, 93, 14, 57, 33, 28, 11, 5, 44, 16, 20, 2, 64, 63, 69, 37, 17, 98, 46, 66 }

    1996

    Returns: {2, 3, 5, 7, 11, 13, 14, 18 }

  11. { 59, -8, -24, -58, 29, 94, -50, 2, 14, -100, 43, -18, 48, 44, 63, 84, -20, 96, 56, -86 }

    { 71, -88, 16, -19, -5, 99, 68, 69, -34, -100, 33, 44, 30, -87, -30, 82, 82, -99, 21, 19 }

    { 42, 86, 31, 74, 24, 13, 15, 54, 59, 36, 36, 34, 10, 12, 18, 77, 81, 87, 38, 87 }

    6872

    Returns: {0, 4, 5, 7, 10, 12, 14, 15, 18 }

  12. { -73, -71, 14, 76, 54, 8, -42, 15, 70, 57, -10, 49, 24, -11, 59, 91, -41, -35, -3, -14 }

    { 81, -34, 52, 30, -63, -98, -13, 2, -55, 39, -46, 60, 64, -92, 98, -86, 43, -63, -41, -17 }

    { 21, 52, 87, 14, 1, 2, 47, 24, 31, 14, 16, 2, 14, 1, 72, 30, 51, 77, 62, 62 }

    1450

    Returns: {4, 7, 9, 11, 12, 13 }

  13. { -77, 63, 49, 75, 22, -46, 15, 54, -60, 34, -100, -52, 82, -3, -40, -22, -17, -5, -75, 30 }

    { -51, -47, 77, 41, -67, -39, 86, -82, 48, -14, 39, 18, 23, -72, -87, 51, -50, 29, 16, 52 }

    { 6, 31, 47, 49, 2, 37, 27, 6, 47, 63, 18, 1, 9, 35, 93, 8, 17, 24, 43, 7 }

    3965

    Returns: {0, 4, 5, 7, 10, 11, 13, 16, 18 }

  14. { -19, 69, -92, -71, 94, -8, -84, -55, 35, 54, 81, -79, -55, 98, -91, 46, -54, 94, 28, -85 }

    { -18, -69, 55, -46, 92, -54, -86, -46, -41, -64, 71, -42, -14, -48, 68, -71, 69, 93, 65, 91 }

    { 18, 47, 56, 96, 56, 31, 33, 36, 2, 57, 65, 70, 14, 46, 17, 64, 12, 42, 48, 30 }

    3480

    Returns: {0, 1, 5, 8, 9, 15 }

  15. { -52, 2, -76, 100, 26, -100, -22, -75, 67, 34, -37, -41, 1, 85, -68, 6, 61, 56, -2, 29 }

    { 35, -24, -87, -26, 79, 65, -83, 14, 24, 17, -30, 94, -59, 23, -52, -44, 67, -55, -19, 51 }

    { 16, 98, 3, 93, 2, 90, 59, 53, 33, 67, 80, 30, 34, 6, 16, 93, 34, 1, 50, 67 }

    2911

    Returns: {1, 2, 6, 10, 12, 14, 15, 17, 18 }

  16. { -20, -41, -54, 60, -95, 53, 76, -22, -99, 19, 87, -62, -6, 59, -37, -87, 66, 0, 28, 79 }

    { 74, 78, 99, 44, 44, -9, 44, -5, -80, -19, 14, -9, -66, -39, -58, -91, 86, 68, -87, 6 }

    { 27, 17, 13, 28, 47, 95, 70, 77, 19, 1, 32, 35, 85, 10, 6, 92, 56, 90, 65, 61 }

    5889

    Returns: {5, 16 }

  17. { -52, 87, -2, 73, -51, -26, -66, -56, 5, 19, -59, 57, -18, -19, 6, 48, -52, 45, -22, -37 }

    { 79, 22, -59, 33, -42, 72, -23, -11, 2, -93, 4, -18, 26, -87, 7, 95, -78, -29, -43, 27 }

    { 27, 41, 66, 3, 51, 35, 1, 49, 14, 36, 74, 27, 77, 33, 17, 92, 17, 47, 56, 22 }

    4558

    Returns: {0, 4, 6, 7, 10, 12, 13, 16, 18, 19 }

  18. { 56, -9, -80, 68, 88, 25, -80, 53, -92, -15, -45, 97, 58, -12, 39, -98, -23, 76, -58, 48 }

    { 88, 41, 55, -71, 58, -39, -13, -5, 7, 67, -28, -71, -9, 43, 78, -40, -70, -71, 92, -12 }

    { 12, 26, 51, 18, 91, 35, 61, 84, 23, 70, 98, 79, 26, 37, 21, 58, 58, 28, 27, 76 }

    5286

    Returns: {3, 5, 7, 12, 17, 19 }

  19. { -70, 46, -92, 16, -58, -57, 62, 27, 27, -22, 36, 61, 64, -97, 48, 33, 93, -29, -49, -35 }

    { -64, 85, 50, -18, -57, -59, 66, -69, 17, -35, 78, -36, 33, -15, 81, -4, 5, -27, 65, 24 }

    { 90, 65, 6, 43, 77, 18, 30, 83, 72, 24, 16, 94, 8, 56, 73, 82, 64, 77, 56, 82 }

    3792

    Returns: {3, 9, 11, 12, 15 }

  20. { 15, 83, -17, 31, -29, 17, -22, -94, -43, -82, -11, 86, 85, 21, 73, -98, 38, 69, -74 }

    { -89, -98, -22, 74, -97, 85, 78, 33, 31, -85, -82, -100, 5, 58, 31, 9, 60, 46, -50 }

    { 24, 12, 47, 45, 9, 49, 84, 2, 81, 95, 1, 91, 5, 2, 18, 26, 43, 63, 14 }

    2413

    Returns: {0, 1, 2, 4, 7, 10, 12, 13, 14, 18 }

  21. { -78, -93, 80, -51, 82, 88, -13, -98, -91, 87, 4, 15, -98, -37, 85, -92, -27, 66, 27 }

    { -25, -67, 59, 21, 61, 65, 15, -43, 83, -88, 42, 58, -84, -20, -66, -58, -84, -57, -14 }

    { 54, 10, 36, 94, 15, 83, 61, 72, 41, 42, 43, 74, 6, 66, 83, 39, 34, 32, 52 }

    3648

    Returns: {0, 1, 12, 13, 15, 16 }

  22. { -88, -26, 40, 6, -96, -49, 60, 71, -53, -93, -26, 73, 81, -57, -62, -28, 17, 52, -51 }

    { 34, -27, 68, 40, -60, 46, -21, 23, -68, -93, 5, -37, -89, 93, 69, 6, -13, 52, 30 }

    { 44, 1, 49, 40, 10, 68, 92, 28, 6, 44, 4, 12, 93, 98, 3, 81, 98, 26, 35 }

    5573

    Returns: {0, 1, 2, 3, 5, 10, 14, 15, 17, 18 }

  23. { -76, -82, 14, -11, 32, 100, -22, 36, 49, -93, -87, -81, 28, 57, 54, -80, -96, 91, 86 }

    { -54, -5, -97, -12, 59, 12, 32, 86, 57, -13, -27, -83, -82, -14, 86, 61, 81, 68, -77 }

    { 11, 86, 6, 51, 3, 19, 7, 2, 81, 95, 32, 30, 88, 20, 96, 54, 1, 56, 48 }

    4203

    Returns: {0, 4, 6, 7, 10, 15, 16 }

  24. { -59, 95, -12, -49, 89, -4, -77, 96, -76, 15, -93, 41, -56, 94, 79, -63, 77, 5, -4 }

    { 45, -72, 11, 18, -21, -61, 46, 52, -2, 13, -22, 56, -22, -46, -74, -94, 30, -36, 60 }

    { 54, 31, 45, 67, 84, 37, 24, 9, 82, 47, 72, 84, 68, 36, 62, 16, 65, 22, 43 }

    3138

    Returns: {1, 5, 7, 13, 15, 17 }

  25. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    {1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }

    {1, 32, 53, 23, 56, 34, 32, 65, 43, 23, 23, 55, 43, 33, 22, 44, 66, 44, 33, 22 }

    1000000

    Returns: { }

  26. {0 }

    {0 }

    {19 }

    1000000

    Returns: { }

  27. {-10, 0, 10 }

    {0, 0, 0 }

    {5, 5, 5 }

    1

    Returns: {1 }

  28. {0, 0, 0, 0 }

    {1, -1, 100, -100 }

    {1, 1, 1, 1 }

    10

    Returns: { }

  29. {1, -1, 1, -1, 0 }

    {-1, -1, 1, 1, 0 }

    {2, 3, 4, 5, 1 }

    10000

    Returns: { }

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: