We will show how to find an optimal solution for an arbitrary number of bags. Here "optimal" means that our solution requires the least possible number of weighings in the worst case. The following text contains several technical details (especially the proof that it is optimal), that were not necessary to solve this problem. The general idea is not difficult and any (even a bit less efficient) solution using this idea should be good enough to solve both inputs. Both inputs could be solved by hand, without the help of a computer.

For a while let's suppose that our scale will show any weight correctly (even if
it is greater than 1717 grams).
Let **B** be the number of the cursed bag. Let us take **x _{1}** beans
from the first bag,

We will look at the same problem from the other side. Suppose the cursed bag is not determined at the beginning. Instead, you are playing a game against a devil sitting inside the scale. At the beginning, any of the bags may be cursed. We will call such bags "candidates". The game ends when there is only one candidate left, in other words there is only one solution consistent with all weighings. The devil wants to force you to do as many weighings as possible. In fact, one such devil was implemented in the program that was answering your submits. The devil's strategy is simple – he would always select such an answer that the largest possible number of candidates remains.

Let **y _{i}** be the number of bags from which we took exactly

Let **M(n)** denote the largest number of bags, among which we can identify the
cursed one if we may use the scale at most **n** times. Clearly **M(0)=1**.
Suppose we know **M(n)** for some **n**. How to compute **M(n+1)**?

Clearly it doesn't make sense to weigh beans from bags that are no
longer candidates. So let's suppose that all the bags are candidates. We may make **n+1**
weighings. However, if more than **M(n)** candidates remain after the first weighing, the devil
wins. It follows that no **y _{i}** may exceed

For now, accept without proof that in an optimal solution we don't have to make weighings where a BAD CASE may occur. The proof will be included at the end of this solution.

Let **Z** be the greatest value of **i** for which **y _{i}** is non-zero.
The maximum possible weight of beans on the scale is

As an example we will compute **M(1)** and **M(2)**. For **M(1)** each
**y _{i}** may be at most

We now compute the values **M(n)** and optimal weighings for **n<10** in the way described
above. Now it suffices to find the smallest **n** such that **M(n)** is at least the number of
bags we have. Then we simply follow the optimal strategy described above. We leave the remaining few details
(e.g. what happens if we have less than **M(n)** bags) to the reader. Note that if we choose the numbers of
beans for each weighing wisely, the set of candidate bags will be **{ x , x+1 , ... , y-1 , y }**
(for some **x,y**) after each weighing.

The solution described above needs **only 9 submits** (8 questions, 1 answer) to solve the problem C2.
If your solution wasn't optimal, you probably needed all 10 submits. (And therefore you couldn't make
any mistakes when submitting your questions.)

Proof that in an optimal solution we don't have to make weighings where a BAD CASE may occur.
Take any weighing where a BAD CASE may occur.
Let **K<Z** be the smallest number of cursed beans on the scale for which the weight at least
**W** is achieved. Depending on the devil's answer **y _{0}**, ...,