正在浏览栏目导航：首页 > 开发学院 > C/C++ >

帮我解几道ACM

时间:2008-06-02 21:05:03 来源:论坛整理作者: 编辑:chinaitzhe

谢谢大家大家也不可以給出自己的算法
Problem1
输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）

Input
一个整数N。(N不大于30000)

Output
从小到大排列的不大于N的与7有关的数字，每行一个。

Sample Input
20
Sample Output
7
14
17

Problem2

猪的安家
Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈，很多猪只能够在一个猪圈安家。举个例子，假如有16头猪，Andy建了3个猪圈，为了保证公平，剩下1头猪就没有地方安家了。Mary生气了，骂Andy没有脑子，并让他重新建立猪圈。这回Andy建造了5个猪圈，但是仍然有1头猪没有地方去，然后Andy又建造了7个猪圈，但是还有2头没有地方去。Andy都快疯了。你对这个事情感爱好起来，你想通过Andy建造猪圈的过程，知道Andy家至少养了多少头猪。

输入

输入包含多组测试数据。每组数据第一行包含一个整数n (n <= 10) – Andy建立猪圈的次数，解下来n行，每行两个整数ai, bi( bi <= ai <= 1000), 表示Andy建立了ai个猪圈，有bi头猪没有去处。你可以假定(ai, aj) = 1.

输出

输出包含一个正整数，即为Andy家至少养猪的数目。

样例输入

3
3 1
5 1
7 2

样例输出

16

Original: Andy Zhau's Contest No.1

网友回复:两道题目都不难，自己思考一下，应该能做出来的。这样对你自己才有好处。
网友回复:我是这样想第一道题算法的,在1到N之间循环,循环体中嵌套一个验证现在的数能否被7整除,其中含有7,满足一项则输出.
不过这个验证其中含有7怎么解决?
网友回复:判定(n-7)==0，假如是则直接输出。假如不是则n=n/10（对n进行去尾处理），然后继续判定是否包含7，直到最高位。
网友回复:#include <iostream.h>

int main()
{
int n,sum;
cin>>n;
int a[10],b[10];
for( int i =0; i < n; i )
cin>>a[i]>>b[i];
for( int m=1; ; m ){
sum = 0;
for(int k=0;k <n;k ){
if((m-b[k])%a[k]==0)
sum ;
}
if (sum == n)
break;
}
cout < <m < <endl;
return 0;
}

网友回复:

C/C code






Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/





#include <iostream>

using namespace std;

bool Have_seven(int i)

{

    while(i/10)

    {

        if((i)==7)

            return true;

        i=i/10;

    }

    return false;

}

int main()

{

    int size;

    cin>>size;

    for(int i=7;i<size;i  )

    {

        if(i%7==0)

            cout<<i<<endl;

        else

            if(Have_seven(i))

                cout<<i<<endl;

    }

    return 1;

}

网友回复:

C/C code






Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/





// The Second

#include <iostream>

using namespace std;

struct ab

{

    int a;

    int b;

};

bool Is_Mod(int i,ab *p,int size)

{

    for(int j=0;j<size;j  )

    {

        if(i%p[j].a!=p[j].b)

            return false;;

    }

    return true;

}

int main()

{

    int size;

    cin>>size;

    if(size>10)

        cout<<"Input Error!"<<endl;

    ab  * vertex=new ab[size];

    for(int i=0;i<size;i  )

    {

        cin>>vertex[i].a>>vertex[i].b;

    }

    int y=1;

    while(1)

    {

        if(Is_Mod(y,vertex,size))

        {

            cout<<y<<endl;

            break;

        }

        y  ;

    }

    return 1;

}

网友回复:尊敬的5楼先生,谢谢你的回答,我仔细分析了你的回答以后您的算法设计确实巧妙,但是有一点小小的瑕疵,就是当最高位为7时的数字,不会输出,显然这也是和7有关,应当输出的,例如输入72,输出别的都是对的就是少了71.
C/C code
#include <iostream>
using namespace std;
bool Have_seven(int i)
{
while(i/10)
{
if((i)==7)
return true;
i=i/10;
}
//就是加了下面几行,即可解决问题
if (i=7)
return true;
return false;
}
int main()
{
int size;
cin>>size;
for(int i=7;i <size;i )
{
if(i%7==0)
cout < <i < <endl;
else
if(Have_seven(i))
cout < <i < <endl;
}
return 1;
}

谢谢您的回答,明天继续研究您的第二个回复.
诚拜师傅,收者发信.

网友回复:

C/C code






Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/



#include <stdio.h>



int main()

{

    int n,tmp,flag;

    while(scanf("%d",&n)!=EOF)

    {

        tmp = n;

        if(tmp < 7) continue;

        for(tmp = 7; tmp <= n;   tmp)

            if(tmp%7 == 0)

            {

                printf("%d\n",tmp);

            }

            else

            {

                flag = 0;

                int _tmp = tmp;

                while(_tmp!=0)

                {

                    if(_tmp % 10 == 7)

                    {

                        flag = 1;

                        break;

                    }

                    _tmp /= 10;

                }

                if(flag)printf("%d\n",tmp);

            }

    }

}

输入：
72
输出：
7
14
17
21
27
28
35
37
42
47
49
56
57
63
67
70
71
72
网友回复:

C/C code






Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/





#include <iostream>

using namespace std;

bool Have_seven(int i)

{

    while(i/10)

    {

        if((i)==7)

            return true;

        i=i/10;

    }

    if(i==7)// 嗯对了 是这样的，我没考虑周全，给你带了困恼！I' am sorry!

        return true;

    return false;

}

int main()

{

    int size;

    cin>>size;

    for(int i=1;i<size;i  )

    {

        if(i%7==0)

            cout<<i<<endl;

        else

            if(Have_seven(i))

                cout<<i<<endl;

    }

    return 1;

}

网友回复:呵呵,谢谢大家了,共同交流.
网友回复:第一道题应该采用数字规律
否则ACM得不到奖

由于N < 30000,规模小，采用flag 标记
bool flag[N 1];
memset(flag, 0, N 1);

1、7的倍数
7 * n ( n = 1, 2, ..., N / 7)，

2、含7的数

直接找到含7的数字段，采用对该段flag设置true

最后检查flag，true均输出

第二道：
同样是数字规律
由于ai互素
先对ai排序，
以最大的为基础循环，
a0 > a1 > a2 > ... > an

k = 1
found = false;
while (!found)
{
num = a0 * k b0;
for (i = 1; i <= n; i )
{
if ((num-bi) % ai == 0)
{
found = true;
break;
}
}
}
这样的速度最快
网友回复:2、含7的数

直接找到含7的数字段，采用对该段flag设置true

最后检查flag，true均输出

第二道：
同样是数字规律
由于ai互素
先对ai排序，
以最大的为基础循环，
a0 > a1 > a2 > ... > an

num = a0 b0;
found = false;
while (!found)
{
num = a0;
for (i = 1; i <= n; i )
{
if ((num-bi) % ai == 0)
{
found = true;
break;
}
}
}
这样的速度最快

关键字：解道,ACM,

网友评论加入收藏错误报告论坛讨论关闭此页

上一篇：求ACM试题

下一篇：下面没有链接了

·求ACM试题 (2008-06-02)

·怎么把用SQLserver 2005里的数据 (2008-06-02)

·怎么在VC使用用skinmagic的皮肤？ (2008-06-02)

·NMAKE : fatal error U1073: don (2008-06-02)

·内存问题？ (2008-06-02)

·一星期挣了三个 (2008-06-02)

·对clazzgetResource( (2008-06-02)

·override 和 overload (2008-06-02)