首页 > ACM题库 > HDU-杭电 > HDU 4120-Ji-Tu Problem[解题报告]HOJ
2015
04-16

HDU 4120-Ji-Tu Problem[解题报告]HOJ

Ji-Tu Problem

问题描述 :

There are some chickens and rabbits in the cage. They have fifteen heads and forty feet in all.
How many chickens and rabbits are there respectively?
It is a classical math problem which can date back to the Northern and Southern Dynasties (420-589). Here is an interesting algorithm to solve the problem: Assume that the chickens and rabbits are well trained. You whistle, and all of them lift a leg, then there are 40-15 = 25 feet on the floor. You whistle again, and there are 25 – 15 = 10 legs remain standing. After two whistles, all the chickens sit on the floor, and all the rabbits stand on two legs. So there are 10/2 = 5 rabbits and 15 – 5 = 10 chickens.
John has a farm with lots of animals in it. He is now facing the similar problem. There are exactly N kinds of animals and he wants to know their quantities. He only knows that different kinds of animals have different number of legs (at least one), but he has no idea how many legs they each have. He trains the animals and tries to figure it out using the algorithm stated above. First he makes all the animals stand up with all their legs and counts their legs. then, for each time he whistles, all the animals lift one leg(if it has at least one leg standing on the ground), and then he counts the feet again. After K times, he thinks that it is enough to determine the quantity of each kind of animal, but does it really work? So, it is your job to help him to solve the problem.

输入:

The first line contains an integer T(1 <= T <= 100), indicating the number of test cases.
Each test case contains two lines.
The first line contains two integers N(1 <= N <= 1000) and K(1 <= K <= 1000), representing the number of different kinds of animals and the time he whistles.
The second line contains K + 1 integers A0,A1 … AK(0 <= Ai <= 104) where Ai represents the number of legs after his ith whistle.

输出:

The first line contains an integer T(1 <= T <= 100), indicating the number of test cases.
Each test case contains two lines.
The first line contains two integers N(1 <= N <= 1000) and K(1 <= K <= 1000), representing the number of different kinds of animals and the time he whistles.
The second line contains K + 1 integers A0,A1 … AK(0 <= Ai <= 104) where Ai represents the number of legs after his ith whistle.

样例输入:

3
2 3
14 9 6 3
2 2
8 5 3
3 2
20 13 8

样例输出:

Case #1:
Unique Solution
1 2
4 3
Case #2:
No Solution
Case #3:
Multiple Solutions

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define LL __int64
const int N = 10005;
using namespace std;

int a[N], n, k, s, t;

int Ans()
{
    int i;
    for( i = 1; i <= k; i ++ )
        if( a[i] < 0 )
            return 0;

    for( i = 1; i < k; i ++ )
    {
        a[i] -= a[i+1];
        if( a[i] )
        {
            n --;
            t -= a[i] * i;
        }
    }
    s = a[k];
    a[k] = 0;
    for( i = 1; i < k; i ++ )
        if( a[i] < 0 )
            return 0;

    if( n < 0 || s < n)
        return 0;
    if( n == 0 )
    {
        if( t == 0 && s == 0 )
            return 1;
        else
            return 0;
    }
    if( n == 1 )
    {
        if( t%s == 0 && t/s >= k )
        {
            a[t/s] = s;
            return 1;
        }
        else
            return 0;
    }
    //n > 1
    int ans(0), j, tt, mm = ( n*n-n ) / 2;
    for( i = k; i*s <= t-mm; i ++ )
    {
        tt = t-mm - i*s;
        if( tt == 0 )
        {
            for( j = 1; j < n; j ++ )
                a[k+j] = 1;
            a[k] = s-n+1;
            ans ++;
        }
        else if( tt > 1 && n > 2 )
            return 2;
        else if( tt > 1 && n == 2 )
        {
            tt += mm;
            for( j = 1; j < s; j ++ )
            {
                if( j > tt )
                    break;
                else if( ans > 1 )
                    return 2;
                if( tt%j == 0 )
                {
                    a[ tt/j + i ] = j;
                    a[i] = s-j;
                    ans ++;
                }
            }
        }
        else if( s > n )
            return 2;
        else
        {
            for( j = 1; j < n-1; j ++ )
                a[k+j] = 1;
            a[k+n] = 1;
            a[k] = s-n+1;
            ans ++;
        }
        if( ans > 1 )
            return 2;
    }
    return ans;
}

int main()
{
    //freopen( "in.txt", "r", stdin );
    //
    int ca, cs, i, pre, now;
    scanf( "%d", &ca );
    for( cs = 1; cs <= ca; cs ++ )
    {
        memset( a, 0, sizeof(a) );
        scanf( "%d%d", &n, &k );
        scanf( "%d", &t );
        pre = t;
        for( i = 1; i <= k; i ++ )
        {
            scanf( "%d", &now );
            a[i] = pre - now;
            pre = now;
        }
        printf( "Case #%d:\n", cs );

        now = Ans();
        if( now < 1 )
            printf( "No Solution\n" );
        else if( now > 1 )
            printf( "Multiple Solutions\n" );
        else
        {
            printf( "Unique Solution\n" );
            for( i = 1; i < N; i ++ )
                if( a[i] )
                    printf( "%d %d\n", i, a[i] );
        }
    }
    //
    return 0;
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示