Имя: Пароль: Зарегистрироваться Восстановить пароль
24/09/2023 22:08:01

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

## Задачи

1887. Blind Problem Solving

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод Послать решение 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();
}
stop();
}

Source: ACM ICPC NEERC, 2012 