主页    讨论版    问题    名次    状态    统计
问题 L: 还是硬币问题
时间限制: 1 Sec  内存限制: 128 MB
提交: 183  解决: 30
状态
题目描述
给你无限多个1元的硬币和2元的硬币，还有5元的硬币。

现在要你从这3种硬币中取n个硬币，使得他们的价值和为m

输入
多组输入

每组n ， m

 n < 1e6 , m <1e6

输出
总的方案数目

样例输入
2 3
样例输出
1
提示
  提交

我代码：
#include<stdio.h>
int main()
{
    int n,m;
    int x,y,z,i,k,j;
    i=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(x=0; x<=n; x++)
        {
            for(y=0; y<=n-x; y++)
            {
                for(z=0; z<=n-x-y; z++)
                {
                    if((x+y+z==n)&&(x+2*y+5*z==m))
                    {
                        i++;
                    }

                }
            }
        }
        printf("%d\n",i);
    }
    return 0;
}

1*a + 2*b + 5*(n-a-b) = m
4*a + 3*b = 5*n - m
a + 3*(a+b) = 5*n-m
在a>=0的条件下，a+b 有 (5*n-m)/3 种可能
此外 a+b>=a，即 a+b >= 5*n-m - 3*(a+b)，即 a+b >= (5*n-m)/4
结果就是 (5*n-m)/3 - (5*n-m-1)/4
以题目中的例子为例就是 7/3 - (7-1)/4 = 2 - 1 = 1

感觉数学公式能一步到位~~~~

第一次先取1，然后求2和5的取法次数，然后下一次每次多取1，然后求2和5的取法次数，感觉其中的规律可以整合~~~~~

对哦，原来限制取银币个数了，我上说的是不限取银币的个数~~~二楼正解~

[此贴子已经被作者于2017-1-7 18:04编辑过]

提交上去答案错误

这个应该能AC~~~

#include<stdio.h>
int main()
{
    int n=0;
    int m=0;

    while(scanf("%d%d",&n,&m)!=EOF)
    { 
        int x=0;
        int y=0;
        int z=0;
        int i=0;
        for (y=0;y<=n;y++)
        {
            x=(5*n-m-3*y)/4;
            z=n-x-y;
            if ((5*n-m-3*y)%4==0&&x>=0&&z>=0)
                i++;

        }

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

    return 0;
}

[此贴子已经被作者于2017-1-7 23:24编辑过]

一步到位~~~~~~~~

#include<stdio.h>
int main()
{
    int n=0;
    int m=0;

    while(scanf("%d%d",&n,&m)!=EOF)
        printf("%d\n",5*n<m||n>m?0:m<2*n?(m-n)/4+1:(5*n-m)/12+1);

    return 0;
}
    

这是我自己推的，和二楼的还是有点差距~

[此贴子已经被作者于2017-1-8 02:53编辑过]

今天C考，求及格~~

献上大神分析造福后来有同样困惑的人，，，如果看不懂不要紧，，，，反正楼主我一知半解一楼最简单但是耗时长

帮我提交一下试试

#include <stdio.h>

int foo( int n, int m )
{
    if( 5*n-m < 0 )
        return 0;
    if( 5*n-m == 0 )
        return 1;

    return (5*n-m)/3 - (5*n-m-1)/4;
}

int main( void )
{
    for( int n,m; scanf("%d%d",&n,&m)==2; )
        printf( "%d\n", foo(n,m) );

    return 0;
}

虽然你很厉害  但考试（尤其是笔试） 却未必能过  但是能比其他同学多打一些分数是谆谆的