Матч 409, Палка (Stick)

Дивизион 2, Уровень 1

У Джона есть палка длиной 64 сантиметра. Однако ему необходима палка длины х сантиметров. Он решил разломать исходную палку на несколько кусков, из которых потом он сможет склеить палку длины х сантиметров. Для решения задачи Джон хочет воспользоваться следующим алгоритмом:

1. Джон суммирует длины имеющихся у него кусков (изначально имеется один кусок длины 64 сантиметра). Пока сумма больше х, Джон делает следующее:

· Джон выбирает кусок наименьшей длины и ломает его пополам;

· Если после выбрасывания одной из половинок сумма оставшихся кусков не станет меньше х, то выбросить ее;

2. Джон склеивает имеющиеся у него куски.

Вычислить количество кусков, которое Джон будет склеивать на втором шаге алгоритма.

Класс: Stick

Метод: int pieces(int x)

Ограничения: 1 £ x £ 64.

Вход. Длина требуемой палки х.

Выход. Количество кусков, которое Джон будет склеивать на втором шаге алгоритма.

Пример входа

x

32

48

23

Пример выхода

1

2

4

РЕШЕНИЕ

элементарные вычисления

Задачу можно решить двумя способами:

1. Моделирование процесса разлома палок. Палку наименьшей длины будем находить в результате сортировки. Суммировать длины палок будем при помощи функции accumulate.

2. Можно заметить, что длины получающихся палок в процессе разлома являются степенями 2. Поэтому ответом будет количество единиц в бинарном представлении числа х. Операция x = x & (x – 1) уничтожает последнюю единицу в бинарном представлении числа х.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

vector<int> v(1,64);

class Stick

{

public:

int pieces(int x)

{

int sum, v0;

while((sum = accumulate(v.begin(),v.end(),0)) > x)

{

sort(v.begin(),v.end());

v0 = v[0]; v[0] = v0 / 2;

if (sum - v[0] < x) v.push_back(v[0]);

}

return v.size();

}

};

Реализация функции pieces через подсчет битов:

#include <stdio.h>

class Stick

{

public:

int pieces(int x)

{

int res=0;

for(; x; x = x & (x - 1)) res++;

return res;

}

};