acm编程作业练习题.doc

杭电：1000 A + B Problem41001 Sum Problem51002 A + B Problem II61005 Number Sequence81008 Elevator91009 FatMouse Trade111021 Fibonacci Again121089 A+B for Input-Output Practice (I)141090 A+B for Input-Output Practice (II)151091 A+B for Input-Output Practice (III)161092 A+B for Input-Output Practice (IV)171093 A+B for Input-Output Practice (V)181094 A+B for Input-Output Practice (VI)191095 A+B for Input-Output Practice (VII)211096 A+B for Input-Output Practice (VIII)221176 免费馅饼231204 糖果大战251213 How Many Tables262000 ASCII码排序322001 计算两点间的距离342002 计算球体积352003 求绝对值362004 成绩转换372005 第几天？382006 求奇数的乘积402007 平方和与立方和412008 数值统计422009 求数列的和432010 水仙花数442011 多项式求和462012 素数判定472014 青年歌手大奖赛_评委会打分492015 偶数求和502016 数据的交换输出522017 字符串统计542019 数列有序!552020 绝对值排序562021 发工资咯：）582033 人见人爱A+B592037 今年暑假不AC612039 三角形632040 亲和数642045 不容易系列之(3) LELE的RPG难题652049 不容易系列之(4)考新郎662056 Rectangles682073 无限的路692084 数塔712201 熊猫阿波的故事722212 DFS732304 Electrical Outlets742309 ICPC Score Totalizer Software752317 Nasty Hacks772401 Baskets of Gold Coins782500 做一个正气的杭电人792501 Tiling_easy version802502 月之数812503 a/b + c/d812504 又见GCD832519 新生晚会842520 我是菜鸟，我怕谁852521 反素数862522 A simple problem882523 SORT AGAIN892524 矩形A + B902535 Vote912537 8球胜负932539 点球大战952547 无剑无我982548 两军交锋992549 壮志难酬1002550 百步穿杨1012551 竹青遍野1032552 三足鼎立1042553 N皇后问题1052554 N对数的排列问题1062555 人人都能参加第30届校田径运动会了1072560 Buildings1102561 第二小整数1122562 奇偶位互换1132563 统计问题1142564 词组缩写1152565 放大的X1172566 统计硬币1182567 寻梦1192568 前进1212569 彼岸1232700 Parity1242577 How to Type126北京大学：1035 Spell checker1291061 青蛙的约会1331142 Smith Numbers1361200 Crazy Search1391811 Prime Test1412262 Goldbachs Conjecture1462407 Relatives1502447 RSA1522503 Babelfish1562513 Colored Sticks159ACM算法：kurXX最小生成树163Prim164堆实现最短路166最短路DIJ普通版167floyd168BELL_MAN168拓扑排序169DFS强连通分支170最大匹配172还有两个最大匹配模板173最大权匹配,KM算法175两种欧拉路177无向图：177有向图：178【最大流】Edmonds Karp178dinic179【最小费用最大流】Edmonds Karp对偶算法181ACM题目：【题目】排球队员站位问题182【题目】把自然数分解为若干个自然数之和。184【题目】把自然数分解为若干个自然数之积。185【题目】马的遍历问题。185【题目】加法分式分解。186【题目】地图着色问题189【题目】放置方案191【题目】找迷宫的最短路径。194【题目】火车调度问题195【题目】农夫过河。197【题目】七段数码管问题。199【题目】 求相邻的格的数不连续200【题目】 棋盘上放棋子202【题目】迷宫问题.204【题目】一笔画问题205【题目】城市遍历问题.207【题目】棋子移动问题208【题目】求集合元素问题（1,2x+1,3X+1类)209杭电：1000 A + B ProblemProblem DescriptionCalculate A + B.InputEach line will contain two integers A and B. Process to end of file.OutputFor each case, output A + B in one line.Sample Input1 1Sample Output2AuthorHDOJ代码：#includeint main() int a,b; while(scanf(%d %d,&a,&b)!=EOF) printf(%dn,a+b);1001 Sum ProblemProblem DescriptionHey, welcome to HDOJ(Hangzhou Dianzi University Online Judge).In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + . + n.InputThe input will consist of a series of integers n, one integer per line.OutputFor each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer.Sample Input1100Sample Output15050AuthorDOOM III解答：#includemain() int n,i,sum; sum=0; while(scanf(%d,&n)!=-1) sum=0; for(i=0;i=n;i+) sum+=i; printf(%dnn,sum); 1002 A + B Problem IIProblem DescriptionI have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.InputThe first line of the input contains an integer T(1=T=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.OutputFor each test case, you should output two lines. The first line is Case #:, # means the number of the test case. The second line is the an equation A + B = Sum, Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.Sample Input21 2112233445566778899 998877665544332211Sample OutputCase 1:1 + 2 = 3Case 2:112233445566778899 + 998877665544332211 = 1111111111111111110AuthorIgnatius.L代码：#include #include int main() char str11001, str21001; int t, i, len_str1, len_str2, len_max, num = 1, k; scanf(%d, &t); getchar(); while(t-) int a1001 = 0, b1001 = 0, c1001 = 0; scanf(%s, str1); len_str1 = strlen(str1); for(i = 0; i = len_str1 - 1; +i) ai = str1len_str1 - 1 - i - 0; scanf(%s,str2); len_str2 = strlen(str2); for(i = 0; i len_str2) len_max = len_str1; else len_max = len_str2; k = 0; for(i = 0; i = 0; -i) printf(%d, ci); printf(n); if(t = 1) printf(n); return 0;1005 Number SequenceProblem DescriptionA number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2) mod 7.Given A, B, and n, you are to calculate the value of f(n).InputThe input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 = A, B = 1000, 1 = n = 100,000,000). Three zeros signal the end of input and this test case is not to be processed.OutputFor each test case, print the value of f(n) on a single line.Sample Input1 1 31 2 100 0 0Sample Output25AuthorCHEN, ShunbaoSourceZJCPC2004 RecommendJGShining代码：#includeint f200;int main() int a,b,n,i; while(scanf(%d%d%d,&a,&b,&n)&a&b&n) if(n=3) f1=1;f2=1; for(i=3;i=200;i+) fi=(a*fi-1+b*fi-2)%7; if(fi-1=1&fi=1) break; i-=2; n=n%i; if(n=0) printf(%dn,fi); else printf(%dn,fn); else printf(1n); return 0;1008 ElevatorProblem DescriptionThe 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.InputThere 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.OutputPrint the total time on a single line for each test case. Sample Input1 23 2 3 10Sample Output1741AuthorZHENG, JianqiangSourceZJCPC2004 RecommendJGShining代码：#includeint a110;int main() int sum,i,n; while(scanf(%d,&n)&n!=0) for(i=1;i=n;i+) scanf(%d,&ai); sum=0; a0=0; for(i=1;iai-1) sum+=6*(ai-ai-1); else sum+=4*(ai-1-ai); sum+=5; printf(%dn,sum); return 0;1009 FatMouse TradeProblem DescriptionFatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.The warehouse has N rooms. The i-th room contains Ji pounds of JavaBeans and requires Fi pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get Ji* a% pounds of JavaBeans if he pays Fi* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.InputThe input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers Ji and Fi respectively. The last test case is followed by two -1s. All integers are not greater than 1000.OutputFor each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.Sample Input5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1Sample Output13.333 31.500AuthorCHEN, YueSourceZJCPC2004RecommendJGShining代码：#include#include#define MAX 1000int main() int i,j,m,n,temp; int JMAX,FMAX; double PMAX; double sum,temp1; scanf(%d%d,&m,&n); while(m!=-1&n!=-1) sum=0; memset(J,0,MAX*sizeof(int); memset(F,0,MAX*sizeof(int); memset(P,0,MAX*sizeof(double); for(i=0;in;i+) scanf(%d%d,&Ji,&Fi); Pi=Ji*1.0/(double)Fi); for(i=0;in;i+) for(j=i+1;jn;j+) if(PiPj) temp1=Pi; Pi=Pj; Pj=temp1; temp=Ji; Ji=Jj; Jj=temp; temp=Fi; Fi=Fj; Fj=temp; for(i=0;in;i+) if(m=2).InputInput consists of a sequence of lines, each containing an integer n. (n 1,000,000).OutputPrint the word yes if 3 divide evenly into F(n).Print the word no if not.Sample Input012345Sample OutputnonoyesnononoAuthorLeojayRecommendJGShining#includeint main() long n; while(scanf(%ld,&n) != EOF) if (n%8=2 | n%8=6) printf(yesn); else printf(non); return 0;1089 A+B for Input-Output Practice (I)Problem DescriptionYour task is to Calculate a + b.Too easy?! Of course! I specially designed the problem for acm beginners. You must have found that some problems have the same titles with this one, yes, all these problems were designed for the same aim. InputThe input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line. OutputFor each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input. Sample Input1 510 20Sample Output630AuthorlcyRecommendJGShining解答：#include main() int a,b; while(scanf(%d%d,&a,&b)!=EOF) printf(%dn,a+b); 1090 A+B for Input-Output Practice (II)Problem DescriptionYour task is to Calculate a + b.InputInput contains an integer N in the first line, and then N lines follow. Each line consists of a pair of integers a and b, separated by a space, one pair of integers per line. OutputFor each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input. Sample Input21 510 20Sample Output630AuthorlcyRecommendJGShining 解答：#include#define M 1000void main() int a ,b,n,jM,i; /printf(please input n:n); scanf(%d,&n); for(i=0;in;i+) scanf(%d%d,&a,&b); /printf(%d %d,a,b); ji=a+b; i=0; while(in) printf(%d,ji); i+; printf(n); 1091 A+B for Input-Output Practice (III)Problem DescriptionYour task is to Calculate a + b.InputInput contains multiple test cases. Each test case contains a pair of integers a and b, one pair of integers per line. A test case containing 0 0 terminates the input and this test case is not to be processed.OutputFor each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input. Sample Input1 510 200 0Sample Output630AuthorlcyRecommendJGShining解答：#include main() int a,b; scanf(%d %d,&a,&b); while(!(a=0&b=0) printf(%dn,a+b); scanf(%d %d,&a,&b); 1092 A+B for Input-Output Practice (IV)Problem DescriptionYour task is to Calculate the sum of some integers.InputInput contains multiple test cases. Each test case contains a integer N, and then N integers follow in the same line. A test case starting with 0 terminates the input and this test case is not to be processed.OutputFor each group of input integers you should output their sum in one line, and with one line of output for each line in input. Sample Input4 1 2 3 45 1 2 3 4 50 Sample Output1015AuthorlcyRecommendJGShining解答：#include int main() int n,sum,i,t; while(scanf(%d,&n)!=EOF&n!=0) sum=0; for(i=0;in;i+) scanf(%d,&t); sum=sum+t; printf(%dn,sum); 1093 A+B for Input-Output Practice (V)Problem DescriptionYour task is to calculate the sum of some integers.InputInput contains an integer N in the first line, and then N lines follow. Each line starts with a integer M, and then M integers follow in the same line. OutputFor each group of input integers you should output their sum in one line, and with one line of output for each line in input. Sample Input24 1 2 3 45 1 2 3 4 5Sample Output1015Authorlcy解答：#includemain() int n,a,b,i,j,sum; sum=0; while(scanf(%dn,&n)!=-1) for(i=0;in;i+) scanf(%d,&b); for(j=0;jb;j+) scanf(%d,&a); sum+=a; printf(%dn,sum); sum=0; 1094 A+B for Input-Output Practice (VI)Problem DescriptionYour task is to calculate the sum of some integers.InputInput contains multiple test cases, and one case one line. Each case starts with an integer N, and then N integers follow in the same line. OutputFor each test case you should output the sum of N integers in one line, and with one line of output for each line in input. Sample Input4 1 2 3 45 1 2 3 4 5Sample Output1015AuthorlcyRecommendJGShining解答：#includemain() int n,a,b,i,j,sum; sum=0; while(scanf(%dn,&n)!=-1) for(j=0;jn;j+) scanf(%d,&a); sum+=a; printf(%dn,sum); sum=0; Copy to Clipboard Save to File1095 A+B for Input-Output Practice (VII)Problem DescriptionYour task is to Calculate a + b.InputThe input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line. OutputFor each pair of input integers a and b you should output the sum of a and b, and followed by a blank line. Sample Input1 510 20Sample Output630AuthorlcyRecommendJGShining解答：#include main() int a,b; while(scanf(%d%d,&a,&b)!=EOF) printf(%dnn,a+b); 1096 A+B for Input-Output Practice (VIII)Problem DescriptionYour task is to calculate the sum of some integers.InputInput contains an integer N in the first line, and then N lines follow. Each line starts with a integer M, and then M integers follow in the same line. OutputFor each group of input integers you should output their sum in one line, and you must note that there is a blank line between outputs.Sample Input34 1 2 3 45 1 2 3 4 53 1 2 3Sam