We periodically include chemistry-themed problems in Code Jam, and Round 2
had three! The two parts of *New Elements* could be solved independently,
but there were some commonalities, so solving one made it perhaps a bit
easier to solve the other. *Contransmutation* was a spiritual successor
to this problem from Round 1B 2018,
and it was similarly challenging. We did take a break from the chemistry lab
to interactively hack a vase contest in *Pottery Lottery*.

This was an uncharacteristically tight round, with the problems having a smaller spread
of difficulties than usual. This was reflected in the full score for each problem being in the
twenties. **mnbvmar** was the first to get a perfect score to claim first place, when there
was a little over an hour left. **ksun48** and **xyz111** followed to
claim second and third. Overall, only 26 contestants managed a perfect score.
Getting even a single point was tough in this round, given it
didn't feature any simple problems, and over 2400 contestants managed to score nonetheless.
Congratulations!

Preliminary results indicate that 32 points and some speed are required to advance to the next round.

After the results have been finalized, the top 1000 contestants will win well-deserved Code Jam 2019 T-shirts, and will advance to Round 3, where 25 tickets to the World Finals await! Are you going to San Francisco?

**Cast**

New Elements, Part 1: Written by Pablo Heiber. Prepared by Jonathan Irvin Gunawan.

Pottery Lottery: Written by Ian Tullis. Prepared by John Dethridge and Pi-Hsun Shih.

New Elements, Part 2: Written by Pablo Heiber. Prepared by Micah Stairs.

Contransmutation: Written by Pablo Heiber. Prepared by Jonathan Irvin Gunawan and Darcy Best.

Solutions and other problem preparation and review by Liang Bai, Darcy Best, Timothy Buzzelli, John Dethridge, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Ray Robinson, Micah Stairs, Ian Tullis, Pi-Hsun Shih, and Adilet Zhaxybay.

Analysis authors:

- New Elements, Part 1: Pablo Heiber and Ian Tullis
- Pottery Lottery: Ian Tullis and Tony Wong
- New Elements, Part 2: Jonathan Irvin Gunawan
- Contransmutation: Ray Robinson and Pablo Heiber

*
The first two paragraphs (not counting this one) of this problem and "New Elements: Part 2"
are identical. The problems can otherwise be solved independently; you do not need to read
or solve one in order to read or solve the other.
*

Muriel is on the path to discovering two new elements that she has named Codium and Jamarium. She has not been able to isolate them yet, but she wants to start investigating some important properties, like their atomic weights, by indirect means. Since Muriel is working with a single isotope of Codium and a single isotope of Jamarium, their atomic weights are strictly positive integers.

Muriel managed to create **N** different molecules, each of which contains one or
more atoms of Codium and one or more atoms of Jamarium, and no other elements.
For each molecule, she knows how many atoms of each element are present in it. The molecular
weight of a molecule is the sum of the atomic weights of all the atoms it contains.

As a first step towards figuring out exact molecular weights for the molecules and atomic weights
for the two elements, Muriel wants to sort the molecules by strictly increasing molecular weight.
To assess the difficulty of that task, she wants to know how many orders are valid
considering only the information she has right now. An ordering of the molecules is considered
valid if there exist values for the atomic weights of Codium and Jamarium such that the ordering is
*strictly* increasing in molecular weight.

To give an example, we represent each molecule by the ordered pair of the number of atoms of Codium and Jamarium it contains. If Muriel has 3 molecules represented by (1, 1), (2, 1) and (1, 2), there are two possible orderings that can be strictly increasing in molecular weight: (1, 1), (1, 2), (2, 1) and (1, 1), (2, 1), (1, 2). The first ordering is valid for any assignment of atomic weights in which Codium is the heaviest of the two elements, and the second is valid for any assignment in which Jamarium is the heaviest. The only case remaining is when both Codium and Jamarium have the same atomic weight, in which case (1, 2) and (2, 1) have the same molecular weight, so no strictly increasing ordering can be produced for that scenario.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
The first line of a test case contains a single integer **N**, the number of molecules. Each
of the next **N** lines describes a different molecule with two integers **C _{i}**
and

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is the total number of valid orderings
as defined above.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **C _{i}** ≤ 10

1 ≤

(

2 ≤ **N** ≤ 6.

2 ≤ **N** ≤ 300.

Sample Input

3 3 1 1 1 2 2 1 4 1 2 2 4 2 1 4 2 3 1 2 1 3 2 3

Sample Output

Case #1: 2 Case #2: 2 Case #3: 1

Sample Case #1 is explained in the statement.

In Sample Case #2, the two valid orderings are (1, 2), (2, 1), (2, 4), (4, 2) and (2, 1), (1, 2), (4, 2), (2, 4). Notice that the ordering (1, 2), (2, 1), (4, 2), (2, 4) is invalid because if (1, 2) is strictly less heavy than (2, 1), then (2, 4), which is exactly twice as heavy as (1, 2), must be strictly less heavy than (4, 2), which is exactly twice as heavy as (2, 1).

The Pottery Palace is going to run a lottery featuring some valuable vases by the artist Cody-Jamal. The lottery works as follows:

- 100 people get to play in the lottery. Each player has a unique number between 1 and 100, and is given a single token with that number.
- There are 20 empty clay vases on a table, numbered 1 through 20. The vases have narrow openings that are large enough to accept a token, but small enough that players cannot look inside to see the contents.
- On the i-th day of the lottery, the player with token number i chooses a vase and puts their token in that vase. Since the vases are all identical (apart from their labels), every player will choose one uniformly at random and independently of all other players' choices.
- On day 100, after player number 100 has inserted their token, the organizers
shake the vases to determine how many tokens are inside each one. If there
is
*exactly*one vase that has fewer tokens than any other vase, then that one is the "winning vase". The organizers then pour out all of the tokens in that vase, and every player whose number is written on one of those poured-out tokens wins a vase! If multiple vases have the same minimal amount of tokens, nobody wins anything.

You have been hired to test the security of the lottery, and you will participate in some trial runs. The company will always assign you the number 100 — that is, you replace player 100.

You have found some ways to tamper with the lottery at night, but security
is tight, so you can only do so much! Specifically, after each of the first
99 days of the lottery, you may do exactly *one* of the following:

- forge a token with the player number of your choice (between 1 and 100, inclusive), and add it to a vase of your choice. You are a very good forger: if there is a winning vase, any forged tokens in that vase will cause the players with those numbers to win (with one exception; see below).
- use a special camera to see the numbers on all of the tokens in one vase of your choice

You may perform different actions on different nights, and you may choose dynamically: you do not need to decide on all of your actions in advance.

On the 100th day, it is your turn to insert your token into a vase of your choice (you do not need to choose uniformly at random). You cannot perform any other actions on that day.

You know that if there is a winning vase with more than one token for the same player, it will be obvious that cheating has occurred and nobody will win. However, it does not matter if other vases contain more than one token for the same player because the organizers never see those tokens.

Your goal is to be a winner in at least 90% of the test cases.

This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.

Initially, your program should read a single line containing a single integer
**T** indicating the number of test cases. Then, you need to process
**T** test cases.

At the start of a test case, the judge outputs one line with one integer: the number of the current day. (The judge starts on day 1, and on the i-th day, it prints i.) After your program reads the integer, it should write a line containing two integers V and P, with 1 ≤ V ≤ 20, and 0 ≤ P ≤ 100. The judge will interpret these as follows:

- If 1 ≤ P ≤ 100, you put a token for player P in vase V. The judge does not write anything back as a response.
- If P = 0, you inspect the contents of vase V. The judge writes one line
containing integers. The first integer is
**N**, the number of tokens in vase V, and then there are**N**more integers: the player numbers on each of the tokens, in non-decreasing order.

Notice that on turn 100, you must put your own token in, so P must be 100.

Remember that on the i-th day, for 1 ≤ i ≤ 99, the judge simulates the action of the i-th player, as described in the statement. This happens before your own action on that day.

After you send your move for turn 100, your program should terminate if it
was the last test case; otherwise, it should start reading data for the next
test case. (Notice that the judge does not tell you whether you got each case
correct or incorrect.) The judge will only check whether you have enough
correct answers after you have attempted all **T** test cases, so you
should not stop early! For example, if you answer the first 225 out of 250
cases correctly and then exit, or provide malformed input, your solution will
not be considered correct.

If your program outputs something illegal (e.g., gives an invalid value for P
or V, or tries to inspect a vase on turn 100), the judge will send
one line containing `-1`

to your input stream, and it will not
send any other output after that. If your program continues to wait for the
judge after receiving `-1`

, your program will time out, resulting
in a Time Limit Exceeded error. Notice that it is your responsibility to have
your program exit in time to receive a Wrong Answer judgment instead of a
Time Limit Exceeded error. As usual, if the total memory is exceeded, or your
program gets a runtime error, you will receive the appropriate judgment.

**T** = 250.

Time limit (for the entire test set): 40 seconds.

Memory limit: 1GB.

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.

Instructions for the testing tool are included in comments within the tool.
We encourage you to add your own test cases. Please be advised that although
the testing tool is intended to simulate the judging system, it is **NOT**
the real judging system and might behave differently. If your code passes the
testing tool but fails the real judge, please check the
Coding section
of the FAQ to make sure that you are using the same compiler as us.

t = readline_int() // reads 250 into t curr_day = readline_int() // reads 1 (day 1) printline 8 100 to stdout // puts a token for player 100 into vase 8 flush stdout curr_day = readline_int() // reads 2 (day 2) printline 8 99 to stdout // puts a token for player 99 into vase 8 flush stdout curr_day = readline_int() // reads 3 (day 3) printline 8 100 to stdout // puts a token for player 100 into vase 8 flush stdout curr_day = readline_int() // reads 4 (day 4) printline 20 7 to stdout // puts a token for player 7 into vase 20 flush stdout curr_day = readline_int() // reads 5 (day 5) printline 8 0 to stdout // inspects vase 8 flush stdout tokens = readline_int_list() // reads 5 2 5 99 100 100 (players 2 and 5 // happen to have chosen vase 8) curr_day = readline_int() // reads 6 (day 6) printline 8 101 to stdout // tries to add a token with a bad player number flush stdout curr_day = readline_int() // reads -1 (judge has decided our solution is // incorrect) exit // exits to avoid an ambiguous TLE error

*
The first two paragraphs (not counting this one) of this problem and "New Elements: Part 1"
are identical. The problems can otherwise be solved independently; you do not need to read
or solve one in order to read or solve the other.
*

Muriel is on the path to discovering two new elements that she has named Codium and Jamarium. She has not been able to isolate them yet, but she wants to start investigating some important properties, like their atomic weights, by indirect means. Since Muriel is working with a single isotope of Codium and a single isotope of Jamarium, their atomic weights are strictly positive integers.

Muriel managed to create **N** different molecules, each of which contains one or
more atoms of Codium and one or more atoms of Jamarium, and no other elements.
For each molecule, she knows how many atoms of each element are present in it. The molecular
weight of a molecule is the sum of the atomic weights of all the atoms it contains.

As a first step, Muriel sorted the molecules by strictly increasing molecular weight. Now she wants to find out possible integer values for the atomic weights of both Codium and Jamarium that are consistent with the ordering. Since she is aware there could be many consistent pairs of values, she wants one that minimizes the atomic weight of Codium. If there are multiple pairs in which Codium's atomic weight is minimum, she wants the one in which Jamarium's atomic weight is minimum.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
The first line of a test case contains a single integer **N**, the number of molecules. Each
of the next **N** lines describes a different molecule with two integers **C _{i}**
and

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1), and `y`

is `IMPOSSIBLE`

(in uppercase) if there is
no pair of integer atomic weights that would make the order of the molecules strictly
increasing in molecular weight. Otherwise, `y`

should be two integers
`c j`

where c is the atomic weight of Codium and j is the atomic weight of
Jamarium, chosen according to the rules above.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

2 ≤ **N** ≤ 10.

(**C _{i}**,

1 ≤ **C _{i}** ≤ 100, for all i.

1 ≤

1 ≤ **C _{i}** ≤ 10

1 ≤

Sample Input

3 3 1 1 1 2 2 1 4 1 2 2 1 4 2 2 4 3 1 2 1 3 2 3

Sample Output

Case #1: 2 1 Case #2: IMPOSSIBLE Case #3: 1 1

In Sample Case #1, the difference between the last two molecules is having an extra atom of one element or the other. Given that the one having the extra Codium is heavier overall, we conclude that Codium must be heavier than Jamarium. The values 2 and 1 for the atomic weights of Codium and Jamarium make the molecular weights 1 × 2 + 1 × 1 = 3, 1 × 2 + 2 × 1 = 4, and 2 × 2 + 1 × 1 = 5, respecting the strict ordering. Since Codium is heavier than Jamarium in this case, 2 is Codium's minimum atomic weight, and 1 is of course Jamarium's minimum atomic weight.

Let a, b, c and d be the molecular weights of the molecules in Sample Case #2, in increasing order of molecular weight. By their atom contents, d = 2 × a and c = 2 × b. It follows from a < b that d = 2 × a < 2 × b = c, which means there is no pair of values for the atomic weights that would make the ordering strictly increasing.

In Sample Case #3, notice that the molecules happen to be sorted in strictly increasing order of total number of atoms. Therefore, assigning both elements an atomic weight of 1 makes the atomic weights be sorted in strictly increasing order.

Last year, we asked you to help us convert expensive metals into lead. (You do not need to know anything about the previous problem to solve this one.) But your country's leader is still greedy for more lead!

There are **M** metals known in the world; lead is metal number 1 on your
periodic table. Your country's leader has asked you to use the metals in the
treasury to make as much lead as possible.

For each metal (including lead), you know exactly one formula that lets you destroy one gram of that metal and create one gram each of two metals. (It is best not to think too much about the principle of mass conservation!) Note that it is possible that the formula for the i-th metal might produce the i-th metal as one of the products. The formulas do not work with partial grams. However, you can use each formula as often as you would like (or not at all), as long as you have a gram of the required ingredient.

If you make optimal choices, what is the largest number of grams of lead you
can end up with, or is it unbounded? If it is not unbounded: since the output
can be a really big number, we only ask you to output the remainder of
dividing the result by the prime 10^{9}+7 (that is, 1000000007).

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each begins with one line with an integer
**M**: the number of metals known in the world. Then there are **M**
more lines with two integers **R _{i1}** and

For each test case, output one line containing `Case #x: y`

where
`x`

is the test case number (starting from 1). If there is no
bound on the maximum amount of lead that can be produced, `y`

must be `UNBOUNDED`

. Otherwise, `y`

must be
the largest amount of lead, in grams, that you can end up with, modulo the
prime 10^{9}+7 (that is, 1000000007).

1 ≤ **R _{i1}** <

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

2 ≤ **M** ≤ 10.

0 ≤ **G _{i}** ≤ 10, for all i.

1 ≤ **T** ≤ 100.

2 ≤ **M** ≤ 100.

0 ≤ **G _{i}** ≤ 10

1 ≤ **T** ≤ 5.

2 ≤ **M** ≤ 10^{5}.

0 ≤ **G _{i}** ≤ 10

Sample Input

3 2 1 2 1 2 1 0 2 1 2 1 2 0 0 4 2 4 3 4 2 4 2 3 10 10 10 10

Sample Output

Case #1: UNBOUNDED Case #2: 0 Case #3: 10

In Sample Case #1, you have one formula that turns 1 gram of lead into 1 gram of lead and 1 gram of the second metal, and another formula that turns 1 gram of the second metal into 1 gram of lead and 1 gram of the second metal. You can alternate between these formulas to produce as much of both metals as you want.

Sample Case #2 has the same formulas as Sample Case #1, but you have no metals to start with!

In Sample Case #3, none of the formulas help you produce more lead, so you cannot end up with more lead than you started with.

In the first test set, there can be at most six molecules, so we can easily
check all 6! = 720 possible orderings of them. The nontrivial part is
figuring out how to check an ordering. We cannot check all possible atomic
weights, since they can be arbitrary integers, and those integers might need
to be quite large (since the **C _{i}** and

For each ordering of molecules, we must determine whether there is at least
one valid pair of atomic weights w_{C} and w_{J} for Codium
and Jamarium, respectively, such that the molecules are in strictly
increasing order of molecular weight. We do not need to find particular
values; we only need to show existence or non-existence.

Let k = w_{J} / w_{C}. Then, if w_{C} and
w_{J} are valid for our ordering, we can substitute
w_{J} = k × w_{C} in the requirement
for any pair of molecules (**C _{a}**,

**C _{a}** × w

If **J _{a}** =

(**C _{a}** -

k < (

So, we can start by assuming that k can take on any value in an infinite range. Then, whenever we check a pair of molecules, we get a new (non-inclusive) upper or lower bound on the value of k, and we can update one end of the range accordingly. If we find that constraints force the range to be empty (e.g., because the upper end is forced to be smaller than the lower end), then no valid set of atomic weights exists. Otherwise, at least one does. Notice that even though the atomic weights of Codium and Jamarium must both be integers, any rational value of k corresponds to some pair of integers.

This is a quick set of checks, and it is even quicker if we realize that we only need to check consecutive pairs of molecules. However, as in any problem involving comparisons of fractional quantities, we must be careful to compute exact values instead of using floating-point approximations.

Considering the solution of Test set 1 in reverse can lead us to a solution for
Test set 2. If we consider two arbitrary molecules with indices a and b, they can
appear in two possible orderings. If one of them is impossible according to the
math above, it means that the other is the ordering of the molecules for every possible
assignment of atomic weights. If that's the case, we can ignore the pair of
molecules (a, b). However, if both orderings are possible, we obtain
a range of valid values for the ratio k of the form
(0, R_{a,b}) for one ordering and a range of the form
(R_{a,b}, +∞) for the other, where
R_{a,b} = |(**C _{a}** -

By the previous paragraph, if we consider a function f from ratios into
orderings, f is a piecewise constant function that is undefined at ratios
R_{a,b} for any pair a, b and is constant in any interval that
doesn't contain any such ratio. Moreover, the image of f over
(0, R_{a,b}) consists of orderings with molecules a and b in one
relative order and the image of f over (R_{a,b}, +∞) consists
of orderings with molecules a and b in the other relative order. Therefore,
no two elements in f's image are the same. The number of elements in f's
image, which is the answer to the problem, is the number of different non-zero
R_{a,b} values, plus 1. Notice that it is possible that
R_{a,b} = R_{c,d} for different molecules a, b, c, d, and
we need to count the number of unique values.

The algorithm to count the number of different values that are equal to
R_{a,b} for some a, b is immediate: try every
pair of molecules, calculate the ratio as explained for the Test set 1 solution
(if there is one), and add it to a set of fractions to discard non-uniques. This algorithm
takes a quadratic number of insertions into a set, which makes it quadratic or barely
above quadratic overall depending on the set implementation that is used.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Our tempting first thought might be: why not just put one of our tokens in each vase? Then we can sit back and just wait to win, no matter which vase gets chosen. Who needs the other 80 days?

The flaw in this reasoning is that if multiple vases are tied for having the fewest tokens, there is no winner. A quick simulation can show us that there is only a unique winner around 57% of the time. So this approach has no hope of passing, and we have to work harder!

It might still seem that we can succeed without inspecting any vases. What if we just choose one vase up front — without loss of generality, we will pick vase #20 — and try to make it the winning vase? Over the course of the first 99 nights, we distribute fake tokens among the other 19 vases, as evenly as possible (to prevent any one of those vases from becoming more of a threat than the others). The labels on these fake tokens do not matter, since we are banking on vase 20 winning. Then, on the 100th night, we place our token in vase 20. Since each of the other 19 vases will be burdened with 5 (or maybe even 6) extra tokens, the odds are good that vase 20 will have the fewest, right?

Unfortunately, those odds aren't so good. Again, we can write a quick simulation to verify that our strategy will only succeed around 53% of the time — it's even worse than the strategy above! The average "burden" that we add to the other vases just isn't large enough compared to the random variation in the number of tokens per vase.

We will need to take advantage of our inspection ability, but when should we use it? There is not much value in inspecting early on in the lottery, since relatively few tokens will have been placed. On the other hand, if we inspect too late, we may not have enough nights left on which to react to whatever information we discover.

We can devise a version of our first approach that also incorporates inspection. In this approach, V and N are parameters that we will have to discover:

- Choose to "give up on" the first V vases. We will assume that none of these will win, and so the labels on the tokens we add to them will not matter. Spend the first N nights sabotaging them (evenly).
- Spend the next 20 turns inspecting every vase, in order.
- Based on the results of our inspections, choose the vase with the fewest tokens (out of the remaining 20-V vases) to be our candidate winning vase.
- On each of the remaining 99 - 20 - N nights, choose a vase (other than our candidate vase) with the smallest number of tokens in our inspection results, and add a token to it. Then, update the inspection results to reflect this.
- On day 100, add our own token to the candidate vase.

We might worry that our inspections are only snapshots in time that grow stale. By the time we inspect vase 20, our estimate for vase 1 is already out-of-date — what if more tokens have been added to it since then? To compare the estimates a little more fairly, we could adjust them by the expected number of tokens that have been added since the night of the estimate (i.e., the number of additional nights, divided by 20). This adjustment will be at most .95, which is less than a single full token, so the adjustments could only possibly be used to break ties among vases with the same number of tokens... and we can get the same effect by just choosing the vase with the highest-numbered ID in the event of a tie.

It is not too hard to simulate this process, so we can try out different values of V and N to see what yields the best results, and find that V = 14, N = 60 works about 95% of the time. That gives us, per the binomial distribution, about a 99.96% chance of solving at least 225 out of 250 cases correctly. Since the problem only has one Visible test set, we should just submit and hope for the best!

If we want to experiment further, there are even better solutions out there! Here is a variant of the above strategy; it succeeds over 98% of the time:

- Days 1-60: Put 4 tokens into each of vases 1-15.
- Days 61-80: Inspect every case. Find the
*two*vases with the smallest number of tokens (breaking ties in favor of higher-numbered vases, as we will throughout this strategy), and designate them as candidates. - Days 81-94: Greedily put a token into the non-candidate vase that has the smallest number of tokens, per our inspection results. Update those results.
- Days 95-96: Inspect the two candidates again and commit to the one with fewer tokens.
- Days 97-99: Sabotage the other candidate.

If we hang onto two candidates, it is less likely that both of them will accumulate a lot of tokens via bad luck during the second sabotage phase. We benefit from delaying our decision point for as long as possible, while still leaving enough time to deal with our runner-up.

Let w_{C} be the atomic weight of Codium and w_{J} be the atomic weight of
Jamarium according to the rules given in the problem statement. Let ΔC_{i} equal
**C**_{i + 1} - **C**_{i} and ΔJ_{i} equal
**J**_{i + 1} - **J**_{i}, for all 1 ≤ i < **N**. As in our
analysis for New Elements, Part 1, we have:

- -ΔC
_{i}/ ΔJ_{i}< w_{J}/ w_{C}, if ΔJ_{i}> 0. - w
_{J}/ w_{C}< -ΔC_{i}/ ΔJ_{i}, if ΔJ_{i}< 0. - -ΔC
_{i}× w_{C}< 0, if ΔJ_{i}= 0.

Therefore, we can get the lower bound and upper bound of w_{J} / w_{C} just by
looking at consecutive indices. We can initially set the lower bound (let us represent it with the
reduced fraction L_{N} / L_{D}) to be 0 and the upper bound (let us represent it
with the reduced fraction U_{N} / U_{D}) to be ∞. We update either
L_{N} / L_{D} or U_{N} / U_{D} for each pair of consecutive
indexes, just as in our analysis from Part 1.

Once we have L_{N} / L_{D} and U_{N} / U_{D}, we want to find a
rational number w_{J} / w_{C} such that
L_{N} / L_{D} < w_{J} / w_{C} <
U_{N} / U_{D}.
If L_{N} / L_{D} ≥ U_{N} / U_{D}, then there is certainly no
solution. Otherwise, there must be at least one solution; for example,
the mediant
(L_{N} + U_{N}) / (L_{D} + U_{D}) is certainly between the
bounds. However, the problem asks us to minimize w_{C} and w_{J}
(first w_{C}, and then w_{J}).

Since ΔJ_{i} ≤ 99 in this test set, we get
L_{D} + U_{D} ≤ 198. Therefore, we know that a solution with
w_{C} ≤ 198 exists. We can try all possible values from 1 to 198 as w_{C}. For
each choice of w_{C}, we can derive the smallest w_{J} such that
L_{N} / L_{D} < w_{J} / w_{C}, and then we can check whether
w_{J} / w_{C} < U_{N} / U_{D}.

For each integer C (from 1 to L_{D} + U_{D}), we can check whether there is a
rational number that is strictly between L_{N} / L_{D} and
U_{N} / U_{D}, and has a denominator that is not more than C. To do that, we can
find a rational number with denominator not more than C closest to the average of
L_{N} / L_{D} and U_{N} / U_{D}. This is because all rational
numbers that are strictly between L_{N} / L_{D} and U_{N} / U_{D}
are closer to the average of L_{N} / L_{D} and U_{N} / U_{D}
than all rational numbers that are not strictly between L_{N} / L_{D} and
U_{N} / U_{D}. We can do so by using a library function like Python's
fractions.limit_denominator, or by implementing our own approximation using
continued fractions.

Once we can solve the problem given in the previous paragraph, we can use binary search to find
w_{C} as the smallest C such that a rational number with denominator not more than C, and
strictly between L_{N} / L_{D} and U_{N} / U_{D} exists. Just as
we did for the previous test set, we can derive the smallest w_{J} such that
L_{N} / L_{D} < w_{J} / w_{C}.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

In Test Set 1 everything is small. One possible solution is to simulate the process. There is never a reason to not convert elements other than lead, so we should just apply the transformations over and over until no more lead can be created. If after a long time the amount of lead keeps growing, that means the total is unbounded. In the Test Set 2 section we do a formal analysis on bounds, but for this one, using an intuitive definition of "a lot" should suffice. If the amount is bounded, 1 gram of a metal can transform into at most 512 grams of lead, since it can only go through 9 splits before getting into a cycle. That means if we ever see more than 5120 grams of lead, the amount is unbounded.

However, the first example shows that we need to do a little more. What if lead itself can be used to get more lead? If that's possible, and we can get any lead at all, the final amount is definitely unbounded. If it is not possible, then we have no reason to ever consume lead. One way to check is to do the simulation above starting with 1 gram each of the two elements that lead is turned into. If that leads to 0 or 1 grams of lead, then lead cannot be used to get more lead. Otherwise, it can.

Test Set 2 is a lot larger, so a hand-wavy analysis and implementation will not work.
However, we can use the same idea above more carefully. Since each metal takes at most
**M** steps to turn into lead, we only need to do **M** iterations of a simulation,
where a simulation involves going over all non-lead metals and converting all grams of them.
This takes O(**M**^{2}) time. To prevent the numbers from growing too big,
we can simply do this process twice: the first pass creates as much lead as possible from
non-cyclical sources, so if the second pass creates even more, then it must come from
cyclical sources that ultimately yield an unbounded amount of lead. The second part,
to check for lead creating more lead, is the same as before.

Notice that the result
does not fit in 64 bit integers, though, and doing modulo all the time as usual doesn't work
right away, since we cannot afford to equate "no X" with "10^{9}+7 grams of X"
if X has the capability of creating unbounded amounts of lead (with X being lead itself,
or some other metal). There are multiple ways to get around the problem, including
using big integers, storing an additional bit for each result that represents whether it is an
actual 0 value, and doing calculations modulo 10^{9}+7 × K for some
large random prime K until the very end.

There are other solutions that only work for Test Sets 1 and 2, that are less efficient implementations of the solution for Test Set 3, that is explained below.

For Test Set 3, the solution looks quite different but it is actually similar. We check for cycles that may generate unbounded lead, and if there are none, we can do the simulation with a single iteration, ordering the metals appropriately. All of those things can be done in linear time, and we describe how below.

One useful thing to notice early on is that if we can determine that the amount of lead we can produce is bounded, the only formulas that are worth using are those that can eventually (perhaps in conjunction with other formulas) produce lead. Moreover, if the amount of lead is bounded, there is no point in using lead as an input to any formula, because even in the best case, every unit of lead will turn into one unit of lead and one unit of something else that cannot be converted to lead. (Otherwise, we could simply apply that series of formulas and generate as much lead as we want).

These observations imply that we can only get an unlimited amount of lead if some metal can produce itself and lead at the same time. In other words, there must be a series of formulas that takes one unit of some metal X and turns it into one unit of X and one unit of lead. In the process, we may end up with some other metals as well, but those don't matter. Notice that if that metal X directly produces metals A and B, then we require that either A produces X and B produces lead, or vice versa. This is because even if X is lead itself and either of A or B is also lead, without considering the other result, we are just destroying 1 unit of lead to get 1 unit of lead, so the total amount of lead doesn't change. In other words, in the unbounded case, after applying each formula, we need to work on both of the outputs, not just one of them.

Let Q be a graph in which each metal is represented by a node, and there is
an edge from node u to node v if, by consuming 1 unit of u, we can produce 1
unit of v. Notice that if a metal i is initially not present (that is,
**G _{i}** = 0), and it is not reachable in Q from some j with
G

Let Q' be the transpose
of Q, and let L denote the node representing lead. Then, traversing Q' from
node L defines a subgraph Q'_{L}, where every node is a metal that can
produce lead after a series of transformations. Now, let P_{u} be the
number of simple paths (paths without cycles) from L to any other node u in
Q'_{L}. If the amount of lead is bounded, then P_{u} is the
number of units of lead we can get from every unit of u. This follows from
the fact that every (reversed) edge is a valid transformation where we start
with 1 unit of some metal and produce 1 unit of some other metal, so along
the path, we are using the results of previous transformations and not the
very first unit of metal we started with. For example, let Q'_{L} be
the following graph:

- 1 → 2
- 1 → 3
- 2 → 4
- 3 → 4

- 4 turns into 2 and 3
- 2 turns into 1 and something else
- 3 turns into 1 and something else

There are 2 simple paths from 1 to 4, namely, 1 → 2 → 4 and 1 → 3 → 4. Now, 1 unit of metal 4 can be turned into 2 units of lead (1) as follows:

- Turn one unit of 4 into one unit of 2 and one unit of 3
- Take the one unit of 3 from step 1 and turn it into one unit of 1 and one unit of some other metal
- Take the one unit of 2 from step 1 and turn it into one unit of 1 and one unit of some other metal

On the other hand, notice that the nodes that form
a strongly connected component (SCC)
in Q are a set of metals that can produce each other. More formally, if u and
v belong to the same SCC, we can produce 1 unit of v from 1 unit of u, and
vice versa. With these definitions, we can say that the amount of lead is
unbounded if, for some node u in Q with v_{1} and v_{2}
being the two outputs of node u's formula, either:

- v
_{1}is in Q'_{L}and v_{2}and u are in the same SCC, or - v
_{2}is in Q'_{L}and v_{1}and u belong to the same SCC.

Otherwise, there is a limit on the amount of lead we can get, which can be
computed by multiplying P_{u} by the initial number of units
**G _{u}** for each u in Q'

We can compute all the SCCs in O(**M**) time using Tarjan's algorithm
or Kosaraju's algorithm
, since both the number of nodes and the number of edges in the graph are
linear on M. Walking over the graphs defined above also takes O(**M**)
time, and so does checking the unbounded condition. We can also compute all
P_{u} in O(**M**) time by taking advantage of the fact that if the
amount of lead is not unbounded, then there are no cycles in Q'_{L}.
(If a cycle existed in Q'_{L}, then by reversing the edges, we get
at least one metal for which the unbounded condition holds.) Therefore, the
nodes on Q'_{L} can be topologically sorted. That means we can
compute a function F from vertices to the number of simple paths in linear
time, using dynamic programming with this recursive definition:

- F(L) = 1
- F(u) = sum(F(v)) for each v, such that there is an edge from v to u in Q'
_{L}

Since the number of edges in every graph described above is also O(**M**),
the whole problem can be solved in linear time.

Test Data

We recommend that you practice debugging solutions without looking at the test data.