Alchemy | Topcoder Archive

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}
```
```
{0,1,2}
```
```
47
```
```
Returns: "Impossible"
```
Reaching the goal is impossible because we cannot get completely rid of lead.
```
{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,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.
```
{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.

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.