链接:

https://codeforces.com/contest/1247/problem/C

题意:

Vasya will fancy any number as long as it is an integer power of two. Petya, on the other hand, is very conservative and only likes a single integer p (which may be positive, negative, or zero). To combine their tastes, they invented p-binary numbers of the form 2x+p, where x is a non-negative integer.

For example, some −9-binary ("minus nine" binary) numbers are: −8 (minus eight), 7 and 1015 (−8=20−9, 7=24−9, 1015=210−9).

The boys now use p-binary numbers to represent everything. They now face a problem: given a positive integer n, what's the smallest number of p-binary numbers (not necessarily distinct) they need to represent n as their sum? It may be possible that representation is impossible altogether. Help them solve this problem.

For example, if p=0 we can represent 7 as 20+21+22.

And if p=−9 we can represent 7 as one number (24−9).

Note that negative p-binary numbers are allowed to be in the sum (see the Notes section for an example).

思路:

枚举使用的个数，判断n-i*p能不能满足条件。

代码:

#include <bits/stdc++.h>

typedef long long LL;

using namespace std;

LL n, p;

int Cal(LL x)

{

    int cnt = 0;

    while (x)

    {

        if (x&1)

            cnt++;

        x >>= 1;

    }

    return cnt;

}

int main()

{

    ios::sync_with_stdio(false);

    cin >> n >> p;

    for (int i = 1;i <= 1e4;i++)

    {

        LL v = n-p*i;

        if (v <= 0)

            break;

        int num = Cal(v);

        if (num <= i && i <= v)

        {

            cout << i << endl;

            return 0;

        }

    }

    cout << -1 << endl;

    return 0;

}

巴特西

Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2) C. p-binary

链接:

题意:

思路:

代码:

最新文章

热门文章