Alchemy

2018 TCO Fun 3B · 2018-04-20 · by misof

2018 TCO Fun 3B · 2018-04-20 · by misof · Dynamic Programming, Greedy

Show categories

Class Name: Alchemy

Return Type: String

Method Name: leadToGold

Arg Types: (vector<int>, vector<int>, long long)

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.

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.

{0}
{0}
0
Returns: "Possible"

{0}
{0}
1
Returns: "Impossible"

{1}
{0}
0
Returns: "Impossible"

10)

{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.

11)

{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.

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

Coding Area

Language: C++17 · define a public class Alchemy with a public method string leadToGold(vector<int> leadOutput, vector<int> goldOutput, long long goal) · 99 test cases · 2 s / 256 MB per case