当前位置:首页 >> IT/计算机 >> ACM简单计算题

ACM简单计算题


ACM算法与程序设计
第二讲

简单计算题(一)

数学科学学院:汪小平 wxiaoping325@163.com

最大公约数与最小公倍数1235
? Problem Description

任给两个正整数,求两数的最大公约数与最小公 倍数。 。 ? Input 有多组测试数据。输入的第一行是整数T (0<T<=1000),表示测试数据的组数。每一组测 试数据只有一行,分别为整数a和b,两数之间有一 个空格。0<a,b<=32767。 ? Output 对应每组输入,输出一行对应两数的最大公约数 和最小公倍数,两数之间用一个空格隔开。
2/42

? Sample input:

1 12 44
? Sample output:

4 132

3/42

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

#include <stdio.h> int gcd(int, int); int main() { int T; 有没有问题 int a,b,r,s; 呢? scanf("%d",&T); while(T--) { scanf("%d %d",&a,&b); s=gcd(a,b); printf("%d %d\n",s,a*b/s); } return 0; }
4/42

? int gcd(int a, int b) ? { ? int r; ? if(a<b) ? { ? r=a; ? a=b; ? b=r; ? } ? do ? { ? r=a%b; ? a=b; ? b=r; ? }while(b!=0); ? return a; ? }

5/42

欧几里德算法
只要两数不相等,就反复用大数减小数,直到相等为 止,此相等的数就是两数的最大公约数。
? int gcd(int x,int y) ? { ? while (x!=y) ? { ? if (x>y) x=x-y; ? else ? y=y-x; ? } ? return x; ? }
6/42

Fibonacci Again
http://acm.hdu.edu.cn/showproblem.php?pid=1021

7/42

? Problem Description There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2). ? Input Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000). ? Output Print the word "yes" if 3 divide evenly into F(n). Print the word "no" if not.

8/42

? Sample input: 0123456 ? Sample output: no no yes no no no yes

9/42

题目分析
? 能被3整除的整数的特点? ? 如果两个数的和能被3整除,这两个数有什么特点?

? 关于能否被3整除,这两个数一共有多少种组合?

还要看程序吗?
10/42

程序清单:
#include<stdio.h> int main() { long n; while(scanf("%ld",&n) == 1) if (n%8==2 || n%8==6) printf("yes\n"); else printf("no\n"); return 0; }

11/42

鸡兔同笼
? http://poj.grids.cn/practice/2750

12/42

? Problem Description
一个笼子里面关了鸡和兔子(鸡有2只脚,兔子有4只脚, 没有例外)。已经知道了笼子里面脚的总数a,问笼子里 面至少有多少只动物,至多有多少只动物。

? Input
第1行是测试数据的组数n,后面跟着n行输入。每组测试 数据占1行,每行一个正整数a (a < 32768)。

? Output
输出包含n行,每行对应一个输入,包含两个正整数,第一 个是最少的动物数,第二个是最多的动物数,两个正整数 用一个空格分开 。如果没有满足要求的答案,则输出两个 0。
13/42

? Sample input: 2 3 20 ? Sample output: 00 5 10

14/42

#include<stdio.h> int main() { int nCases,I,nFeet; //InCases表示输入测试数据的组 数,nFeet表示输入的脚数 scanf(“%d”, &nCases); for(i=0; i<nCases; i++) { scanf((“%d”,& nFeet); if(nFeet % 2 !=0) //如果有奇数只脚,则没有满足题 意的答案,因为不论2只还是4只,都是偶数 printf(“0 0\n”); else if(nFeet % 4 !=0) //若要动物最少,使动物尽量有4只脚, //若要动物最多,使动物尽量有2只脚 printf(“%d %d\n”, nFeet / 4 + 1, nFeet / 2); else printf(“%d %d\n”, nFeet / 4, nFeet / 2); } return 0; }
15/42

Elevator
http://acm.hdu.edu.cn/showproblem.php? pid=1008

16/42

题目评述

这是2004浙江省省赛最简单的一题,当时训练 水平相对较高的队员基本上10分钟之内解决该题, 这是一个没有算法的简单模拟题目。 入门训练的好选择~

17/42

? Problem Description The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.
For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled. ? Input There are multiple test cases. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed. ? Output Print the total time on a single line for each test case.
18/42

? Sample input: 12 3231 0 ? Sample output: 17 41

19/42

#include <stdio.h> int main(void) { int n, i, a[101], value, sum; while(scanf("%d",&n) && n!=0) { a[0] = 0; for(i = 1; i <= n; i++) { scanf("%d",&value); a[i]=value; } sum = n * 5; for(i = 0; i < n; i++) { if(a[i]<a[i+1]) sum = sum + (a[i+1]-a[i])*6; else if(a[i]>a[i+1]) sum = sum + (a[i]-a[i+1])*4; } printf("%d\n", sum); } return 0; }
20/42

Rightmost Digit
? http://acm.hdu.edu.cn/showproblem.php?pid =1061

21/42

? Problem Description Given a positive integer N, you should output the most right digit of N^N. ? Input The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.Each test case contains a single positive integer N(1<=N<=1,000,000,000). ? Output For each test case, you should output the rightmost digit of N^N.
22/42

? Sample input: 2 3 4 ? Sample output: 7 6

23/42

?数据规模? 很大 ?暴力方法? 该打 ?基本思路? 规律

24/42

#include<stdio.h> int main(void) { int T,i,a,digit; int n; scanf("%d",&T); for(i=0;i<T;i++) { scanf("%d",&n); a=n%10; if(a==0||a==1||a==5 ||a==6||a==9) digit=a; else if(a==2) { if(n%4==0) digit=6; else digit=4; }

else if(a==3) { if(n%4==1) digit=3; else digit=7; } else if(a==4) digit=6; else if(a==7) { if(n%4==1) digit=7; else digit=3; } else //a=8 { if(n%4==0) digit=6; else digit=4; } printf("%d\n",digit); } return 0;}
25/42

偏僻的小路
1、Link
http://acm.uestc.edu.cn/problem.php?pid=1025

2、Description
在电子科大清水河校区的某个偏僻角落里,有一条东西方 向的小路,长L米(由西向东位置为0到L),小路上有N个人 从t=0秒开始以相同的恒定速率V米/秒前进(面朝西或面朝 东)。这条小路太偏僻了,所有人都想尽快离开这条小路。 不幸的是,当两个人相遇时,只有男生会给女生让路(视为 两人擦肩而过),男生遇上男生、女生遇上女生时,谁也不 肯让路,只好都无奈的掉头往回走。 现在HS很好奇,想知道最后一个人离开小路的时间,以及 所有人在小路上走的路程的总和,你能编写程序帮助他吗?
26/42

偏僻的小路
3、Input 第一行包括3个整数,N,L,V,表示小路上的人数、小路的长 度、所有人前进的速率 (N<=100, L<= 1000000,V>0) 接下来有N行,每行3个数据,第i行的数据表示第i个人的 位置(从0到L的整数)、性别(M或F)、方向(W表示面 朝西、E表示面朝东) 当N=L=V=0时,输入结束 4、Output 对于每组输入,输出一行两个小数,表示最后一个人离开 的时间以及所有人在小路上走的路程的总和,用一个空格隔 开,答案四舍五入保留两位小数 。

27/42

偏僻的小路
5、Sample Input 242 1ME 3MW 000 6、Sample Output 1.50 6.00

7、Source royce
28/42

偏僻的小路

分析

29/42

#include <stdio.h> int N, L, V, pos; char sex[4], dir[4]; int main() { double last, dist;//最后时间与路程 double len;//当前人的路程 while (scanf("%d %d %d", &N, &L, &V) != EOF) { if (N == 0 && L == 0 && V == 0) break; last = 0.0, dist = 0.0;//清零 for (int i = 0; i < N; i++) { scanf("%d %s %s", &pos, sex, dir); if (dir[0] == 'W') len = pos; else len = L - pos; if (len / V > last) last = len / V; dist += len; } printf("%.2f %.2f\n", last, dist); } return 0; }

偏僻的小路

30/42

约会
1、Link
http://acm.uestc.edu.cn/problem.php?pid=1033

2、Description
有一天silentsky和lcy同学去教室上自习。silentsky百无聊赖地看 着书本,觉得很无聊,看着右手边的lcy认真仔细的在画着她繁重 的物理实验报告的图。silentsky无聊地弄着他的脉动瓶子,结果一 不小心就把瓶盖弄到了lcy刚画好的坐标纸上,而且冥冥之中仿佛 有一双手在安排,瓶盖的中心正好和坐标纸的中心重合了,瓶盖的 边缘有水,会弄湿坐标纸的。 lcy很生气,后果很严重。 于是,lcy由此情形想出了一道难题问silentsky,如果他回答正确了。 lcy就原谅了silentsky并且答应他星期天去看暮光之城2的请求,不 然一切都免谈。然后silentsky就回去面壁思过了,现在silentsky好 无助的,希望得到广大编程爱好者的好心帮助。
31/42

约会
问题是这样的: lcy现在手上有一张2n * 2n的坐标纸,而 silentsky的圆形瓶盖的直径正好有2*n-1大,现在lcy想知道 silentsky到底弄湿了多少个坐标纸的格子(坐标纸是由1 * 1的 小格子组成的表格) 如果还是有人觉得理解不了焦急的silentsky的意思。干脆 silentsky做下翻译,毕竟silentsky还是多了解lcy的O(∩_∩)O~。

问题就是给你一个2n * 2n的正方形格子,分成1 * 1的格子, 然后以中心为原点画一个直径为2n - 1的圆,问圆的周线穿过 了多少个格子。

32/42

约会
3、Input 含有多组测试数据,每组数据都包含一个正 整数n(n <= 1000)。 当n = 0的时候结束程序,证明silentky经受 住考验了的O(∩_∩)O~ 4、Output 对于每个n,输出被瓶盖边缘的水弄湿了的格 子数为多少。

33/42

约会
5、Sample Input 1 2 0 6、Sample Output 4 12

7、Source love8909 & silentsky
34/42

约会

分析

35/42

约会
#include<stdio.h>
int main()

{
int n; while(scanf("%d", &n)!=EOF&&n) printf("%d\n", n*8-4); return 0; }
36/42

The Story of ZCS
1、Link
http://acm.uestc.edu.cn/problem.php?pid=1088

2、Description
Love and Eternal lay hid in night; God said "Let CS be" and all was light. Walking alone in darkness, lonely and never knew what I would go through. How many times I walked lonely in the campus, how many times I woke up with a start at midnight, and how many times I sang a sorrow song but no one cared about? The terrible feeling is just like a albatross around my neck until I met CS. My door is opened and the sky is lightened.It is a moment for my renaissance, which makes me understand the meaning of sunshine and rainbow once again. When I catch sight of you, you are the only one in my view. When you are out of sight, you are the only one in my heart. When I am awake, you are the only one in my mind. When I am asleep, you are the only one in my dream. You are my only one.I want to catch sight of you every minute and every second. -- Letter from Kamel (ZS) to CS
37/42

The Story of ZCS
Kamel has lots of photos of CS. He wants to fill his desktop with her photos. The desktop is made up of m rows and n columns. One photo occupies b consecutive squares in a row or b consecutive squares in a column. He want to know whether it is possible to cover his desktop with CS's photos while no two photos overlap with each other and the whole desktop is full?

You may assume that Kamel has tens of thousands of photos of CS. If it is possible then print "YES" else print "NO".

38/42

The Story of ZCS
3、Input The first line of the inputs is T(no more than 120), which stands for the number of test cases you need to solve. Each line has three numbers M,N,B (1 <= M,N <= 1000, 1 <= B <= M,N). 4、Output Each "YES" or "NO" occupies one line.

39/42

The Story of ZCS
5、Sample Input

2 484 573
6、Sample Output

YES NO
7、Source

kamel
40/42

The Story of ZCS

分析 证明

41/42

The Story of ZCS
#include<stdio.h> int main() { int T,M,N,B; scanf("%d",&T); while(T--) { scanf("%d%d%d",&M,&N,&B); if(M%B==0||N%B==0) printf("YES\n"); else printf("NO\n"); } return 0; }

42/42


赞助商链接
更多相关文档:

ACM第三次培训题目及答案

当然,对于这样的简单题能通过的就是好代码。 #include <math.h> #include <...杭电ACM部分题目答案 54页 1下载券 ©2018 Baidu |由 百度云 提供计算服务 ...

acm计算几何基础题目

acm计算几何基础题目 - POJ 1113 WALL 计算几何,求凸包 这题的结果等于这个多边形构成的凸包的周长加上以所给半径为半径的圆的周长 步骤如下: 1)算法首先寻找最...

计算几何题目推荐

POJ 计算几何入门题目推荐(转) 其实也谈不上推荐,只是自己做过的题目而已,甚至有的题目尚未 AC,让在 挣扎中。之所以推荐计算几何题,是因为,本人感觉 ACM 各种...

ACM计算几何题目总结及分类

ACM计算几何题目总结及分类_数学_高中教育_教育专区。ACM计算几何题目总结及分类 ...pid=1032 简单题 最大可分离值问题 http://acm.fzu.edu.cn/problem.php?...

概率论与数理统计思考题(算是玩acm)

概率论与数理统计思考题(算是玩acm)_数学_自然科学_专业资料。20120008001 数学...如果需要计算其他概 率下的建议报价,可以运行附录代码四) 方案 A:求出下浮率的...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com