ACM入门试题Problem_Set.doc

A : 赶公交Alfred在大学新区上学，他每个星期都要到市区学琴，因此要在每个星期六的10点钟之前赶到琴行上课，从郑大坐68路车到琴行要花整整一个小时，而68路车是每半小时一趟，整点和30分的时候会发一趟车。这一次，Alfred起床晚了，一看表已经8点多了，匆忙收拾了一下之后，Alfred马上冲向公交站，但是，由于路况不佳，在前面的一段路上满是泥泞。路况如下：xyOAB如左图，A(xA,yA)是Alfred现在所处的位置，B(xB,yB)是公交站(Bus-stop)的位置，其中y0的区域是泥泞的地面，Alfred在泥泞的地面上的移动速度是v1(米/秒)，而y0的区域是水泥地，Alfred在水泥地上的移动速度只有v2(米/秒)，其中v1=v2，A在第二象限，B在第四象限。Alfred是一个物工院的学生，他稍微估算了一下，剩下的时间已经不多了，他看看表，现在离9点整只剩下T秒了 (T由题目给出)，Alfred想知道，他如果用最优的策略赶往公交站，今天的课是否会迟到。输入规格：第一行是一个整数C，C=10，紧接着C组数据，每组数据依次给出xA,yA,xB,yB,v1,v2 和T，他们的意义如上文所述，x,y坐标的单位是米，所有坐标的绝对值=10分，他这个学期就可以合格。他甚至为此充分调查了老师的点名习惯，发现如下规律：每个学期这门课程共有K个课时(K=20)，而对于某节课老师点不点名是一个独立的事件，并且老师在某一节课点名的概率是p(0.0=p=1.0)，现在fish_ball想尽可能多的逃课，但是要保证他有90%以上的概率不挂掉这门课，问fish_ball这个学期最多能翘掉多少课？输入规格：第一行是一个整数C，C=20，紧接着C组数据，每组数据包含一行，依次给出整数K (1=K=20)和p(0.0=p=1.0)，如题目中所描述。输出规格：对于每组数据，输出一个整数，表示fish_ball这学期最多能够翘掉几堂课。输入样例：44 14 020 0.520 0.2输出样例：0449出题者：黄文超C : 烦恼的中学生在郑大，很多学生都会找点兼职来赚点外快，Alfred也不例外，他找的兼职是家教。好了，现在Alfred的工作就是辅导一个高中生的数学。这一天，这位高中生叫Alfred帮忙做一下作业：在二维平面内给出一个三角形的三个顶点坐标，现在的任务是求出这个三角形的垂心，也就是三角形的三条高线所在直线的交点。当然，Alfred的数学是不错的，对于这么简单的问题，Alfred只用了半分钟就解决掉了，正当Alfred得意的时候，这位高中生却毫不吃惊地说：我们的作业一共有100条呢! Alfred听见了之后不禁倒抽了一口凉气，现在的中学生真命苦啊。所以，打抱不平的Alfred决定要帮这位高中生的忙：利用计算机程序来批量解决这个问题，但是Alfred苦思数日却没有想出来解决办法，你们能帮他这个忙吗？输入规格：第一行是一个整数C(C=100)，表示有C组测试数据，每组数据三行，每行两个浮点数分别表示三角形某个顶点的x,y坐标。所有坐标的绝对值10000。输入保证三点不共线。输出规格：对于每组输入数据，输出两个浮点数xh, yh表示所给三角形垂心的纵横坐标，保留三位小数(四舍五入)。Hint:请注意你的程序，避免输出-0.000的情况，这样系统会判错。(如果要输出一个极小的负数，如-0.000001，输出会变成-0.000，应该手动排除这种情况，确保这种时候输出0.000。)输入样例：3-10 00 1010 0-10 010 00 17.3212 104 -520 6输出样例：0.000 10.0000.000 5.7746.031 4.137出题者：黄文超D : MazeTherere many buildings in ZZU, and Alfred is new here. Today, it is the first day he is at school. Its 7:40 now, Alfred must go to the classroom at once, or hell be late. You know being late at the first class will make a bad impression on the teacher. Alfred is a good student, he will never make this happen, will he?So he hurries to the buildings where the classrooms locate at. But the problem come out, he does not know the road! This make him mad, it just like a maze!Now he turns to you, an old student at ZZU. What you should do is simple: just tell him how long the shortest path that leads him to the right classroom is. Alfred will thank you very much.Now lets describe the situation here. The map can be represented as a MN grid(2=M=50, 2=N=50). In each cell, theres a symbol: ., X, a, c, where a . means a the cell is reachable, an X represents a wall that is not reachable, and a means Alfred is at that place initially, c means the classroom.At a single minute, Alfred can go from a reachable cell to an adjacent one (to the north, west, south or east), of course, the target cell must be also reachable. So can you tell if Alfred takes the optimal path, how many minutes does he need at least to reach the classroom?Input Specification:The first line consist only one integer C(C = 10), indicates C cases follows. In each case, there are two integers M and N on the first line, as the size of the map. Then M lines follows are the given map.Output Specification:For each case, output a single line consist a single integer, represents at least how many minutes Alfred need to arrive at the class. If there is no path to the classroom, just print “No path”Sample Input:23 5a.XX.XXc.X.4 6a.X.XX.X.cX.X.XX.Sample Output:6No pathAuthor：Alfred HuangE ：生日聚会今天是JacmY生日，他请大家吃饭，就这样，一行N个人来到了餐馆，大家吃吃喝喝，有说有笑，气氛甚欢，这时突然有人提议大家玩一个游戏，听罢规则后，就开始了游戏。 游戏规则是这样的，吃饭的N个人围坐在桌子旁，JacmY是1号，沿着顺时针方向开始编号，2、3N，然后由JacmY随机说一个数K(1 = K = N)，从JacmY开始顺时针报数，“1，2”，当有人报到K时，这个人从他的位置起来，先坐到了其他桌子，然后由下一个人重新从1开始报就这样循环下去，每当有人报到K，这个人就离开了桌子，直到剩下这最后一个人，他非常倒霉的要接受大家的惩罚，就是罚酒一杯。JacmY有些郁闷了，K是由自己说的，万一说不好让自己受惩罚了，这个就有点不爽了，所以JacmY想请你帮忙找出哪些K会让他受罚，这样以来，JacmY就不用担心会喝太多酒了！输入规格：第一行一个整数T代表样例的组数下面T行，每行一个整数N， 1 = N= 100；N如题目所述。输出规格：对于每组数据，第一行输出一个整数M，表示有M个这样的K会让JacmY受罚，接下来一行是M个整数，代表K分别取的哪些值，这些数字间用空格隔开。输入样例：35810输出样例：1422 618出题人：吴云鹏F：奇特的图形记得上小学奥数时，JacmY最喜欢做的题就是给一个图形，从它某一个顶点出发描这个图形，若恰通过图中每条边一次，看最后能否又回到起点。当时JacmY只懂得拿着铅笔随便画画试试，如果成功了，就说这个图能画下来，而他判断不能画下来的标准就是费了半天功夫都画不出来，当然这么做是不对的，特别当图形变得复杂时，JacmY是试不过来的。看着可怜的JacmY，你能帮帮他吗？输入规格：第一行一个整数T代表样例的组数以下T组数据中，每组第一行是N，K，(2 = N = 100)分别代表当前图形有N个顶点，K条边，接下来K行中，每行两个整数X， Y（ 1 = X,Y = N）代表顶点X和顶点Y之间有一条边。输出规格：如果当前图形能按照题目要求描出来，则输出“YES”（不包括引号），否则输出“NO”。输入样例：33 31 22 31 33 21 22 32 21 21 2输出样例：YESNOYES出题人：吴云鹏G: Binary String MatchingI can say: this is the simplest problem in this contest, if you missed it because the problem is in English, it will be a pity.Given two strings A and B, whose alphabet consist only 0 and 1. Your task is only to tell how many times does A appear as a substring of B?For example, the text string B is 1001110110 while the pattern string A is 11, you should output 3, because the pattern A appeared at the position 4, 5 and 8.Its very simple, isnt it? I will never cheat you. So be quick, you will easily get a Yes! Just do it!Input Specification:The first line consist only one integer C(C = 10), indicates C cases follows. In each case, there are two lines, the first line gives the string A, length (A) = 10, and the second line gives the string B, length (B) = 100. And it is guaranteed that B is always longer than A.Output Specification:For each case, output a single line consist a single integer, tells how many times do B appears as a substring of A.Sample Input:31110011101101011100100100100011010110100010101011Sample Output:303 Author：Alfred HuangH: Binary String Matching (Extreme)You will soon found this problem is the same as the previous one, but I tell you, it is not so easy, because the data is extremely large, so in order to get a Yes, you must find an effective way to solve it, within a second. Otherwise, youll get a Time Limit Exceed. So a brute force solution is not available here, be avoid to do this.Given two strings A and B, whose alphabet consist only 0 and 1. Your task is only to tell how many times does A appear as a substring of B?For example, the text string B is 1001110110 while the pattern string A is 11, you should output 3, because the patte