Statistics

Problem Statement for "ColorfulCoinsEasy"

Problem Statement

The currency system in Colorland consists of various types of coins. The coin denominations follow these simple rules:
  • The denominations are distinct positive integers.
  • There is a coin type with denomination 1.
  • For each pair of different coin types, the denomination of one coin type divides the denomination of the other one.
You are given a int[] values containing all the available denominations in ascending order.

Coins of different denominations look exactly the same except that they have different colors. Each coin in Colorland has exactly one color. The coin colors follow these even simpler rules:
  • All coins of the same type are of the same color.
  • No two coins of different types are of the same color.
You know all coin denominations used in Colorland, but you don't know their colors. You don't even know the set of colors used on the coins.

For each denomination, you'd like to know the color of coins of this denomination. To accomplish this, you've got a credit card with an infinite amount of money. You can perform a single query to an ATM which can also provide you with an infinite amount of money. The query is described by a positive integer X, which means that you want to receive exactly X units of money from the ATM. The ATM will provide you with the requested amount. You also know that the requested amount will be paid using the smallest possible number of coins. (Note that this rule always uniquely determines the set of coins chosen to make the payment.)

Return "Possible" (quotes for clarity) if it's possible to determine the color of coins of each denomination, and return "Impossible" otherwise.

Definition

Class:
ColorfulCoinsEasy
Method:
isPossible
Parameters:
int[]
Returns:
String
Method signature:
String isPossible(int[] values)
(be sure your method is public)

Constraints

  • values will contain between 1 and 15 elements, inclusive.
  • Each element of values will be between 1 and 20000, inclusive.
  • values will be sorted in strictly ascending order. Note that this also implies that all the elements of values will be distinct.
  • For each pair of different elements in values, the smaller one will be a divisor of the larger one.
  • values[0] will be 1.

Examples

  1. {1}

    Returns: "Possible"

    For any positive X, you'll get exactly X coins of denomination 1, so you'll easily learn their color.

  2. {1, 3}

    Returns: "Possible"

    X = 5 is one possible solution. As the ATM gives the smallest number of coins, it will give one coin of denomination 3 and two coins of denomination 1. That means, for example, that if you get one red coin and two blue coins, you'll understand that coins of denomination 3 are red, and coins of denomination 1 are blue.

  3. {1, 2, 4}

    Returns: "Impossible"

    It can be proven that for any X, you'll get at most one coin of denomination 1, and at most one coin of denomination 2. If you get no coins of some denomination, clearly you won't be able to determine their color. However, if you get one coin from each of denominations 1 and 2, you won't be able to find out which of the two colors represents which denomination.

  4. {1, 5, 15, 90}

    Returns: "Possible"

    X = 504 is one possible solution. You'll get five coins of denomination 90, three coins of denomination 15, one coin of denomination 5 and four coins of denomination 1.

  5. {1, 4, 20, 60, 180, 1440, 5760}

    Returns: "Impossible"

  6. {1, 7, 21, 105, 630, 3150, 18900}

    Returns: "Possible"

    X = 137969 is the smallest possible solution.

  7. {1, 10, 30, 300, 900, 9000, 18000}

    Returns: "Impossible"

  8. {1, 2, 10, 40, 200, 1000, 4000, 20000}

    Returns: "Impossible"

  9. {1, 2}

    Returns: "Possible"

  10. {1, 42}

    Returns: "Possible"

  11. {1, 20000}

    Returns: "Possible"

  12. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384}

    Returns: "Impossible"

  13. {1, 2, 8, 16, 64, 512, 4096, 16384}

    Returns: "Impossible"

  14. {1, 2, 8, 64, 512, 4096, 16384}

    Returns: "Possible"

  15. {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683}

    Returns: "Impossible"

  16. {1, 9, 27, 243, 729, 2187, 19683}

    Returns: "Impossible"

  17. {1, 9, 27, 243, 729, 19683}

    Returns: "Possible"

  18. {1, 4, 16, 64, 256, 1024, 4096, 16384}

    Returns: "Impossible"

  19. {1, 16, 256, 1024, 4096, 16384}

    Returns: "Possible"

  20. {1, 5, 25, 125, 625, 3125, 15625}

    Returns: "Impossible"

  21. {1, 5, 25, 125, 3125, 15625}

    Returns: "Possible"

  22. {1, 6, 36, 216, 1296, 7776}

    Returns: "Possible"

  23. {1, 10, 100, 1000, 10000}

    Returns: "Possible"

  24. {1, 10, 100, 1000, 10000, 20000}

    Returns: "Possible"

  25. {1, 5, 25, 100, 400, 2800, 19600}

    Returns: "Possible"

  26. {1, 3, 18, 108, 540, 2700, 18900}

    Returns: "Possible"

  27. {1, 2, 14, 98, 686, 4802, 19208}

    Returns: "Possible"

  28. {1, 4, 16, 80, 400, 2800, 19600}

    Returns: "Possible"

  29. {1, 2, 12, 72, 432, 2592, 18144}

    Returns: "Possible"

  30. {1, 2, 8, 56, 392, 2352, 16464}

    Returns: "Possible"

  31. {1, 4, 20, 100, 400, 2800, 19600}

    Returns: "Possible"

  32. {1, 2, 6, 24, 120, 720, 5040}

    Returns: "Possible"

  33. {1, 2, 6, 12, 36, 72, 216, 648, 1296, 2592, 7776, 15552}

    Returns: "Impossible"

  34. {1, 100, 20000}

    Returns: "Possible"

  35. {1, 2, 10000, 20000}

    Returns: "Impossible"

  36. {1, 3, 6561, 19683}

    Returns: "Possible"

  37. {1, 3, 9, 6561, 19683}

    Returns: "Impossible"

  38. {1, 3, 2187, 6561, 19683}

    Returns: "Impossible"

  39. {1, 23, 966, 11592}

    Returns: "Possible"

  40. {1, 1000, 2000, 4000, 8000, 16000}

    Returns: "Impossible"

  41. {1, 5000, 10000, 20000}

    Returns: "Impossible"

  42. {1, 2000, 10000, 20000}

    Returns: "Possible"

  43. {1, 19999}

    Returns: "Possible"

  44. {1, 10007}

    Returns: "Possible"

  45. {1, 101, 10201}

    Returns: "Possible"

  46. {1, 99, 9801}

    Returns: "Possible"

  47. {1, 49, 2401}

    Returns: "Possible"

  48. {1, 99, 9801, 19602}

    Returns: "Possible"

  49. {1, 4, 24, 144, 432, 2160, 12960}

    Returns: "Impossible"

  50. {1, 4, 24, 144, 432, 2160, 15120}

    Returns: "Possible"

  51. {1, 3, 9, 36, 144}

    Returns: "Impossible"

  52. {1, 5, 10, 40, 200, 1000}

    Returns: "Impossible"

  53. {1, 2, 6, 30, 210, 2310}

    Returns: "Possible"

  54. {1, 4, 8, 32, 64, 256, 512, 2048, 4096, 16384}

    Returns: "Impossible"

  55. {1, 3, 9, 1107, 4428}

    Returns: "Possible"

  56. {1, 3, 9, 45, 405, 1215}

    Returns: "Impossible"

  57. {1, 3, 9, 27, 621, 19872}

    Returns: "Impossible"

  58. {1, 2, 4, 8, 16}

    Returns: "Impossible"

  59. {1, 7, 42, 210, 840, 2520, 5040}

    Returns: "Possible"

  60. {1, 7, 42, 210, 840, 2520, 17640}

    Returns: "Possible"

  61. {1, 7, 42, 210, 840, 2520, 10080}

    Returns: "Possible"

  62. {1, 7, 42, 210, 420, 1260, 5040, 15120}

    Returns: "Impossible"

  63. {1, 4, 24, 48, 144, 720, 4320}

    Returns: "Impossible"

  64. {1, 5, 25, 100, 500, 3500, 17500}

    Returns: "Impossible"

  65. {1, 6, 42, 168, 672, 2688, 10752}

    Returns: "Impossible"

  66. {1, 10, 30, 300, 900, 9000, 18000 }

    Returns: "Impossible"

  67. {1, 7, 21, 105, 630, 3150, 18900 }

    Returns: "Possible"

  68. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384 }

    Returns: "Impossible"

  69. {1, 3 }

    Returns: "Possible"

  70. {1, 3, 9, 27 }

    Returns: "Impossible"

  71. {1, 4 }

    Returns: "Possible"

  72. {1, 2, 8 }

    Returns: "Possible"

  73. {1, 2000 }

    Returns: "Possible"

  74. {1, 2, 6, 24, 120 }

    Returns: "Possible"

  75. {1, 5, 25 }

    Returns: "Possible"

  76. {1, 3, 6, 12, 24, 48 }

    Returns: "Impossible"

  77. {1, 2 }

    Returns: "Possible"

  78. {1, 7, 49, 343 }

    Returns: "Possible"

  79. {1, 2, 4 }

    Returns: "Impossible"

  80. {1, 5, 25, 125, 625, 3125 }

    Returns: "Impossible"

  81. {1, 2, 10 }

    Returns: "Possible"

  82. {1, 4, 8, 64 }

    Returns: "Possible"

  83. {1, 4, 32, 64 }

    Returns: "Possible"

  84. {1, 10, 30, 60 }

    Returns: "Possible"

  85. {1, 2, 6, 24, 120, 720, 5040 }

    Returns: "Possible"

  86. {1, 20, 4000 }

    Returns: "Possible"

  87. {1, 3, 9, 27, 81 }

    Returns: "Impossible"

  88. {1, 4, 16 }

    Returns: "Possible"

  89. {1, 4, 20, 60, 180, 5760 }

    Returns: "Possible"

  90. {1, 5, 15, 75 }

    Returns: "Possible"

  91. {1, 10, 100, 1000, 10000 }

    Returns: "Possible"

  92. {1, 5, 10 }

    Returns: "Possible"

  93. {1, 2, 6, 12 }

    Returns: "Impossible"

  94. {1, 3, 9 }

    Returns: "Possible"

  95. {1, 10, 50 }

    Returns: "Possible"

  96. {1, 10, 100, 1000 }

    Returns: "Possible"

  97. {1, 3, 6 }

    Returns: "Possible"

  98. {1, 2, 6 }

    Returns: "Possible"

  99. {1, 2, 6, 18 }

    Returns: "Impossible"

  100. {1, 5, 15, 90 }

    Returns: "Possible"

  101. {1, 5, 25, 125, 625 }

    Returns: "Possible"

  102. {1 }

    Returns: "Possible"

  103. {1, 7, 21, 105, 420, 2100, 12600 }

    Returns: "Possible"

  104. {1, 2, 10, 40, 200, 1000, 4000, 20000 }

    Returns: "Impossible"

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: