Once upon a time, Toma found himself in a binary cafe. It is a very popular and unusual place. The cafe offers visitors k different delicious desserts. The desserts are numbered from 0 to k−1. The cost of the i-th dessert is 2i coins, because it is a binary cafe! Toma is willing to spend no more than n coins on tasting desserts. At the same time, he is not interested in buying any dessert more than once, because one is enough to evaluate the taste. In how many different ways can he buy several desserts (possibly zero) for tasting? Input The first line of the input contains a single integer t (1≤t≤1000) — the number of test cases. Then follows t lines, each of which describes one test case. Each test case is given on a single line and consists of two integers n and k (1≤n,k≤109) — the number of coins Toma is willing to spend and the number of desserts in the binary cafe. Output Output t integers, the i-th of which should be equal to the answer for the i-th test case — the number of ways to buy desserts for tasting.

题目描述

Toma来到了一个二进制咖啡馆，这里有k种不同的点心，第i个点心的价格是2^i个硬币，Toma最多愿意花n个硬币去品尝不同的点心，求他最多能品尝多少种不同的点心。

输入格式

第一行包含一个整数t，表示测试数据组数。

每组数据占一行，包含两个整数n和k。

输出格式

每组数据输出一个结果，每个结果占一行。

数据范围

1≤t≤1000,
1≤n,k≤10^9

输入样例

2
5 3
7 3

输出样例

1
2

算法1

(贪心) $O(logn)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

相关问题

Once upon a time, Toma found himself in a binary cafe. It is a very popular and unusual place. The cafe offers visitors k different delicious desserts. The desserts are numbered from 0 to k−1 . The cost of the i -th dessert is 2i coins, because it is a binary cafe! Toma is willing to spend no more than n coins on tasting desserts. At the same time, he is not interested in buying any dessert more than once, because one is enough to evaluate the taste. In how many different ways can he buy several desserts (possibly zero) for tasting? Input The first line of the input contains a single integer t (1≤t≤1000 ) — the number of test cases. Then follows t lines, each of which describes one test case. Each test case is given on a single line and consists of two integers n and k (1≤n,k≤109 ) — the number of coins Toma is willing to spend and the number of desserts in the binary cafe. Output Output t integers, the i -th of which should be equal to the answer for the i -th test case — the number of ways to buy desserts for tasting.

This is a classic problem of finding the number of subsets of a given set with a certain property. In this case, we want to find the number of subsets of the set {0,1,2,...,k-1} such that the sum of the elements in the subset is less than or equal to n.

We can use dynamic programming to solve this problem efficiently. Let dp[i][j] be the number of ways to choose a subset of the first i elements of the set {0,1,2,...,k-1} such that the sum of the elements in the subset is exactly j. Then the answer to the problem is the sum of dp[k][0] to dp[k][n].

The base case is dp[0][0]=1, since there is exactly one way to choose an empty subset with sum zero. For each i from 1 to k, we can either choose the i-th element or not. If we choose it, then we need to find the number of ways to choose a subset of the first i-1 elements with sum j-2i. If we do not choose it, then we need to find the number of ways to choose a subset of the first i-1 elements with sum j. Therefore,

dp[i][j] = dp[i-1][j] + dp[i-1][j-2i], if j>=2i
dp[i][j] = dp[i-1][j], otherwise

The final answer is the sum of dp[k][0] to dp[k][n]. The time complexity of this algorithm is O(kn).

Here is the Python code to solve the problem:

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    dp = [[0] * (n+1) for _ in range(k+1)]
    dp[0][0] = 1
    for i in range(1, k+1):
        for j in range(n+1):
            dp[i][j] = dp[i-1][j]
            if j >= 2**i:
                dp[i][j] += dp[i-1][j-2**i]
    print(sum(dp[k]))

I hope this helps! Let me know if you have any more questions.

请用C语言实现Once upon a time, Toma found himself in a binary cafe. It is a very popular and unusual place. The cafe offers visitors k different delicious desserts. The desserts are numbered from 0 to k−1 . The cost of the i -th dessert is 2i coins, because it is a binary cafe! Toma is willing to spend no more than n coins on tasting desserts. At the same time, he is not interested in buying any dessert more than once, because one is enough to evaluate the taste. In how many different ways can he buy several desserts (possibly zero) for tasting? Input The first line of the input contains a single integer t (1≤t≤1000 ) — the number of test cases. Then follows t lines, each of which describes one test case. Each test case is given on a single line and consists of two integers n and k (1≤n,k≤109 ) — the number of coins Toma is willing to spend and the number of desserts in the binary cafe. Output Output t integers, the i -th of which should be equal to the answer for the i -th test case — the number of ways to buy desserts for tasting.

以下是使用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int t;
    scanf("%d", &t);

    while(t--)
    {
        int n, k;
        scanf("%d%d", &n, &k);

        int ans = 0;
        for(int i=0; i<=30; i++)
        {
            if(n >= (1<<i) - 1 && k >= i+1)
            {
                ans = i+1;
            }
            else
            {
                break;
            }
        }

        int res = 0;
        for(int i=0; i<ans; i++)
        {
            res += (1<<i);
        }

        if(res <= k)
        {
            ans += (k-res);
        }

        printf("%d\n", ans);
    }

    return 0;
}

程序先输入了t表示测试用例的数量，然后使用while循环读入t个测试用例。每个测试用例包含两个整数n和k。接下来，程序使用一个for循环，从0到30枚举甜点的数量i，如果n大于等于2^i-1并且k大于等于i+1，则说明可以购买i+1个甜点，同时更新ans的值。如果n小于2^i-1或者k小于i+1，则退出循环。接下来，程序使用另一个for循环，计算购买ans个甜点的花费res。如果res小于等于k，则说明可以购买所有这ans个甜点，此时ans就是答案。否则，程序需要再购买k-res个甜点，将ans加上这个数量即可。最后，程序输出ans作为答案。