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 x1 beans from the first bag, x2 from the second one, ... and xm from the last (m-th) one. The total weight of the selected beans will be (sum of xi) + xB. We know the values xi, we compute the value (sum of xi) and get the value xB. In order to determine B all the values xi have to be different. This is easily accomplished – e.g. let x1=0, ..., xm=m-1. So if there was no limit on the maximum weight, the cursed bag could be always determined using only one weighing. However, there IS a limit (let's call it W, in our case W=1717).
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 yi be the number of bags from which we took exactly i beans for the current weighing. The total weight of the beans placed on the scale is (sum of i*yi)+C, where C is the number of beans taken from the cursed bag. Again, we know the value (sum of i*yi) thus we are able to determine C. (In fact, if the returned weight is W, there may even be more possible values for C. If there are indeed more possible Cs, we will call the situation a BAD CASE and deal with it later.) We now know that there are exactly C cursed beans on the scale. This reduces our search to yC bags, namely those bags from which we took exactly C beans.
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 yi may exceed M(n) – the devil would simply answer as if there were i cursed beans on the scale.
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 yi is non-zero. The maximum possible weight of beans on the scale is (sum of i*yi) + Z. Each yi is at most M(n) and the BAD CASE doesn't occur. We are trying to maximize (sum of yi) – the number of bags we have – while keeping the mentioned conditions true. Clearly the sum is maximal for y0=...=yZ-1=M(n), yZ<=M(n). (I.e. we take 0 beans from M(n) bags, 1 bean from another M(n) bags, etc. until the second greatest possible weight reaches W.)
As an example we will compute M(1) and M(2). For M(1) each yi may be at most M(0)=1. It follows that the best weighing is described by y0=...=yZ=1 for some Z. The maximum possible weight is 0+1+2+...+(Z-1)+Z + Z. A quadratic inequality for Z follows, solving it gives Z<=57. Therefore M(1)=58 – we are able to find the cursed bag in one weighing iff there are at most 58 bags. Now for M(2) each yi may be at most M(1)=58. We take 0 beans from 58 bags, 1 bean from 58 bags, etc. E.g. by solving a similar quadratic inequality as above we get that the optimal weighing is described by y0=...=y7=58, y8=10. (There are (sum of yi)=474 bags, the maximum possible weight is 58*0+...+58*7 + 10*8 + 8 = 1712.) Therefore M(2)=474.
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 y0, ..., yK-1 or (yK+...+yZ) candidates will remain. We took Z beans from some yZ bags. Now suppose we would take only Z-1 beans from each of them. How would the possible outcomes change? Either the value K stays the same or it increases to some K' (because the number of beans on the scale decreased). In the first case the possible outcomes are the same – we lost nothing. The second case may even be better (but never worse) – y0, ..., yK'-1 or (yK'+...+(yZ-1+yZ)) candidates may remain. (Remember that the devil always chooses the maximum of these numbers and note that the maximum didn't increase when we modified the numbers of beans.)