OJ---百钱买百鸡问题

Description

“百钱买百鸡”是我国著名的古代数学问题,中国古代数学家张丘建在他的《算经》中提出了这样一个问题:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问翁、母、雏各几何?
你的任务是求解下面这个问题。问题是这样描述的:a文钱可买一只公鸡,b文钱可买一只母鸡,c文钱可买d只小鸡。用m文钱买n只鸡,那么有公鸡x只、母鸡y只、小鸡z只。求解出符合题意的x,y,z。

Input

输入为一张表。第一行是一个固定不变的表头,格式见sample。后面有多行,每行为一组测试数据。每组测试数据由6个整数组成,分别为“a,b,c/d,m,n”。满足0<a,b,c,d<=50,50<=m,n<=108+1,并且母鸡和小鸡的单价不会相同。

Output

每组测试数据的运行结果输出为一张表,表头固定为“COCKS,HENS,CHICKS”。每组测试数据的一个可行解数出为一行,为三个整数:“x,y,z”。多组解按照公鸡数从少到多的顺序输出。若测试数据无解则输出“Cannot buy!”。两组测试数据之间用一个空行分隔开。

Sample Input

COCK,HEN,CHICK,MONEY,CHICKS 3,2,1/3,100,100 5,3,1/3,100,100 8,5,1/7,100,100 8,5,1/7,300,300

Sample Output

COCKS,HENS,CHICKS 0,40,60 5,32,63 10,24,66 15,16,69 20,8,72 25,0,75 COCKS,HENS,CHICKS 0,25,75 4,18,78 8,11,81 12,4,84 Cannot buy! COCKS,HENS,CHICKS 8,40,252

HINT

本题重点在于了解多重循环的运行效率问题,减少一层循环可以降低很大规模的运算量。通过在循环体内加计数器可以统计出循环的运行次数,当测试数据变大时,运行次数的增长会非常可观,这就是超时的原因了。

//总思路为:因为要考虑超时的问题,所以只能采用一个循环,不妨让x++
//联立方程组求出y,z的表达式
//(1)(2)(3)处都应当化简掉c/d,即等式两边都乘以d,防止出现c/d=0而干扰结果,这也是解决本题的关键!!!
#include <stdio.h>
int main ()
{
    int a,b,c,d,m,n;
    scanf("COCK,HEN,CHICK,MONEY,CHICKS");
    while(scanf("%d,%d,%d/%d,%d,%d",&a,&b,&c,&d,&m,&n)!=EOF)
    {
        int judge=1;
        int x,y,z;
        int first=1;
        for(x=0;x<=m/a;x++)
        {
            y=(m*d-c*n-(a*d-c)*x)/(b*d-c);//(1)
            z=(m*d-b*d*n-(a-b)*d*x)/(c-b*d);//(2)
            if( x+y+z==n && (a*x*d+b*y*d+c*z)==m*d && y>=0 &&z>=0)//(3)
            {
                if(first) {printf("COCKS,HENS,CHICKS\n");first=0;}
                printf("%d,%d,%d\n",x,y,z);
                judge=0;
            }
        }
        if(!judge) printf("\n");
        if(judge) printf("Cannot buy!\n\n");
    }
}

上一篇:2.5约瑟夫问题(OJ 2746)DAY 2


下一篇:【Java数据结构】经典链表OJ题——超详细做题笔记及心得