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


1887. Blind Problem Solving

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
Interaction protocol
You must write function solve with two integer parameters `n` and `c`.
void solve(int n, int 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:
  • stop() — this is the final action. This means that `B` encodes the optimal solution.
  • accept() — the value of `B` is copied to `A`.
  • decline() — the value of `B` is thrown out.
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.
Sample code
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();
Source: ACM ICPC NEERC, 2012