Statistics

Problem Statement for "Alchemy"

Problem Statement

You managed to achieve one of the main goals of alchemists: the transmutation of lead into gold. More precisely, you have discovered a collection of experiments. Each experiment starts with exactly one lead coin and ends with some (possibly zero) lead coins and some (possibly zero) gold coins. You may perform each experiment arbitrarily many times, as long as you have at least one lead coin to start with.

You are given the int[]s leadOutput and goldOutput. For each valid i, experiment i produces leadOutput[i] lead coins and goldOutput[i] gold coins. You are also given the long goal. Suppose you start with exactly one lead coin. Is it possible to reach a state with exactly goal gold coins and no lead coins at all? Return "Possible" or "Impossible" accordingly.

Definition

Class:
Alchemy
Method:
leadToGold
Parameters:
int[], int[], long
Returns:
String
Method signature:
String leadToGold(int[] leadOutput, int[] goldOutput, long goal)
(be sure your method is public)

Constraints

  • leadOutput will contain between 1 and 50 elements, inclusive.
  • goldOutput will contain the same number of elements as leadOutput.
  • Each element of leadOutput and goldOutput will be between 0 and 100, inclusive.
  • goal will be between 0 and 10^18, inclusive.

Examples

  1. {1,1,1}

    {0,1,2}

    47

    Returns: "Impossible"

    Reaching the goal is impossible because we cannot get completely rid of lead.

  2. {4,0}

    {1,3}

    23

    Returns: "Possible"

    One possible sequence of actions: Perform experiment 0. We now have 4 lead coins and 1 gold coin. Perform experiment 0 again. This consumes one of the 4 lead coins and then produces 4 new lead coins and 1 new gold coin. Thus, we now have a total of 7 lead coins and 2 gold coins. Seven times perform experiment 1, each time turning one of the lead coins into three gold coins.

  3. {0}

    {0}

    0

    Returns: "Possible"

  4. {0}

    {0}

    1

    Returns: "Impossible"

  5. {1}

    {0}

    0

    Returns: "Impossible"

  6. {2,3,4,0}

    {0,0,0,0}

    0

    Returns: "Possible"

  7. {2,3,4,5,6,0}

    {0,0,10,20,47,0}

    9

    Returns: "Impossible"

  8. {2,3,4,5,6,0}

    {0,0,10,20,47,0}

    104

    Returns: "Possible"

  9. {0,100,100}

    {100,100,99}

    99970101

    Returns: "Impossible"

  10. {0,100,100}

    {100,100,98}

    999999999999999999

    Returns: "Impossible"

  11. {3,0,0}

    {0,5,7}

    9876543210

    Returns: "Impossible"

    We have three experiments that turn one lead coin into 3 lead coins, 5 gold coins, and 7 gold coins, respectively. Quite obviously we won't be able to end with 9,876,543,210 gold coins, as the total number of coins remains odd after each experiment.

  12. {3,0,0}

    {0,5,7}

    123456789

    Returns: "Possible"

    On the other hand, we can easily turn the initial one lead coin into 123,456,789 gold coins.

  13. {3,2,1,0,7,0,1}

    {5,15,4,9,0,7,0}

    1234567

    Returns: "Possible"

  14. {3,2,1,0,7,0,1}

    {5,15,4,9,0,7,0}

    24

    Returns: "Impossible"

  15. {100, 98, 96, 94, 92, 90, 88, 86, 84, 82, 80, 78, 76, 74, 72, 70, 68, 66, 64, 62, 60, 59, 58, 57, 56, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76}

    4355

    Returns: "Impossible"

  16. {1,0}

    {0,47}

    47

    Returns: "Possible"

  17. {1,0}

    {0,47}

    94

    Returns: "Impossible"

  18. {1,0}

    {0,47}

    0

    Returns: "Impossible"

  19. { 90, 4, 0 }

    { 9, 75, 30 }

    999999999998350100

    Returns: "Impossible"

  20. { 90, 4, 0 }

    { 9, 75, 30 }

    999999999998350176

    Returns: "Possible"

  21. { 9, 0 }

    { 38, 54 }

    999999999995300100

    Returns: "Impossible"

  22. { 9, 0 }

    { 38, 54 }

    999999999995300141

    Returns: "Impossible"

  23. { 23, 0 }

    { 35, 89 }

    999999999980070100

    Returns: "Impossible"

  24. { 23, 0 }

    { 35, 89 }

    999999999980070149

    Returns: "Impossible"

  25. { 83, 62, 0 }

    { 96, 87, 31 }

    999999999980220098

    Returns: "Impossible"

  26. { 83, 62, 0 }

    { 96, 87, 31 }

    999999999980220192

    Returns: "Impossible"

  27. { 75, 99, 0 }

    { 7, 4, 95 }

    65526362

    Returns: "Impossible"

  28. { 75, 99, 0 }

    { 7, 4, 95 }

    65526444

    Returns: "Possible"

  29. { 65, 0, 84, 70 }

    { 62, 35, 65, 38 }

    258664

    Returns: "Impossible"

  30. { 65, 0, 84, 70 }

    { 62, 35, 65, 38 }

    258725

    Returns: "Possible"

  31. { 57, 0, 89 }

    { 67, 82, 80 }

    999999999953410100

    Returns: "Impossible"

  32. { 57, 0, 89 }

    { 67, 82, 80 }

    999999999953410192

    Returns: "Possible"

  33. { 97, 0, 69 }

    { 36, 71, 54 }

    999999999951180098

    Returns: "Impossible"

  34. { 97, 0, 69 }

    { 36, 71, 54 }

    999999999951180152

    Returns: "Impossible"

  35. { 54, 0, 84 }

    { 22, 76, 76 }

    999999999959500100

    Returns: "Impossible"

  36. { 54, 0, 84 }

    { 22, 76, 76 }

    999999999959500115

    Returns: "Impossible"

  37. { 63, 73, 0 }

    { 0, 1, 11 }

    539362

    Returns: "Impossible"

  38. { 63, 73, 0 }

    { 0, 1, 11 }

    539372

    Returns: "Possible"

  39. { 0, 95, 65 }

    { 27, 43, 69 }

    4633706

    Returns: "Impossible"

  40. { 0, 95, 65 }

    { 27, 43, 69 }

    4633721

    Returns: "Possible"

  41. { 79, 0, 53, 95, 83, 68, 97 }

    { 69, 45, 64, 90, 83, 33, 40 }

    55630

    Returns: "Impossible"

  42. { 79, 0, 53, 95, 83, 68, 97 }

    { 69, 45, 64, 90, 83, 33, 40 }

    55688

    Returns: "Possible"

  43. { 59, 59, 73, 67, 83, 0, 58, 90, 71, 55, 57, 73, 86, 53, 0, 0, 95 }

    { 37, 92, 22, 70, 89, 12, 32, 13, 8, 43, 2, 62, 72, 53, 70, 35, 33 }

    995

    Returns: "Impossible"

  44. { 59, 59, 73, 67, 83, 0, 58, 90, 71, 55, 57, 73, 86, 53, 0, 0, 95 }

    { 37, 92, 22, 70, 89, 12, 32, 13, 8, 43, 2, 62, 72, 53, 70, 35, 33 }

    1016

    Returns: "Possible"

  45. { 73, 78, 0 }

    { 52, 59, 55 }

    999999999959880098

    Returns: "Impossible"

  46. { 73, 78, 0 }

    { 52, 59, 55 }

    999999999959880099

    Returns: "Possible"

  47. { 70, 0, 55, 86, 90, 0, 52 }

    { 41, 27, 21, 29, 26, 11, 32 }

    2167

    Returns: "Impossible"

  48. { 70, 0, 55, 86, 90, 0, 52 }

    { 41, 27, 21, 29, 26, 11, 32 }

    2224

    Returns: "Possible"

  49. { 51, 82, 51, 63, 78, 56, 50, 61, 79, 56, 98, 78, 59, 0, 90, 74, 0, 90, 68, 0, 85, 0, 91, 55, 0, 76, 70, 0, 81, 71, 96, 64, 58, 73, 60, 75, 98, 0, 72, 0, 55, 98, 0, 56, 0, 0, 77 }

    { 56, 83, 35, 97, 89, 25, 99, 36, 8, 68, 87, 91, 74, 87, 47, 55, 75, 57, 73, 74, 78, 36, 52, 81, 33, 6, 91, 81, 16, 96, 99, 99, 86, 15, 7, 52, 19, 94, 27, 64, 22, 79, 32, 44, 93, 44, 88 }

    1666

    Returns: "Impossible"

  50. { 51, 82, 51, 63, 78, 56, 50, 61, 79, 56, 98, 78, 59, 0, 90, 74, 0, 90, 68, 0, 85, 0, 91, 55, 0, 76, 70, 0, 81, 71, 96, 64, 58, 73, 60, 75, 98, 0, 72, 0, 55, 98, 0, 56, 0, 0, 77 }

    { 56, 83, 35, 97, 89, 25, 99, 36, 8, 68, 87, 91, 74, 87, 47, 55, 75, 57, 73, 74, 78, 36, 52, 81, 33, 6, 91, 81, 16, 96, 99, 99, 86, 15, 7, 52, 19, 94, 27, 64, 22, 79, 32, 44, 93, 44, 88 }

    1682

    Returns: "Possible"

  51. { 65, 80, 98, 94, 59, 0, 0 }

    { 35, 54, 32, 18, 79, 91, 38 }

    15575

    Returns: "Impossible"

  52. { 65, 80, 98, 94, 59, 0, 0 }

    { 35, 54, 32, 18, 79, 91, 38 }

    15659

    Returns: "Possible"

  53. { 51, 0, 86 }

    { 9, 1, 55 }

    8062

    Returns: "Impossible"

  54. { 51, 0, 86 }

    { 9, 1, 55 }

    8127

    Returns: "Possible"

  55. { 61, 0, 19, 0, 50, 0, 89, 0, 31, 0, 3, 0, 92, 0, 57, 0, 5, 0, 15, 0, 50, 0, 34, 0, 17, 0, 87 }

    { 80, 30, 30, 35, 100, 30, 90, 15, 15, 45, 70, 85, 10, 5, 10, 50, 55, 65, 45, 0, 65, 25, 70, 15, 10, 70, 75 }

    999999999999999993

    Returns: "Impossible"

  56. { 61, 0, 19, 0, 50, 0, 89, 0, 31, 0, 3, 0, 92, 0, 57, 0, 5, 0, 15, 0, 50, 0, 34, 0, 17, 0, 87 }

    { 80, 30, 30, 35, 100, 30, 90, 15, 15, 45, 70, 85, 10, 5, 10, 50, 55, 65, 45, 0, 65, 25, 70, 15, 10, 70, 75 }

    999999999999999840

    Returns: "Possible"

  57. { 15, 0 }

    { 60, 96 }

    999999999999999992

    Returns: "Impossible"

  58. { 15, 0 }

    { 60, 96 }

    999999999999999954

    Returns: "Impossible"

  59. { 4, 0, 26 }

    { 98, 49, 84 }

    999999999999999993

    Returns: "Impossible"

  60. { 4, 0, 26 }

    { 98, 49, 84 }

    999999999999999950

    Returns: "Possible"

  61. { 100 }

    { 57 }

    999999999999999996

    Returns: "Impossible"

  62. { 100 }

    { 57 }

    999999999999999952

    Returns: "Impossible"

  63. { 29, 0, 66, 0 }

    { 36, 75, 75, 3 }

    999999999999999989

    Returns: "Impossible"

  64. { 29, 0, 66, 0 }

    { 36, 75, 75, 3 }

    999999999999999987

    Returns: "Possible"

  65. { 48, 0, 73 }

    { 60, 86, 45 }

    999999999999999982

    Returns: "Impossible"

  66. { 48, 0, 73 }

    { 60, 86, 45 }

    999999999999999812

    Returns: "Possible"

  67. { 51, 0, 2, 0 }

    { 10, 1, 49, 11 }

    999999999999999982

    Returns: "Impossible"

  68. { 51, 0, 2, 0 }

    { 10, 1, 49, 11 }

    999999999999999981

    Returns: "Possible"

  69. { 70, 0, 86, 0, 89, 0, 98, 0, 5, 0, 20, 0, 81, 0, 23, 0, 48, 0, 26, 0, 33, 0, 77, 0, 68, 0, 19, 0, 86, 0, 64, 0, 58, 0, 46, 0, 93, 0, 95, 0, 70, 0, 34, 0, 25, 0, 64 }

    { 80, 66, 38, 16, 14, 64, 64, 96, 4, 10, 70, 88, 16, 64, 96, 44, 72, 82, 44, 60, 42, 54, 0, 50, 24, 30, 92, 68, 8, 98, 18, 58, 68, 76, 10, 76, 78, 80, 32, 14, 90, 42, 28, 38, 84, 82, 18 }

    999999999999999993

    Returns: "Impossible"

  70. { 70, 0, 86, 0, 89, 0, 98, 0, 5, 0, 20, 0, 81, 0, 23, 0, 48, 0, 26, 0, 33, 0, 77, 0, 68, 0, 19, 0, 86, 0, 64, 0, 58, 0, 46, 0, 93, 0, 95, 0, 70, 0, 34, 0, 25, 0, 64 }

    { 80, 66, 38, 16, 14, 64, 64, 96, 4, 10, 70, 88, 16, 64, 96, 44, 72, 82, 44, 60, 42, 54, 0, 50, 24, 30, 92, 68, 8, 98, 18, 58, 68, 76, 10, 76, 78, 80, 32, 14, 90, 42, 28, 38, 84, 82, 18 }

    999999999999999966

    Returns: "Possible"

  71. { 61, 0, 70, 0, 43, 0, 28, 0, 57, 0, 17, 0, 41, 0, 98, 0, 55, 0, 96, 0, 9, 0, 20, 0, 21, 0, 85, 0, 6, 0, 2, 0, 23, 0, 99, 0, 29, 0, 96, 0, 24, 0, 13, 0, 96, 0, 84, 0, 45, 0 }

    { 90, 60, 24, 96, 54, 42, 84, 24, 54, 96, 36, 36, 42, 54, 66, 78, 78, 12, 0, 96, 48, 60, 72, 42, 96, 48, 60, 66, 60, 90, 84, 78, 18, 42, 12, 6, 54, 36, 90, 6, 0, 54, 54, 18, 78, 12, 96, 30, 48, 84 }

    999999999999999975

    Returns: "Impossible"

  72. { 61, 0, 70, 0, 43, 0, 28, 0, 57, 0, 17, 0, 41, 0, 98, 0, 55, 0, 96, 0, 9, 0, 20, 0, 21, 0, 85, 0, 6, 0, 2, 0, 23, 0, 99, 0, 29, 0, 96, 0, 24, 0, 13, 0, 96, 0, 84, 0, 45, 0 }

    { 90, 60, 24, 96, 54, 42, 84, 24, 54, 96, 36, 36, 42, 54, 66, 78, 78, 12, 0, 96, 48, 60, 72, 42, 96, 48, 60, 66, 60, 90, 84, 78, 18, 42, 12, 6, 54, 36, 90, 6, 0, 54, 54, 18, 78, 12, 96, 30, 48, 84 }

    999999999999999966

    Returns: "Possible"

  73. { 99, 0 }

    { 4, 14 }

    999999999999999964

    Returns: "Impossible"

  74. { 99, 0 }

    { 4, 14 }

    999999999999999950

    Returns: "Impossible"

  75. { 58, 0, 29, 0, 22, 0, 54, 0, 32, 0, 70, 0, 66, 0, 79, 0, 5, 0, 49, 0, 89, 0, 75, 0, 15, 0, 69 }

    { 31, 67, 29, 12, 98, 47, 34, 97, 23, 47, 57, 82, 0, 67, 49, 72, 52, 47, 89, 62, 74, 12, 52, 2, 72, 82, 89 }

    999999999999999983

    Returns: "Impossible"

  76. { 58, 0, 29, 0, 22, 0, 54, 0, 32, 0, 70, 0, 66, 0, 79, 0, 5, 0, 49, 0, 89, 0, 75, 0, 15, 0, 69 }

    { 31, 67, 29, 12, 98, 47, 34, 97, 23, 47, 57, 82, 0, 67, 49, 72, 52, 47, 89, 62, 74, 12, 52, 2, 72, 82, 89 }

    999999999999999957

    Returns: "Possible"

  77. { 92, 0, 5, 0, 77, 0, 4 }

    { 84, 47, 36, 68, 96, 12, 6 }

    999999999999999989

    Returns: "Impossible"

  78. { 92, 0, 5, 0, 77, 0, 4 }

    { 84, 47, 36, 68, 96, 12, 6 }

    999999999999999934

    Returns: "Possible"

  79. { 29, 0, 60, 0 }

    { 28, 94, 58, 90 }

    999999999999999987

    Returns: "Impossible"

  80. { 29, 0, 60, 0 }

    { 28, 94, 58, 90 }

    999999999999999958

    Returns: "Possible"

  81. { 46 }

    { 35 }

    999999999999999984

    Returns: "Impossible"

  82. { 46 }

    { 35 }

    999999999999999937

    Returns: "Impossible"

  83. { 38, 0, 79 }

    { 1, 47, 6 }

    999999999999999985

    Returns: "Impossible"

  84. { 38, 0, 79 }

    { 1, 47, 6 }

    999999999999999943

    Returns: "Impossible"

  85. { 20, 0, 34, 0, 64, 0, 72, 0, 42, 0, 49, 0, 8, 0, 25, 0, 88, 0, 35, 0, 16, 0, 17, 0, 94, 0, 19 }

    { 73, 91, 19, 65, 25, 9, 53, 49, 97, 77, 44, 53, 35, 89, 26, 23, 1, 61, 4, 31, 65, 93, 8, 11, 65, 93, 64 }

    999999999999999982

    Returns: "Impossible"

  86. { 20, 0, 34, 0, 64, 0, 72, 0, 42, 0, 49, 0, 8, 0, 25, 0, 88, 0, 35, 0, 16, 0, 17, 0, 94, 0, 19 }

    { 73, 91, 19, 65, 25, 9, 53, 49, 97, 77, 44, 53, 35, 89, 26, 23, 1, 61, 4, 31, 65, 93, 8, 11, 65, 93, 64 }

    999999999999999977

    Returns: "Possible"

  87. { 76, 0 }

    { 19, 83 }

    999999999999999988

    Returns: "Impossible"

  88. { 76, 0 }

    { 19, 83 }

    999999999999999971

    Returns: "Impossible"

  89. { 17, 0 }

    { 40, 47 }

    999999999999999985

    Returns: "Impossible"

  90. { 17, 0 }

    { 40, 47 }

    999999999999999963

    Returns: "Impossible"

  91. { 77, 0, 57, 0, 28, 0, 15 }

    { 30, 80, 100, 75, 60, 0, 100 }

    999999999999999994

    Returns: "Impossible"

  92. { 77, 0, 57, 0, 28, 0, 15 }

    { 30, 80, 100, 75, 60, 0, 100 }

    999999999999999990

    Returns: "Possible"

  93. { 45 }

    { 12 }

    999999999999999988

    Returns: "Impossible"

  94. { 45 }

    { 12 }

    999999999999999922

    Returns: "Impossible"

  95. {0 }

    {0 }

    0

    Returns: "Possible"

  96. {1 }

    {1 }

    0

    Returns: "Impossible"

  97. {0, 1, 1 }

    {0, 100, 99 }

    50

    Returns: "Impossible"

  98. {1, 0 }

    {0, 1 }

    1

    Returns: "Possible"

  99. {100, 0, 0 }

    {100, 99, 100 }

    9901000099009

    Returns: "Possible"

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: