杭电acm部分答案.doc

Problem DescriptionCalculateA + B.InputEach line will contain two integersAandB. Process to end of file.OutputFor each case, outputA + Bin one line.Sample Input1 1Sample Output2#include void main() int a,b; while(scanf(%d %d,&a,&b)!=EOF) printf(%dn,a+b); Problem 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 Output15050#include void main() int n,sum,i; while(scanf(%d,&n)!=EOF) sum=0; for( i=0;i=n;i+) sum+=i; printf(%dnn,sum); Problem 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 = 1111111111111111110#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;elselen_max = len_str2;k = 0;for(i = 0; i = 0; -i)printf(%d, ci);printf(n);if(t = 1)printf(n);return 0;Problem DescriptionGiven a sequence a1,a2,a3.an, your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.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 starts with a number N(1=N=100000), then N integers followed(all the integers are between -1000 and 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 contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.Sample Input25 6 -1 5 4 -77 0 6 -1 1 -6 7 -5Sample OutputCase 1:14 1 4Case 2:7 1 6注：最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如5,-3,4,2的最大子序列就是 5,-3,4,2，它的和是8,达到最大；而 5,-6,4,2的最大子序列是4,2，它的和是6。你已经看出来了，找最大子序列的方法很简单，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列#includeint a100005,str100005,start100005;int main()int t,n,i,num=1,end,max,k;scanf(%d,&t);while(t-)scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai); str1=a1;start1=1;for(i=2;i=0)stri=stri-1+ai;starti=starti-1;elsestri=ai;starti=i;max=str1;end=1;for(k=2;kmax)max=strk;end=k;printf(Case %d:n,num);num+;printf(%d %d %dn,max,startend,end);if(t) printf(n);return 0;Problem DescriptionContest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.This year, they decide to leave this lovely job to you.InputInput contains multiple test cases. Each test case starts with a number N (0 N = 1000) - the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.A test case with N = 0 terminates the input and this test case is not to be processed.OutputFor each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.Sample Input5greenredblueredred3pinkorangepink0Sample Outputredpink#include#includechar a100015;int b1000;int main()int n,i,j,max,k;while(scanf(%d,&n)!=EOF)if(n=0) break; for(i=1;i=n;i+) bi=0; scanf(%s,ai); /二维数组的神奇用法for(i=1;i=n;i+) for(j=1;j=n;j+) if(strcmp(ai,aj)=0) bi+; max=b1;k=1;for(i=2;imax)max=bi;k=i; printf(%sn,ak); return 0;Problem 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 Output25方法1：注函数介绍void *memset(void *s, int ch, size_t n);函数解释：将s中前n个字节替换为ch并返回s；memset:作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。#include #include int main() int b77; int a100; int n; int x, y, m, st, len; while (scanf(%d %d %d, &x, &y, &m) = 3) if (x=0 & y=0 & m=0) break; a1 = 1; a2 = 1; memset(b, 0, sizeof(b); b11 = 1; n = 3; for (;) an = (an-1*x+an-2*y)%7; if (ban-1an != 0) break; ban-1an = n-1; +n; /计算周期 st = ban-1an; len = n-1-st;/len为周期 if (m st) printf(%dn, am); else printf(%dn, ast+(m-st)%len); return 0;方法二简单递归应为模运算中（a+b）%p=(a%p+b%p)%p;所以循环周期为7*7=49；#includeint a,b;int f(int n) if(n=2|n=1) return 1; else return (a*f(n-1)+b*f(n-2)%7;main() while(scanf(%d%d,&a,&b)!=EOF&a&b) _int64 n; int m; scanf(%I64d,&n); m=n%49; printf(%dn,f(m); Problem DescriptionThe three hands of the clock are rotating every second and meeting each other many times everyday. Finally, they get bored of this and each of them would like to stay away from the other two. A hand is happy if it is at least D degrees from any of the rest. You are to calculate how much time in a day that all the hands are happy.InputThe input contains many test cases. Each of them has a single line with a real number D between 0 and 120, inclusively. The input is terminated with a D of -1.OutputFor each D, print in a single line the percentage of time in a day that all of the hands are happy, accurate up to 3 decimal places.Sample Input012090-1Sample Output100.0000.0006.251这个钟是个物理的钟，也就是说秒针每一秒走6度之后，分针就走了10分之1度，然后时针又走了120分之1度，当然钟表盘一圈是360度了或者还可以继续拆，秒针每千分之一秒走千分之6度，然后分针就走万分之1度，时针就走十二万分之1度，就这样只要知道他是一个连续的钟，那就什么都好解决了首先我们有一个东西是必然可以知道的，在0点的时候三根针是重合的，然后在12点的时候三跟针就又重合了（操，我最开始的时候居然想的是24的时候三根针才再次重复），也就是说一天被分为两个周期，每个周期12个小时。所以，只要我们求出在一个周期中三根针满足条件的总时间，我们就可以知道一天中三根针满足条件的总时间。所占百分比也自然就出来了好了，这东西肯定不能暴力，如果你按一秒为梯度来暴力解出每一秒的时候三根针之间的间距，然后把总时间求和，精度肯定不够，甚至可能是错误的解，当然，如果你以万分之一秒为梯度来暴力求解的话，那有可能就达到题目的精度了，但是，多半也就超时了所以，就只有解方程了好，最开始我想的是用三个方程，分别表示三根针随时间的变化的角度的变化，就是说第0秒秒针的角度是0度，第1秒是6度，第30秒是180度，第59秒时60-6度然后把两跟针的度数相减，就得到了他们之间相距的角度不过，我发现这个好麻烦而且整个方程和给定的角度D完全没有关系，也很难根据那个D来解出我们想要的结果所以，换了，将方程改为随时间变化的针之间相距的角度的方程，也是三个。首先，我们知道每根针的角速度：Vs = 6度每秒 （60秒走一圈360度 360/60=6）Vm = 1/10度每秒（3600秒，一个小时走一圈， 360/3600=0.1）Vh = 1/120度每秒（12小时走一圈，360/（3600*12）= 1/120）然后，就可以得到每两根之间的速度差了：Vsm = Vs - Vm = 6 - 1/10 = 59/10Vsh = Vs - Vh = 6 - 1/120 = 719/120Vmh = Vm - Vh = 1/10 - 1/120 = 11/120然后，时间乘以速度等于距离。然后我们可以算出来：秒针和分针之间的夹角在时间t = 0的时候是0度，在t = 1800/59（59分之1800秒）的时候达到最大值180度，然后从59分之1800秒开始就开始减少，当时间t到达59分之3600秒的时候，秒针和分针之间的夹角就又是0度了。（算法：Vsm * t = 180 ，所以 t = 180/Vsm = 180 /（59/10） = (180 * 10)/ 59时针和秒的0度-180度-0度这三个点的时间t分别是 0, 120*180/719, 120*180*2/719时针和分针:0, 180*120/11, 180*120*2/11所以：Dsm = (59/10) * t 或者 360 - (59/10) * tDsh = (719/120) * t 或者 360 - (719/120) * tDmh = (11/120) * t 或者 360 - (11/120) * t#includedouble max(double a,double b,double c)a=ab?a:b;a=ac?a:c;return a;double min(double a,double b,double c)a=ab?a:b;a=a43200&dsmj43200)break;for(i=2,j=3;i+=2,j+=2)dshi=dshi-2+tsh;dshj=dshj-2+tsh;if(dshi43200&dshj43200)break;for(i=2,j=3;i+=2,j+=2)dmhi=dmhi-2+tmh;dmhj=dmhj-2+tmh;if(dmhi43200&dmhj43200)break; sp0=mp0=hp0=0; sp1=mp1=hp1=1; while(y=43200 & x=43200) x=max(dsmsp0,dshmp0,dmhhp0); y=min(dsmsp1,dshmp1,dmhhp1); if(xy) sum+=y-x; if(y=dsmsp1) sp0+=2;sp1+=2; if(y=dshmp1) mp0+=2;mp1+=2; if(y=dmhhp1) hp0+=2;hp1+=2; printf(%.3lfn,sum/432); （不会）Problem DescriptionHave you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.InputThe input consists of several test cases. For each case, the first line contains an integer N (2 = N = 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.OutputFor each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.Sample Input20 01 121 11 13-1.5 00 00 1.50Sample Output0.710.000.75#include #include #include #include #include using namespace std;const int maxn=100011;int n;int qmaxn;double xmaxn,ymaxn;inline double dis( double x1, double y1, double x2, double y2 ) return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );void qsortX( int l, int r )/对?数y组进?行D排?序（横坐?标从小?到?大）? int i=l, j=r; double mid=x(l+r)/2; do while ( ximid ) j-; if ( i=j ) swap( xi, xj ); swap( yi, yj ); i+; j-; while ( i=j ); if ( ir ) qsortX( i, r ); if ( lj ) qsortX( l, j );void qsortY( int l, int r ) int i=l, j=r; double mid=yq(l+r)/2; do while ( yqimid ) j-; if ( i=j ) swap( qi, qj ); i+; j-; while ( i=j ); if ( ir ) qsortY( i, r ); if ( lj ) qsortY( l, j );double findMin( int l, int r ) if ( l=r ) return 99999999; if ( l+1=r ) return dis( xl, yl, xr, yr ); double t1=findMin( l, (l+r)/2 ),/递Y归，?分?治?思?想?，?把?大问题a看若?干个?小?问题a t2=findMin( (l+r)/2+1, r ), mid=(xl+xr)/2, min; if ( t1t2 ) min=t1; else min=t2;/最?小?距离?在A或B里?情况?下? int tot=0; for ( int i=l; i=r; i+ ) if ( fabs( xi-mid )min ) q+tot=i; qsortY( 1, tot ); for ( int i=1; i=tot; i+ ) for ( int j=i+1; jtot ) break; double t=dis( xqi, yqi, xqj, yqj ); if ( tmin ) min=t; return min;void readdata() for ( int i=1; i=n; i+ ) scanf( %lf%lf, &xi, &yi );int main() while ( scanf( %d, &n ) ) if ( n=0 ) break; readdata(); qsortX( 1, n ); double ans=findMin( 1, n ); printf( %.2fn, ans/2 ); return 0;Problem 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 Output1741#include#includevoid main()int n,i,time;int length101=0;while(scanf(%d,&n)!=EOF)time=0;if(n=0)break;for(i=1;i=n;i+)scanf(%d,&lengthi);for(i=0;i=0)time+=6*(lengthi+1-lengthi)+5;elsetime+=4*(abs(lengthi+1-lengthi)+5;printf(%dn,time);Problem 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 las