数论 boj1202 appleAndBox boj1804 add number

AppleAndBoxSubmit: 425   Accepted:197Time Limit: 1000MS  Memory Limit: 65536KDescription
Monica有N个苹果和M个盘子，现在她需要将N个苹果分放到M个盘子里。

因为Monica希望做到一个很好的分配策略，不论Chandler需要多少个（1到N）苹果时，她总能拿出若干盘，这些盘子里的苹果数之和就是 Chandler所需要的，而不必重新调整每个盘子里的苹果。


现在Monica告诉你N和M，请你帮她判断是否存在这样的分配策略。


Input
多则测试数据，以两个0结束。
每组数据占一行，两个整数N，M。
1 <= N < 2^32， 1 <= M <= 25


Output
对应每组输入数据，如果存在一种分配策略则输出“YES”，否则输出“NO”。



Sample Input

2 1
4 2
6 4
0 0


Sample Output

NO
NO
YES


利用下面的结论：
a, a+1, a+2, a+n能够表示a到a + (a+1) + ... + (a+n)之间的任何数

如:
1, 2能表示1..3之间的任何数
1, 2, 4能表示任何1...1+2+4之间的数
1, 2, 4, 8能表示任何1...1+2+4+8之间的数
以此类推

代码如下

#include <stdio.h>

long long N, M;

int solve(long n, long long m)
{
    int i;
    long long sum, temp;


    /*计算m个数能表示的值的范围的上界*/
    sum = 1;
    for (i=1 ; i<m ; i++)
    {
        temp = sum + 1;
        sum += temp;
    }

    if (sum >= n)
        return 1;
    else
        return 0;
}

int main(int argc, char *argv[])
{
    int ret;

    while (1)
    {
        scanf("%lld %lld", &N, &M);
        if (0 == N && 0 == M)
            break;

        ret = solve(N, M);
        if (0 == ret)
            printf("NO\n");
        else
            printf("YES\n");
    }
}

Add numberSubmit: 271   Accepted:47Time Limit: 1000MS  Memory Limit: 65536KDescription
Employees of Baidu like to play a game called Making Numbers. It goes like this: there are two players in the game, one is called little A, the other little B. There are some cards with a number on each one of them, little A chooses a number X from 1 to N randomly, while little B has to choose some cards, the sum of which equals X. Now there are already M cards with numbers, and K blank cards. At the beginning of the game, little B is allowed to write numbers on the blank cards. Now little B wants to know, if it is possible to write some numbers that will assure him of the victory, that is to say, if it is possible for him to make up any number from 1 to N with the cards.

Input
The input consists of several test cases. The first line is an integer T , in the second line of each case are 3 numbers, N M K, the second line shows the number that is already written on M cards. 1<=N<=99999999,0<=M<=19,1<=K<=19 The numbers in the second line are above 0, smaller than or equals N, in non-descending order. Input ends with 0 0 0, which doesn't need to be processed.

Output
If little B can make it, output "YES", else output "NO".

Sample Input

3 15 0 4
12 3 2
3 3 3
13 3 2
3 3 3


Sample Output

YES
YES
NO

思路类似于上题:

#include <stdio.h>

long long N, M, K, data[30];

int solve(int n, int m, int k)
{
    long long i, t, sum;

    for (i=0 ; i<m ; i++)
        scanf("%lld", &data[i]);
    
    sum = 0;
    for (i=0 ; i<m ; i++)
    {
        t = data[i];
        while (sum < t - 1)
        {
            k--;
            if (k < 0)
                return 0;
            sum += (sum + 1);
// printf("%lld ", sum);

            if (sum >= n)
                return 1;
        }
        sum += t;
// printf("%lld ", sum);

        if (sum >= n)
            return 1;
    }

    while (k > 0)
    {
        sum += (sum + 1);
// printf("%lld ", sum);

        if (sum >= n)
            return 1;
        k--;
    }

// printf("\n");

    return 0;
}

int main(int argc, char *argv[])
{
    int T, ret;

    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld %lld %lld", &N, &M, &K);
        ret = solve(N, M, K);
        if (0 == ret)
            printf("NO\n");
        else
            printf("YES\n");
    }
}