Рабочее место участника

This is an interactive problem. You are to solve a subset sum problem, a variant of a knapsack problem. You are given n items, each weighing wi grams, and a knapsack with the maximum capacity of c grams. You are to find a subset of these items whose total weight does not exceed c and is maximal possible. Easy? But you have to do it blindly!

At the beginning you know only two numbers `n` and `c` — the number of items and the maximal capacity of a knapsack. There are positive weights `w_i` and two bit strings inside the jury program: `A` and `B`, each having `n` bits. Each bit string represents a candidate solution to the problem: if the `i`-th bit is set to 1, then the `i`-th item is a part of the solution. `A` stores your previously selected candidate solution. `B` is a candidate solution that is proposed to you on each turn by flipping a random bit in `A`. You can either accept or decline this proposal. Your task is to stop when `B` encodes the optimal solution.

Initially, `A` is initialized with some value that is fixed for each test case but is not known to you. At each turn the value of `A` is copied to `B`, and then a bit at a uniformly random position of `B` is flipped.

You must write function solve with two integer parameters `n` and `c`.

At any time you may get the weight of `B` which is equal to `sum_{i=1}^n\ w_i\ *B(i)`, where `B(i)` is the value of `i`-th bit in `B`.

Your function is allowed to perform one of the following three actions:

After each non-final action next turn starts. You are allowed to perform at most 1000 actions.

It is guaranteed that a jury program chooses the bits to flip randomly, i. e. using a random number generation algorithm with an initial seed fixed for each test case.

void solve(int n, int c)
{ 
  for(int i=0;i<100;++i)
  { int w=weightB();
    if(w==c) stop();
    else if(w<c) accept();
    else decline();
  }
  stop();
}