06/04/2025 19:20:59

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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();
  }
  stop();
}

06/12/2012	Занятие 13 (Задачи NEERC 2012) (B)
21/11/2013	Занятие 10 для продолжающих (C)