2008年ACM大学生程序设计竞赛题

天津工业大学200 8 ～200 9 学年第 2 学期C 程序设计试卷（A）学院班级学号姓名注意事项：1、本试卷共13 页，满分为100 分，考试时间为110 分钟。

2、标准答题卡使用2B铅笔涂写；文字题答题时请使用蓝、黑钢笔或圆珠笔，不得使用红颜色墨水笔。

二、阅读程序题答题处：(每空3分，共30分)四、完善程序填空题答题处：(每空2分，共18分)一、单项单选题：（每题 1 分，共40 分）（说明：请将正确答案按照题干上【】内的序号涂写“标准答题卡”）1．以下标识符中，能够作为变量名使用的是【1】。

A) n_1 B) charC) x(2) D) 2_a2．若有定义语句char ch='\072'; 则变量ch 【2】。

A) 定义错误B) 包含1个字符C) 包含3个字符D) 包含4个字符3．已知字母B的ASCII码值为66，则运行下面程序段后，输出结果是【3】。

char ch1; ch1='B'+'5'-'3'; printf("%d,%c",ch1,ch1);A) D,D B) 68,DC) D,68 D) 68,684．若有如下语句：int x; float y;scanf("k=%d,f=%f",&x,&y);则能够正确的为变量x输入5、为变量y输入3.2的方法是【4】。

说明：备选答案中的<CR>表示回车符A) 5 3.2 <CR> B) 5 <CR> 3.2 <CR>C) k=5,f=3.2 <CR> D) x=5,y=3.2 <CR>int k=10; printf("%d,%o,%x",k,k,k);A) 12,a,10 B) 12,10,aC) 10,12,a D) 10,a,126．判断char 型变量ch 是否为小写字母的正确表达式是【6】。

ACM作业与答案整理1、平面分割方法：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。

#include <iostream.h>int f(int n){if(n==1) return 2;else return f(n-1)+2*(n-1);}void main(){int n;while(1){cin>>n;cout<<f(n)<<endl;}}2、LELE的RPG难题：有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．编程全部的满足要求的涂法.#include<iostream.h>int f(int n){if(n==1) return 3;else if(n==2) return 6;else return f(n-1)+f(n-2)*2;}void main(){int n;while(1){cin>>n;cout<<f(n)<<endl;}}3、北大ACM(1942)Paths on a GridTime Limit: 1000MS Memory Limit: 30000K DescriptionImagine you are attending your math lesson at school. Once again, you are bored because your teacher tells things that you already mastered years ago (this time he's explaining that (a+b)2=a2+2ab+b2). So you decide to waste your time with drawing modern art instead.Fortunately you have a piece of squared paper and you choose a rectangle of size n*m on the paper. Let's call this rectangle together with the lines it contains a grid. Starting at the lower left corner of the grid, you move your pencil to the upper right corner, taking care that it stays on the lines and moves only to the right or up. The result is shown on the left:Really a masterpiece, isn't it? Repeating the procedure one more time, you arrive with the picture shown on the right. Now you wonder: how many different works of art can you produce?InputThe input contains several testcases. Each is specified by two unsigned 32-bit integers n and m, denoting the size of the rectangle. As you can observe, the number of lines of the corresponding grid is one more in each dimension. Input is terminated by n=m=0.OutputFor each test case output on a line the number of different art works that can be generated using the procedure described above. That is, how many paths are there on a grid where each step of the path consists of moving one unit to the right orone unit up? You may safely assume that this number fits into a 32-bit unsigned integer.Sample Input5 41 10 0Sample Output1262#include<iostream>using namespace std;longlong f(long long m, long long n){if(n==0) return 1;else return f(m-1,n-1)*m/n;}int main(){longlongm,n;while(scanf("%I64d %I64d",&n,&m) &&n+m){printf("%I64d\n",f(m+n,min(m,n)));}return 0;}1、（并查集）若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

ACM 软件大赛之编程大赛比赛注意事项：l 比赛时间为3小时（小时（180180分钟）；比赛分两个阶段：第一阶段限时30分钟，完成公示的3题，第二阶段限时150分钟（事先完成第一阶段题目的小组可提前进入第二阶段）； l 比赛第一阶段的3道题目将在前期宣传中告知参赛选手，比赛第二阶段的题目将由赛事主席当场公布竞赛题目；主席当场公布竞赛题目；l 前两阶段题目分为三个分值（前两阶段题目分为三个分值（55分、分、1010分、分、1515分），第一阶段3道公示题都为5分；第二阶段总共15道题，根据不同的难度分值不同，分别为5道5分题，分题，55道10分题，分题，55道15分题；第一阶段参赛队员不可参考任何相关资料；第二阶段参赛队员可以携带诸如书，如书，手册，程序清单等参考资料。

手册，程序清单等参考资料。

手册，程序清单等参考资料。

比赛过程中队员不得携带任何电子媒质的资料；参比赛过程中队员不得携带任何电子媒质的资料；参赛者可以选择自己擅长的语言（赛者可以选择自己擅长的语言（C,C++,JAVA C,C++,JAVA 等等）进行编写等等）进行编写l 考虑到大一和大二学生的知识掌握程度，大一参加选手一开始就会有10分的分数，最后总分是由所做题目及初始的10分相加得到。

分相加得到。

l 每组队员根据安排使用电脑，小组人数为两人的使用一台电脑，超过两人的使用两台电脑，每台的电脑配置完全相同；脑，每台的电脑配置完全相同；l 各小组每做完一题或几题，必须交予评委老师运行，评委老师当场给分；各小组每做完一题或几题，必须交予评委老师运行，评委老师当场给分； l 如在比赛中发现作弊等行为，将取消比赛资格。

如在比赛中发现作弊等行为，将取消比赛资格。

第一阶段公示题目：题目一：（5分） 打印以下图形，纵遵从字母顺序，行字符数遵从斐波那契数列ABCCDDD EEEEEFFFFFFFFGGGGGGGGGGGGG#include<iostream>int f(int x){int a = 1 , b = 0;int max_ = x;int sum = 0; for(int i = 0; i < max_ ; i++){sum = a + b;a = b;b = sum;}return sum;}void loop_print(int num,char chr){for(int i = 0; i < num ;i++)std::cout<<chr;std::cout<<"\n";}int main(){int line_max = 7;char chr = 'A';for(int line = 0; line < line_max; line++){loop_print(f(line+1),chr);chr++;}return 0;}题目二：（5分）有个电子钟，12点显示为12:00（即12小时制），那么请问一天24时间内，出现连续3个相同数字的钟点有几个？#include<iostream>using namespace std;bool check(int me){int h= me/100;int m= me-100*h;return h<=12&&m<=59&&h>0?true:false;//12小时制小时制}int main(){int me=0;int j(0);//总计数器总计数器while( me<1270){//max 12:59int t= me;int n[4];for(int i=0;i<4;i++){n[i]=t%10;t /= 10;}if(n[1]==n[2]&&(n[0]==n[1]||n[3]==n[1])&&check( me)){//cout<<n[3]<<n[2]<<":"<<n[1]<<n[0]<<"\n";//testj++;me++;}cout<<"total: "<<j*2<<endl;}题目三：（5分）10进制的四位数中有几个符合如下特征：将其分别表示为16进制、10进制、12进制，在每种状态下，分别将各个位上的数相加，能得到3个相等10进制数。

程序设计比赛试题主办方：迅翔计算机协会最少钱币数：【问题描述】这是一个古老而又经典的问题。

用给定的几种钱币凑成某个钱数，一般而言有多种方式。

例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。

显然，最少需要2个钱币才能凑成15元。

你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。

【要求】【数据输入】输入可以有多个测试用例。

每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <= 1000)。

输入M=0时结束。

【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。

如果凑钱失败，输出“Impossible”。

你可以假设，每种待凑钱币的数量是无限多的。

【样例输入】156 2 5 10 20 50 10011 2【样例输出】2ImpossibleFeli 的生日礼物【问题描述】Felicia 的生日是11月1日（和Kitty是同一天生的哦）。

于是Feli请来Kitty一起过生日。

Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。

Feli要帮她一个忙，才能够得到心仪已久的玩具。

Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。

Feli 听了大吃一惊。

要知道，算出n!是一个无比艰巨的任务。

Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20 时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。

C语言程序设计竞赛题及其答案数学与统计学院第三届计算机程序设计竞赛题竞赛需知：1、答案必须写在答题纸上。

2、程序采用C/JAVA/VB/VFP语言实现均可。

3、考虑到各种因素，程序的键盘输入和结果输出可以用伪代码或者自然语言表示。

但是必须说明输入变量和输出变量。

4、题目最好能用完整、正确的语言程序来解决问题，如确实无法编写完整语言程序的，可以写出程序主要框架和流程，必要时可以用伪代码或者自然语言描述算法（程序）。

一、玫瑰花数（20分）如果一个四位数等于它的每一位数的4次方之和，则称为玫瑰花数。

例如：++1634+=，4^44^34^64^1编程输出所有的玫瑰花数。

#includevoid main(){int i,j,k,l,m;for(i=999;i<=9999;i++){j=i/1000;k=i%10;l=i/100-10*j;m=i/10-100*j-10*l;if(i==j*j*j*j+k*k*k*k+l*l*l*l+m*m*m*m) printf("%d\n",i);}}二、菱形图案（20分）对给定的奇数n，编程打印菱形图案。

输入样例：7输出样例：*************************#include#includevoid main(){int i,j,k;int n;scanf("%d",&n);for(i=0;i<n;i++)< p="">{for(j=0;j<="" p="">printf("");for(k=0;k<n-2*j;k++)< p="">printf("*");printf("\n");}}三、钻石奖励（20分）海盗们决定用“投环套物”的方式来奖励最近一次行动中贡献最大的人。

ACM International Collegiate Programming Contest2008East Central Regional ContestMcMaster UniversityUniversity of CincinnatiUniversity of Michigan–Ann ArborYoungstown State UniversityNovember1,2008Sponsored by IBMRules:Problem A:Bordering on MadnessBob Roberts owns a design business which creates custom artwork for various corporations.One technique that his company likes to use is to take a simple rectilinearfigure(afigure where all sides meet at90or270degrees and which contains no holes)and draw one or more rectilinear borders around them.Each of these borders is drawn so that it is a set distance d away from the previously drawn border(or the originalfigure if it is thefirst border)and then the new area outlined by each border is painted a unique color.Some examples are shown below(without the coloring of the borders).The example on the left shows a simple rectilinearfigure(grey)with two borders drawn around it.The one on the right is a more complicatedfigure;note that the border may become disconnected.These pieces of art can get quite large,so Bob would like a program which can draw prototypes of the finished pieces in order to judge how aesthetically pleasing they are(and how much money they will cost to build).To simplify things,Bob never starts with afigure that results in a border where2horizontal (or vertical)sections intersect,even at a point.This disallows such cases as those shown below:InputInput will consist of multiple test cases.Thefirst line of the inputfile will contain a single integer indicating the number of test cases.Each test case will consist of two or more lines.Thefirst will contain three positive integers n,m and d indicating the number of sides of the rectlinearfigure,the number of borders to draw,and the distance between each border,where n≤100and m≤20. The remaining lines will contain the n vertices of thefigure,each represented by two positive integers indicating the x and y coordinates.The vertices will be listed in clockwise order starting with the vertex with the largest y value and(among those vertices)the smallest x value.OutputFor each test case,output three lines:thefirst will list the case number(as shown in the examples), the second will contain m integers indicating the length of each border,and the third will contain m integers indicating the additional area contributed to the artwork by each border.Both of these sets of numbers should be listed in order,starting from the border nearest the originalfigure.Lines two and three should be indented two spaces and labeled as shown in the examples.Separate test cases with a blank line.Sample Input26210 2030100301000000102010 10172050705070000030 20302010601060402040 Sample OutputCase1:Perimeters:340420Areas:30003800Case2:Perimeters:380Areas:2660Problem B:Jack of All TradesJack Barter is a wheeler-dealer of the highest sort.He’ll trade anything for anything,as long as he gets a good deal.Recently,he wanted to trade some red agate marbles for some goldfish.Jack’s friend Amanda was willing to trade him1goldfish for2red agate marbles.But Jack did some more digging and found another friend Chuck who was willing to trade him5plastic shovels for3marbles while Amanda was willing to trade1goldfish for3plastic shovels.Jack realized that he could get a better deal going through Chuck(1.8marbles per goldfish)than by trading his marbles directly to Amanda (2marbles per goldfish).Jack revels in transactions like these,but he limits the number of other people involved in a chain of transactions to9(otherwise things can get a bit out of hand).Normally Jack would use a little program he wrote to do all the necessary calculations tofind the optimal deal,but he recently traded away his computer for afine set of ivory-handled toothpicks.So Jack needs your help.InputInput will consist of multiple test cases.Thefirst line of thefile will contain an integer n indicating the number of test cases in thefile.Each test case will start with a line containing two strings and a positive integer m≤50.Thefirst string denotes the items that Jack wants,and the second string identifies the items Jack is willing to trade.After this will be m lines of the forma1name1a2name2indicating that some friend of Jack’s is willing to trade an amount a1of item name1for an amount a2 of item name2.(Note this does not imply the friend is also willing to trade a2of item name2for a1of item name1.)The values of a1and a2will be positive and≤20.No person will ever need more than 231−1items to complete a successful trade.OutputFor each test case,output the phrase Case i:(where i is the case number starting at1)followed by the best possible ratio that Jack can obtain.Output the ratio using5significant digits,rounded.Follow this by a single space and then the number of ways that Jack could obtain this ratio.Sample Input2goldfish marbles31goldfish2marbles5shovels3marbles1goldfish3shovelsthis that47this2that14this4that7this2theother1theother1thatSample OutputCase1:1.80001Case2:0.285713Problem C:LCRLCR is a simple game for three or more players.Each player starts with three chips and the object is to be the last person to have any chips.Starting with Player1,each person rolls a set of three dice.Each die has six faces,one face with an L,one with a C,one with an R and three with a dot.For each L rolled,the player must pass a chip to the player on their left(Player2is considered to be to the left of Player1);for each R rolled,the player passes a chip to the player on their right;and for each C rolled, the player puts a chip in a central pile which belongs to no player.No action is taken for any dot that is rolled.Play continues until only one player has any chips left.In addition,the following rules apply:1.A player with no chips is not out of the game,since they may later gain chips based on otherplayers’rolls.2.A player with only1or2chips left only rolls1or2dice,respectively.A player with no chips leftdoes not roll but just passes the dice to the next player.Your job is to simulate this game given a sequence of dice rolls.InputInput will consist of multiple test cases.Each test case will consist of one line containing an integer n (indicating the number of players in the game)and a string(specifying the dice rolls).There will be at most10players in any game,and the string will consist only of the characters‘L’,‘C’,‘R’and‘.’.In some test cases,there may be more dice rolls than are needed(i.e.,some player wins the game before you use all the dice rolls).If there are not enough dice rolls left to complete a turn(for example,only two dice rolls are left for a player with3or more chips)then those dice rolls should be ignored.A value of n=0will indicate end of input.OutputFor each test case,output the phrase“Game i:”on a single line(where i is the case number starting at1)followed by a description of the state of the game.This desciption will consist of n+1lines of the formPlayer1:c1Player2:c2...Player n:cnCenter:ctwhere c1, are the number of chips each player has at the time the simulation ended(either because some player has won or there are no more remaining dice rolls)and ct is the number of chips in the center pile.In addition,if some player has won,you should append the string“(W)”after their chip count;otherwise you should append the string“(*)”after the chip count of the player who is the next to roll.The only blank on any line should come before the game number or the player number. Use a single blank line to separate test cases.Sample InputR.L.RLLLCLR.LL..R...CLR. 5RL....C.LSample OutputGame1:Player1:0Player2:0Player3:6(W)Center:3Game2:Player1:1Player2:4Player3:1Player4:4(*)Player5:4Center:1Problem D:Party Party PartyEmma has just graduated high school and it is the custom for the new graduates to throw parties for themselves and invite everyone in school to attend.Naturally,Emma wishes to attend as many parties as possible.This is not such a problem on a weekday since usually there are only two or three parties in the evening.But,Saturdays are packed!Typically some parties start at8AM(breakfast is served) while others might end at midnight(much to the annoyance of the neighbors).Emma naturally wants to know how many parties she can attend.Each party has a starting and stopping time,which are on the hour.These are listed via a24-hour clock.For example,a party might start at10AM(10)and end at2PM(14).The earliest a party can start is8AM(8)and the latest it can end is midnight(24).In order not to be rude,Emma stays at each party at least one half hour and will consider traveling time between parties to be instantaneous. If there are times during the day when there are no parties to attend,she’ll simply go home and rest. InputThere will be multiple test cases.Each test case starts with a line containing an integer p(≤100) indicating the number of parties on the given day.(A value of p=0indicates end of input.)The following p lines are each of the form s e,both integers where8≤s<e≤24,indicating a party that starts at time s and ends at time e.Note there may be multiple parties with the same starting and ending time.OutputFor each input set output a line of the formOn day d Emma can attend as many as n parties.where you determine the value of n and d is the number of the test case starting at1.Sample Input8121313141213910910121312149113141514151415Sample OutputOn day1Emma can attend as many as7parties.On day2Emma can attend as many as2parties.Problem E:Su-Su-SudokuBy now,everyone has played Sudoku:you’re given a9-by-9grid of boxes which you are tofill in with the digits1through9so that1)every row has all nine digits,2)every column has all nine digits,and 3)all nine3-by-3subgrids have all nine digits.To start the game you are given a partially completed grid and are asked tofill in the remainder of the boxes.One such puzzle is shown below.415676985972453919853752472398187286231In this problem,you will be given Sudoku grids which you have nearly completed;indeed you’vefilled in every box exceptfive.You are asked to complete the grid,or determine that it’s impossible.(You might have already made an error!)InputThefirst line of input will contain a positive integer indicating the number of test cases to follow.Each test case will be a nearly completed Sudoku grid consisting of9lines,each containing9characters from the set of digits0through9.There will be exactlyfive0’s in each test case,indicating thefive unfilled boxes.OutputOutput for each test case should be eitherCould not complete this grid.if it is impossible to complete the grid according to the rules of the game,or the completed grid,in the form given below.(There are no blank spaces in the output.)If there is a way to complete the grid,it will be unique.Separate test cases with a blank line.Sample Input2481253697267948105539671204654389712908704563173562849702136958315897426896425371481253697267948105539671284654289710908704562173562849702136958315897426896425371Sample Output481253697267948135539671284654389712928714563173562849742136958315897426896425371Could not complete this grid.Problem F:Tanks a LotImagine you have a car with a very large gas tank-large enough to hold whatever amount you need. You are traveling on a circular route on which there are a number of gas stations.The total gas in all the stations is exactly the amount it takes to travel around the circuit once.When you arrive at a gas station,you add all of that station’s gas to your tank.Starting with an empty tank,it turns out there is at least one station to start,and a direction(clockwise or counter-clockwise)where you can make it around the circuit.(On the way home,you might ponder why this is the case-but trust us,it is.) Given the distance around the circuit,the locations of the gas stations,and the number of miles your car could go using just the gas at each station,find all the stations and directions you can start at and make it around the circuit.InputThere will be a sequence of test cases.Each test case begins with a line containing two positive integers c and s,representing the total circumference,in miles,of the circle and the total number of gas stations. Following this are s pairs of integers t and m.In each pair,t is an integer between0and c−1measuring the clockwise location(from some arbitraryfixed point on the circle)around the circumference of one of the gas stations and m is the number of miles that can be driven using all of the gas at the station. All of the locations are distinct and the maximum value of c is100,000.The last test case is followed by a pair of0’s.OutputFor each test case,print the test case number(in the format shown in the example below)followed by a list of pairs of values in the form i d,where i is the gas station location and d is either C,CC,or CCC, indicating that,when starting with an empty tank,it is possible to drive from location i around in a clockwise(C)direction,counterclockwise(CC)direction,or either direction(CCC),returning to location i.List the stations in order of increasing location.Sample Input1042343619355014121311100Sample OutputCase1:2C4CC9CCase2:0CCC1CCC2CCC3CCC4CCCProblem G:The Worm TurnsWinston the Worm just woke up in a fresh rectangular patch of earth.The rectangular patch is divided into cells,and each cell contains either food or a rock.Winston wanders aimlessly for a while until he gets hungry;then he immediately eats the food in his cell,chooses one of the four directions(north, south,east,or west)and crawls in a straight line for as long as he can see food in the cell in front of him.If he sees a rock directly ahead of him,or sees a cell where he has already eaten the food,or sees an edge of the rectangular patch,he turns left or right and once again travels as far as he can in a straight line,eating food.He never revisits a cell.After some time he reaches a point where he can go no further so Winston stops,burps and takes a nap.For instance,suppose Winston wakes up in the following patch of earth(X’s represent stones,all other cells contain food):01234X13XIf Winston starts eating in row0,column3,he might pursue the following path(numbers represent order of visitation):0123442X11816620143X2281012In this case,he chose his path very wisely:every piece of food got eaten.Your task is to help Winston determine where he should begin eating so that his path will visit as many food cells as possible. InputInput will consist of multiple test cases.Each test case begins with two positive integers,m and n, defining the number of rows and columns of the patch of earth.Rows and columns are numbered starting at0,as in thefigures above.Following these is a non-negative integer r indicating the number of rocks,followed by a list of2r integers denoting the row and column number of each rock.The last test case is followed by a pair of zeros.This should not be processed.The value m×n will not exceed 625.OutputFor each test case,print the test case number(beginning with1),followed by four values:amount row column directionwhere amount is the maximum number of pieces of food that Winston is able to eat,(row,column) is the starting location of a path that enables Winston to consume this much food,and direction isone of E,N,S,W,indicating the initial direction in which Winston starts to move along this path.If there is more than one starting location,choose the one that is lexicographically least in terms of row and column numbers.If there are optimal paths with the same starting location and different starting directions,choose thefirst valid one in the list E,N,S,W.Assume there is always at least one piece of food adjacent to Winston’s initial position.Sample Input55304313200Sample OutputCase1:2203WProblem H:You’ll be Working on the RailroadCongratulations!Your county has just won a state grant to install a rail system between the two largest towns in the county—Acmar and Ibmar.This rail system will be installed in sections,each section connecting two different towns in the county,with thefirst section starting at Acmar and the last ending at Ibmar.The provisions of the grant specify that the state will pay for the two largest sections of the rail system,and the county will pay for the rest(if the rail system consists of only two sections,the state will pay for just the larger section;if the rail system consists of only one section,the state will pay nothing).The state is no fool and will only consider simple paths;that is,paths where you visit a town no more than once.It is your job,as a recently elected county manager,to determine how to build the rail system so that the county pays as little as possible.You have at your disposal estimates for the cost of connecting various pairs of cities in the county,but you’re short one very important requirement—the brains to solve this problem.Fortunately,the lackeys in the computing services division will come up with something.InputInput will contain multiple test cases.Each case will start with a line containing a single positive integer n≤50,indicating the number of railway section estimates.(There may not be estimates for tracks between all pairs of towns.)Following this will be n lines each containing one estimate.Each estimate will consist of three integers s e c,where s and e are the starting and ending towns and c is the cost estimate between them.(Acmar will always be town0and Ibmar will always be town1.The remaining towns will be numbered using consecutive numbers.)The costs will be symmetric,i.e.,the cost to build a railway section from town s to town e is the same as the cost to go from town e to town s,and costs will always be positive and no greater than1000.It will always be possible to somehow travel from Acmar to Ibmar by rail using these sections.A value of n=0will signal the end of input.OutputFor each test case,output a single line of the formc1c2...cm costwhere each ci is a city on the cheapest path and cost is the cost to the county(note c1will always be0 and cm will always be1and ci and ci+1are connected on the path).In case of a tie,print the path with the shortest number of sections;if there is still a tie,pick the path that comesfirst lexicographically. Sample Input70210036245343354417518Sample Output03413。

Problem A：祝福【问题描述】得知Atlantis即将沉没的消息以后，King决定把他的人民送到安全的国外去。

但是码头已经废弃很多很多年了。

码头前有一个迷宫，国王的骑士只身闯入了这个迷宫……骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单独作战，所以很快便招架不住了，他的大马被打得奄奄一息（。

）这个时候，迷宫中的两座石像(一个是猫，一个是天使。

（！！！！！))里放出了无数锋利的刀片，把不明生物全部杀死，骑士当场晕倒在地。

等他醒来，发现马已经死了，手上多了一个戒指，上面写着：“这个戒指会帮助你逃脱。

它赋予了神奇的力量。

有了它，每次移动如果是只要|x-x1|+|y-y1|<=P(P在输入文件中给出)，且(x1, y1)不是障碍物，你就能实现(x, y) -> (x1, y1)的移动！”(Angel暗自想：还有这么心黑的……)迷宫为n*m(0<n,m<=20)的矩阵。

骑士从(n, m)到(1, 1)。

问：在戒指的帮助下，骑士最少要多少步才能回到入口？在步数最少的前提下，总共有多少种办法到达入口？注意，骑士不会傻到一直停留在原地不动。

【输入文件】第1行3个整数，n, m, P，分别代表迷宫大小和移动范围以后n行，每行m个数，代表了迷宫，其中0代表可通，1代表不能通过。

【输出文件】两个整数，用空格分开，分别代表最少到达入口的步数和路径的数目。

假设一定能够达到入口。

【样例输入】2 2 10 01 0【样例输入】2 1Problem B：津津的储蓄计划【问题描述】津津的零花钱一直都是自己管理。

每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。

因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

第八届程序设计大赛初赛试题说明：请将所有答案写到试卷第1页及第2页。

一、读程序写结果（40分）1、（5分）2、（5分）3、（10分）结果：结果：结果：4、（10分）5、（5分）6、（5分）结果：结果：结果：二、代码填空（30分）1、（5分）2、（5分）空一：____acm / lg （5分）空一：if(begin>end) return （5分）3、（12分）4、（8分）空一：siruan /= 10 （3分）空一：s[i] - '0' （4分）空二：hm - lg （3分）空二：siruan[sum % 11] （4分）空三：lghm = acm(lghm) （6分）三、思维题（15分）数据1：T1=1，T2=2，T3=3，T4 = 4 数据2：T1=1，T2=2，T3=5，T4 = 10 答案：（acm）1 2->(siruan) 2min 答案：（acm）1 2->(siruan) 2min (acm) <-1 (siruan) 1min (acm) <-1 (siruan) 1min(acm) 1 3->(siruan) 3min (acm) 5 10->(siruan) 10min(acm) <-1 (siruan) 1min (acm) <-2 (siruan) 2min(acm) 1 4-> (siruan) 4min (acm) 1 2-> (siruan) 2min最短时间：2+1+3+1+4 = 11min 最短时间：2+1+10+2+2 = 17min数据3：T1 = 5，T2 = 2，T3=1，T4=10，T5=8 答案：（acm）1 2->(siruan) 2min(acm) <-1 (siruan) 1min(acm) 8 10->(siruan) 10min(acm) <-2 (siruan) 2min(acm) 1 2-> (siruan) 2min(acm) <-1 (siruan) 1min(acm) 1 5 ->(siruan) 5min最短时间：2+1+10+2+2+1+5 = 23min四、编程题（15分）程序代码：#include<stdio.h>#include<string.h>int s[110];int main(){int i;int a, n, m;while (scanf("%d%d", &a, &n)!=EOF){memset(s, 0x00, sizeof(s));m = n;for (i=0; i<m; i++){s[i] += a * (n--);s[i+1] = s[i] / 10;s[i] %= 10;}if (s[m]) printf("%d", s[i]);for (i=m-1; i>=0; i--)printf("%d", s[i]);printf("\n");}return 0;}一、读程序写结果（40分）1、（5分）#include <stdio.h>int main(){char acm[] = "I love acm!";char siruan[] = "I love siruan!";char def[] = "Welcome to join us!";int chose = 0;switch (chose){case 0: printf("%s\n", acm);case 1: printf("%s\n", siruan);default : printf("%s", def);}return 0;}输出结果：2.（5分）#include <stdio.h>int main(){int acm = 0, siruan = 1;if (acm = siruan) printf("%s", "May you success!");else printf("%s", "May you success,too!");return 0;}输出结果：3.（10分）#include <stdio.h>#include <math.h>int main(){int i,j,k,n;char lghm[14]="ILOVEACMSIRUAN";n = 3;for (i=0; i<n-1; i++) printf(" ");printf("%c\n",lghm[0]);for (i=1; i<n; i++){for (j=abs(n-i-1); j>0; j--) //abs(n)返回值为整形n的绝对值printf(" ");printf("%c",lghm[2*i-1]);for (k=1; k<=2*i-1; k++) printf(" ");printf("%c\n",lghm[2*i]);}for (i=n; i<=2*n-3; i++){for (j=abs(n-i-1); j>0; j--) printf(" ");printf("%c",lghm[2*i-1]);for (k=1; k<=4*n-5-2*i; k++) printf(" ");printf("%c\n",lghm[2*i]);}for (i=0; i<n-1; i++) printf(" ");printf("%c\n",lghm[4*n-5]);return 0;}输出结果：4.（10分）#include <stdio.h>#include <string.h>struct Student{char name[20];int num;} stu[5];{stu[0].num = 521; strcpy(stu[0].name, "sichuan wenchuan");stu[1].num = 521; strcpy(stu[1].name, "bless");stu[2].num = 420; strcpy(stu[2].name, "sichuan yaan");stu[3].num = 420; strcpy(stu[3].name, "love");stu[4].num = 420; strcpy(stu[4].name, "god");}void swap(int a, int b){struct Student tmp;tmp.num = stu[a].num;stu[a].num = stu[b].num;stu[b].num = tmp.num;strcpy(, stu[a].name);strcpy(stu[a].name, stu[b].name);strcpy(stu[b].name, );}void bubble_sort(int n){int i,j,flag,temp;for(i = 0; i < n-1; i++){flag = 1;for(j = 0; j < n-i-1; j++){if(stu[j].num > stu[j+1].num){swap(j, j+1);flag = 0;}else if (stu[j].num == stu[j+1].num && strcmp(stu[j].name,stu[j+1].name)<0){ swap(j, j+1);}}if(flag) break;}}int main(){init();bubble_sort(5);for (i=0; i<5; i++)printf("%-4d%s\n", stu[i].num, stu[i].name);return 0;}输出结果：6.（5分）#include <stdio.h>int acm(){int lg = 1314520;int hm = 0;while(lg > 0){hm = hm * 10 + lg % 10;lg /= 10;}return hm;}int main(){int siruan = acm();printf("%d", siruan);return 0;}输出结果：二、代码填空（30分）1.(5)如果没有计算器，我们如何求3的平方根？可以先猜测一个数，比如1.5，然后用3除以这个数字。

一、选择题（每题1分，共20分）1．设 int b=2;表达式b/(b*2)的值是（）。

A. 0B. 0.5C. 0.500000D. 0.000002．下列标识符中不合法的标识符的是（）。

A. hot_doB. cat1C. _priD. 2ab3．以下程序的输出结果是（）。

void main(){int k=17；printf("%d，%o，%x \n"，k，k，k)；}A. 17，021，0x11B. 17，17，17C. 17，0x11，021D. 17，21，114．设x、y、z和k都是int型变量，则执行表达式：x=（y=4，z=16，k=32）后，x的值为（）。

A．4 B．16 C．32 D．525．下述程序段中，while循环执行次数是( )。

int k=0;while(k=1) k++;A. 无限次B. 有语法错误，不能执行C. 一次也不执行D. 执行一次6. 若要求在if后一对圆括号中表示a不等于0的关系,则能正确表示这一关系的表达式为（）。

A. a < > 0B. !aC. a=0D. a!=07．执行下述语句后,*(p+1)的值是( )。

char s[]= “ab”,*p；p=s;A.‘b’B. OC. 不定值D. 非法引用128．有以下语句:int b;char c[10];,则正确的输入语句是( )。

A. scanf("%d%s",&b,&c);B. scanf("%d%s",&b,c);C. scanf("%d%s",b,c);D. scanf("%d%s",b,&c);9．能正确表示a 和b 同时为正或同时为负的逻辑表达式是（ ）。

A. (a>=0‖b>=0)&&(a<0‖b<0)B. (a>=0&&b>=0)&&(a<0&&b<0)C. (a+b>0)&&(a+b<=0)D. a*b>010．C 语言中的逻辑运算结果，用（ ）表示逻辑“真”值。

备战ACM资料习题1． 0-1背包问题在0 / 1背包问题中，需对容量为c 的背包进行装载。

从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。

对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。

程序如下：#include <stdio.h>void readdata();void search(int);void checkmax();void printresult();int c=35, n=10; //c：背包容量；n：物品数int w[10], v[10]; //w[i]、v[i]：第i件物品的重量和价值int a[10], max; //a数组存放当前解各物品选取情况；max：记录最大价值//a[i]=0表示不选第i件物品，a[i]=1表示选第i件物品int main(){readdata(); //读入数据search(0); //递归搜索printresult();}void search(int m){if(m>=n)checkmax(); //检查当前解是否是可行解，若是则把它的价值与max比较else{a[m]=0; //不选第m件物品search(m+1); //递归搜索下一件物品a[m]=1; //不选第m件物品search(m+1); //递归搜索下一件物品}}void checkmax(){int i, weight=0, value=0;for(i=0;i<n;i++){if(a[i]==1) //如果选取了该物品{weight = weight + w[i]; //累加重量value = value + v[i]; //累加价值}}if(weight<=c) //若为可行解if(value>max) //且价值大于maxmax=value; //替换maxvoid readdata(){int i;for(i=0;i<n;i++)scanf("%d%d",&w[i],&v[i]); //读入第i件物品重量和价值}void printresult(){printf("%d",max);}2．装载问题有两艘船，载重量分别是c1、c2，n个集装箱，重量是wi (i=1…n)，且所有集装箱的总重量不超过c1+c2。

2、美丽的大树，难度：中等。

【程序文件名】tree.pas
【问题描述】
兴中道是中山最美丽的道路，路中间的绿化带上种了两列漂亮的大树，这些大树分成了50行，每行两棵大树，一共100棵大树，这些大树被编上了号，编号方式如下：
1 3 5 7 …………45 47 49 …………97 99
2 4 6 8 …………46 48 50 …………98 100
再过几天奥运火炬就要在中山传递了，美丽的兴中道当然是最重要的必经之路，但是某天晚上却发生了一件令人震惊的大事--可恶的破坏分子为了破坏奥运，让中山人民丢丑，竟然偷去了这100棵大树中的一部分！
公安部门马上出动，列出了被偷去了大树的编号。

现在摆在我们面前的情况是，如果火炬的旁边是空空的树坑，那是令人无法接受的，因此我们只能压缩火炬在兴中道上的传递距离，务必使火炬在连续的大树边传递，当时，我们就得找出一列最长的连续的大树供传递火炬时展现在全世界的人面前。

请你编写程序解决这一难题。

【输入格式】
N （表示有N棵大树被盗）
N1 N2 N3……NN （被盗大树的编号）
【输出格式】
M X （表示从第M棵大树开始，共有连续的X棵大树，如果有多个解，只输出一个解即可）
【输入输出样例1】
输入：
5
9 15 27 35 6
输出样例：
8 47
【输入输出样例2】
输入：
6
9 15 20 35 6 29
输出样例：
22 40。

2008年5月17日，在浙江大学成功举行了浙江省第五届大学生程序设计竞赛。

本人的解题报告如下：A 简单题因为p的范围很小才99 所以从700-799就可以满足全部要求了。

可以打表出来，找出每个连续的一段满足要求的数，保存起来（并且要求新存的段长度比原先的要长），打出一张表，对每个要求的数，2分答案。

（把1-99的结果都保存好，直接输出）。

反正“转折点”很少，怎么搞都可以。

B 简单题直接bfs无向图mst。

C 中等偏难。

给定直线，对每条直线，传说解不等式组可以过，直接看是否存在一个点在直线之上。

（左端点取max,右端点取min，如果左>=右，直接break掉）。

有点ft...O(n^2) n=5000 rp好的可以过....我用的方法类似于凸包，先把所有直线按照斜率a由小到大排序，斜率相同取b较大的，扔掉b小的。

于是所有直线斜率不同。

准备一个栈，栈里面存放上一次能看到的“最上面”的直线以及这条直线能看到的范围x(x值右边的部分可以被看到）。

初始时，把斜率最小的直线入栈，并记录x值为-inf。

然后对第i条直线，所做的是用第i条直线和栈顶直线求交点x,如果这个x值不大于栈顶的x值，则把栈顶元素弹出，继续求交，否则退出。

这种判断操作直到栈为空，或者当前栈顶的x值大于栈顶的x值。

然后把第i条直线入栈，继续，看后面的直线。

最后栈中的直线数就是能看到的。

这种做法类似于凸包的方法，除去排序外，每条直线至多出入栈一次，复杂度O(n)。

总复杂度是O(nlogn)。

D 难题。

这题是比较有意思和有搞头的题。

应该可以算压轴题吧。

题目意思不难，但是很难做。

我想了好久，想出个方法，但是比vb的方法难一些。

其实可以贪心。

首先集合大小为1时，没法搞，直接判断掉。

我们把A集合和B集合里的数都由小到大排序。

要移动元素并且保证代价，那么可以选择的操作方法是A和B交换一些元素，然后A再给B(或者B再给A)若干个元素。

我们只讨论最后A再给B若干个数的情形，B给A的可以类似讨论。

acm大学生程序试题及答案1. 题目：字符串反转描述：给定一个字符串，编写一个函数来将字符串中的字符按相反的顺序重新排列。

输入：一个字符串输出：反转后的字符串答案：```pythondef reverse_string(s):return s[::-1]```2. 题目：寻找最大数描述：给定一个整数数组，找出数组中的最大数。

输入：一个整数数组输出：数组中的最大数答案：```pythondef find_max(nums):return max(nums)```3. 题目：两数之和描述：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的索引（从1开始计数）。

输入：一个整数数组和一个目标值输出：两个数的索引，如果没有则返回空数组答案：```pythondef two_sum(nums, target):num_to_index = {}for i, num in enumerate(nums):complement = target - numif complement in num_to_index:return [num_to_index[complement] + 1, i + 1] num_to_index[num] = ireturn []```4. 题目：无重复字符的最长子串描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

输入：一个字符串输出：最长子串的长度答案：```pythondef length_of_longest_substring(s):char_map = {}start = max_length = 0for end in range(len(s)):if s[end] in char_map:start = max(start, char_map[s[end]] + 1)char_map[s[end]] = endmax_length = max(max_length, end - start + 1)return max_length```5. 题目：整数转罗马数字描述：将一个整数转换为罗马数字。

计算机科学系第二届大学生程序设计竞赛试题题目一大数乘法问题描述（Problem Description）：编程实现位数不超过300位的任意大的两个整数相乘。

输入（Input）：提示用户输入第一个大数乘数和第二个大数乘数。

输出（Output）：输出两个大数的乘积。

输入示例（Sample Input）：请输入第一个乘数：123456789123456请输入第二个乘数：123456789123456输出示例（Sample Output）：两数的乘积是：15230578580673373689799383936题目二排球队员站位问题问题描述（Problem Description）：左图为排球场的平面图，其中一、二、三、四、五、六为位置编号，二、三、四号位置为前排，一、六、五号位为后排。

某队比赛时，一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻手。

队员所穿球衣分别为１，２，３，４，５，６号，但每个队员的球衣都与他们的站位号不同。

已知１号、６号队员不在后排，２号、３号队员不是二传手，３号、４号队员不在同一排，５号、６号队员不是副攻手。

编程求每个队员的站位情况。

输入（Input）：输出（Output）：输出每个队员球衣号码和所站的位置编号。

输入示例（Sample Input）：输出示例（Sample Output）：球衣号码：1 2 3 4 5 6位置编号：一二三四五六题目三文件读写问题描述（Problem Description）：INI文件为一种广泛应用的储存程序配置的文件格式。

要求不使用操作系统自带INI 文件处理功能，用c++编写一个INI文件读取程序，并把结果输出到显示器及文件result.txt中。

说明：INI文件的结构：[区名字] # 区名注释键名=键值# 键值注释一个区里可以有几个不同键名的键值，例如：测试用INI文件test.ini：[section] #this is a section commentkey=value #this is a key comment[section2]key2=value2要求程序能读取section2区中键名为key2的值，以及section区中的键名为key的注释。

附件一：学习科技竞赛奖获得者名单1、2008年ACM国际大学生程序设计竞赛亚洲区预选赛获奖名单全国一等奖（1000元/人）国际软件学院：杨洋计算机学院：高云翔崔汗青全国二等奖（700元/人）计算机学院：阎栋李志旭刘利祥圣赞电气工程学院：董志嵩国际软件学院：李嘉琦全国三等奖（500元/人）国际软件学院：杜浩计算机学院：刘涛范锦曾杰瑜洪毅虹金毅2、2008年第二届全国大学生结构设计竞赛获奖名单全国一等奖（1000元/人）土木建筑学院：邓业龙杨迤王默3、2008年全国Intel杯嵌入式系统专题邀请赛获奖名单全国一等奖（1000元/人）电子信息学院：冯浩刘小兵苏磊全国二等奖（700元/人）电子信息学院：曾杜陈文辉国际软件学院：项翔全国三等奖（500元/人）电子信息学院：曾真徐广嵚施智强4、第三届全国大学生“飞思卡尔”杯智能汽车竞赛获奖名单全国一等奖（1000元/人）动力与机械学院：严金辉裘有斌张星全国二等奖（700元/人）动力与机械学院：赵瑞祥庄洁玉卢开瑞省部级二等奖（400元/人）动力与机械学院：杨杰王雪竹崔春雷郭强周文林电气工程学院：蔡伟5、2008年全国大学生数学建模竞赛获奖名单全国一等奖（1000元/人）电子信息学院：初从颖赵宇乐意数学与统计学院：刁辰喆资源与环境科学学院：李洪利物理科学与技术学院：马亚军全国二等奖（700元/人）数学与统计学院：吴雪飞魏鑫董绍政孙煜土木建筑工程学院：刘银田恒蛟李健电气工程学院：杨尚瑾遥感信息学院：罗晖何连电子信息学院：汤煌刘欣慰省部级一等奖（500元/人）电子信息学院：杨成测绘学院：冯晨数学与统计学院：谢玲王超许竹影江寅计算机学院：张五州电气工程学院：王聪水利水电学院：刘治军省部级二等奖（400元/人）土木建筑工程学院：张俊峰熊焕叶俊电子信息学院：董微张守首物理科学与技术学院：房一楠资源与环境科学学院：吴冰洁计算机学院：叶佳数学与统计学院：谌琛常远洋凌铃郑宇林迪郑鹏飞沈阳杜梦宇廖毅马丽电气工程学院：徐迎周宇晴郑凌娟省部级三等奖（300元/人）电子信息学院：陈紫微王洁琼测绘学院：马亶佑数学与统计学院：袁烨土木建筑工程学院：颜敬计算机学院：许强6、2008年湖北省电子设计竞赛获奖名单省部级特等奖（TI杯）（800元/人）电子信息学院：陈林辉夏效禹伍玉省部级一等奖（500元/人）电子信息学院：谭潇雄方阁刘利子罗怡李朋朋马玖凯廖艳闺李刚唐晓庆省部级二等奖（400元/人）电子信息学院：徐骅陈浩瞿涛陈丽君刘凯王伟平曹晓杭王雨曦江超张志勇余师倩方力电气工程学院：陈坚张拯民刘阳7、2008年湖北省高校普通话风采大赛获奖名单省部级一等奖（500元/人）新闻与传播学院：陈维省部级二等奖（400元/人）土木建筑工程学院：邓业龙省部级优秀奖（100元/人）艺术系：唐雯8、2008年全国信息安全竞赛获奖名单省部级一等奖（500元/人）计算机学院：刘岱坪省部级三等奖（300元/人）计算机学院：刘新文刘永亮彭康张通博叶卫军熊思阳朱婵元陶夏昕刘宇斌9、2008年全国ESRI大学生GIS软件开发竞赛获奖名单省部级一等奖（500元/人）遥感信息工程学院：邓雯婷郭善昕余万里10、2008湖北省大学生机械创新设计大赛获奖名单省部级一等奖（500元/人）动力与机械学院：李莹松高福生何缘樊孝贺省部级一等奖（3000元/集体）动力与机械学院：程经淦洪垣赵瑞祥郑贵荣萧国能省部级二等奖（400元/人）动力与机械学院：杨菲刘勇吴亚娟赵彦詹立新刘振李奇龙省部级二等奖（2000元/集体）动力与机械学院：黄金马泽龙严金辉徐敏庄洁玉动力与机械学院：陈威薛健吉星星牛文韬王小彬省部级优秀奖（100元/人）动力与机械学院：张佩陈磊李晟包泳珂操建平蔡敏11、第二届武汉大学结构设计大赛获奖名单校级一等奖（200元/人）土木建筑学院：袁淑蓉唐婷婷谢津成李江华张伟曹建坤张孝春杨迤谢鹏邓礼陈恕光帅昌立校级二等奖（100元/人）土木建筑学院：申岩峰康欢孔德俊王晓虎马开志王小翠汪李汪平邓业龙周颖沈昕刘银颜敬贺伟伟肖天天李健祥李杰张晗胡正欢刘茂青朱易龙邵倩曾思栋张琳校级三等奖（50元/人）土木建筑学院：彭道权张明杰李誉亮杨世涛娄泽方田恬范伟王啸晟林朝平张俊峰夏巨伟王金杰线实涂望龙胡楠王前进李锋方业友李超欧阳越温则虎何启志谭远武朱滢夏巨伟谭磊王金杰胡德亮韩大江曹凯刑鹏举罗飞翔陶烨祁得志魏健陈乾锐12、2008年大学生优秀科研成果获奖名单省部级一等奖（500元/人）生命科学学院：谭博计算机学院：丁乙华饶立姚岸松龙成江省部级二等奖（400元/人）文学院：袁明锡周舒艺齐晓燕霍西胜政治与公共管理学院：马兰芬化学与分子科学学院：何川电子信息学院：陈紫微丁建胡昱希李韵潘姣动力与机械学院：麦晓明花丽水利水电学院：万颖李宇轩周建银资源与环境科学学院：朱彦刚口腔医学院：肖秀凤杨瑞莉林淑贤刘译聪基础医学院：唐玲华吕锡锋马敏赵雪清第二临床学院：王艳炜何精选程雄飞公共卫生学院：骆名进护理学院：陈永凤卢吉王天慈电子信息学院：杨洋徐俊谭鹏举程达省部级三等奖（300元/人）经济与管理学院：谷寒梅政治与公共管理学院：王思博宋磊法学院：于雷电气工程学院：曾正陶佳燕林志敏电子信息学院：张金柱校级一等奖（200元/人）化学与分子科学学院：蔡政旭生命科学学院：高艳周毛天电气工程学院：陈堃国际软件学院：项翔陈文辉曾杜化学与分子科学学院：吕红金计算机学院：刘岱坪第一临床学院：王顺闫晗公共卫生学院：庄丽丽刘国强黄斌祝明清程丽薇邹萍基础医学院：黄偲璇校级一等奖（2000元/集体）第一临床学院：韩国鸽范彪张懿敏王永平董慧敏资源与环境科学学院：何伟徐芙清郑星肖潇杨晨校级二等奖（100元/人）经济与管理学院：关永辉邢杰张燕历史学院：杨光吕昭哲学学院：张丽平吴海霞张威赖金金王利文学院：陈文婷曾攀谢旭杰于乐信息管理学院：刘璐化学与分子科学学院：邓轶张华余甘翔周琼波测绘学院：王磊李军张恒付海龙刘炎炎陈林李盼梁小双计算机学院：闫昭博赵静朱丽萍刘新文唐德一方传云方喆君寇鹏席栋土木建筑工程学院：陈阳程辉吴可伟陈学物理科学与技术学院：李鸿渐遥感信息工程学院：李斯泽刘雪俊丁晓阳李红举基础医学院：李燕张迪罗瑛任斌校级二等奖（1500元/集体）动力与机械学院：欧阳子健王康曾晓宇罗欢宗鑫曼动力与机械学院：郑贵荣赵瑞祥洪垣程经淦萧国能新闻与传播学院：李明明樊沙官庆庆施拟阳饶瑶哲学学院：山姗张丽平吴海霞许巧巧廖雯恒校级三等奖（50元/人）社会学系：王思萌陈津华齐凡汪芸政治与公共管理学院：宋磊王思博计算机学院：刘昶寇鹏杨倩方传云朱婵元陶夏刘宇斌动力与机械学院：何洁肖鹏韩倩倩肖稳动力与机械学院：肖鹏肖稳何洁韩倩倩第二临床学院：张维郭方健孟晔校级三等奖：（1000元/集体）电子信息学院：赵印刘琴李晶刘欣慰孙宁13、第五届“中国青少年科技创新奖”全国一等奖（1000元/人）化学与分子科学学院：何川14、全国大学生“迎奥运讲文明树新风”礼仪知识电视竞赛全国一等奖（1000元/人）哲学学院：贺捷生命科学学院：陈东新闻与传播学院：张星月15、第七届海峡两岸知识大赛全国一等奖（1000元/人）新闻与传播学院：徐林张星月资源与环境学院：杨子江16、湖北省第七届互联网知识竞赛省部级一等奖（3000元/集体）遥感信息工程学院：杨沁雨宋磊王炜哲动力与机械学院：张立超方晶哲学学院：吴穹山姗水利水电学院：李志晶外国语言文学学院：孔安然17、第六届湖北省高校“新青年”小说大赛省部级一等奖（500元/人）经济与管理学院：王磊艺术学系：张竞文文学院：董金超省部级二等奖（400元/人）文学院：谢旭杰省部级三等奖（300元/人）信息管理学院：郑妍基础医学院：刘源辉18、第七届湖北省高校“新青年”小说大赛省部级一等奖（500元/人）信息管理学院：周琳达省部级二等奖（400元/人）经济与管理学院：蔡杰哲学学院：渠爽19、第七届中国（武昌）辛亥首义文化节大学生辩论邀请赛省部级一等奖（3000元/集体）哲学学院：贺捷资源与环境学院：杨子江历史学院：潘泽曾昕动力与机械学院：杜俊省部级一等奖（500元/人）哲学学院：贺捷20、湖北省高校第二十四届一二·九诗歌散文大赛省部级二等奖（400元/人）法学院：赵博经济与管理学院：邹韵政治与公共管理学院：李永真省部级三等奖（300元/人）文学院：马维娜21、第二届海峡两岸大学生“阅读与财富”演讲比赛全国一等奖（1000元/人）法学院：赵博22、湖北省首届大学生“感恩之声”演讲大赛省部级一等奖（500元/人）法学院：赵博23、武汉大学首届“助学政策助我成长”优秀征文获奖名单校级特等奖（500元/人）社会学系：周辉剑基础医学院：杨应成水利水电学院：穆贵玲校级一等奖（200元/人）经济与管理学院：毛忠星肖本雨乔云华新闻与传播学院：郑斯思城市设计学院：达娃扎西遥感信息工程学院：王向东印刷与包装系：刘龙基础医学院：钟燕军胡芬夏海波校级二等奖（100元/人）法学院：董琳李少文经济与管理学院：朱叶领江碧屏付永丽水利水电学院：黄蓉电气工程学院：李红元徐群伟杨慧基础医学院：艾罗燕陈曼丽黄昱张洋崔世森护理学院：孙秋娥三等奖（50元/人）外国语言文学学院：饶洋经济与管理学院：陈燕商光香李政吴航数学与统计学院：汪兰兰水利水电学院：李杨曹升起钟权电气工程学院：肖叶清印刷与包装系：徐洁基础医学院：金二亮王晴夏婷杨艳张雪荣李少冲桑涛护理学院：彭芬口腔医学院：郑云飞校级一等奖（2000元/集体）基础医学院校级二等奖（1500元/集体）电气工程学院水利水电学院校级三等奖（1000元/集体）经济与管理学院印刷与包装系附件二：文艺活动奖获得者名单1、2008年“五月的鲜花”全国大学生大型校园文艺演出全国一等奖（800元/集体）武汉大学大学生艺术团2、第六届中国舞蹈荷花奖校园舞蹈比赛全国三等奖（600元/项）武汉大学大学生艺术团2项3、第二届湖北省大学生服装秀大赛省部级一等奖（600元/集体）政治与公共管理学院：杨雅琳艺术学系：赵钟泉高瑒陈婧周越辉外国语言文学学院：何珊化学与分子科学学院：黄利莉文学院：张薇经济与管理学院：高慕涛宋晓宇杨志伟裴毅张嘉伟吴玉鑫省部级一等奖（500元/人）艺术学系：赵钟泉4、湖北省第四届“楚风杯”大学生书画大赛省部级一等奖（500元/人）文学院：丘新巧经济与管理学院：周升剑省部级二等奖（200元/人）经济与管理学院：王杨江剑省部级三等奖（100元/人）信息管理学院：赵小青电气工程学院：黄松5、湖北省第三届大学生艺术节及文艺展演省部级一等奖（600元/项）生命科学学院合唱团1项大学生艺术团交响乐团2项大学生艺术团民乐团3项大学生艺术团舞蹈团2项大学生艺术团声乐团女声组合1项省部级二等奖（500元/项）大学生艺术团声乐团男声组合1项经济与管理学院1项省部级三等奖（400元/项）文华剧社2项附件三：体育竞赛奖获得者名单1、第十四届全国大学生乒乓球锦标赛3200元/人：陈畅1600元/人：苗文静唐兴亮马明玉1400元/人：叶磊王珂1200元/人：徐文静杨婧600元/人：柳炜赵伟栋周迪400元/人：舒悦熊丽刘珍媛200元/人：郑华马屹南2、第三届中国大学生排球联赛3000元/人：陈琪俊殷立柱王鹤翔张双旺杨璐源沈筱庆1500元/人：周清张拂天车轶郭靖汤旭磊周昌之3、第四届中国大学生沙滩排球赛1200元/人：陈琪俊张双旺4、第十二届全国大学生羽毛球锦标赛2900元/人：饶闻宇2400元/人：黄粲林皓2100元/人：杨震1200元/人：宾执朝李正楠叶晨400元/人：邢星金彦妘5、2008年湖北省高校田径运动会1625元/人：胡冰彭娅丹1525元/人：刘思偲1437.5元/人：梁振东1377.5元/人：王兵1300元/人：张伟1175元/人：孙祚洋1162.5元/人：吴忌1000元/人：李英875元/人：孙琳凯737.5元/人：雷畅650元/人：覃卫平625元/人：刘丽娜600元/人：肖龙525元/人：张亚鹏6、中国大学生足球联赛“李宁杯”湖北赛区比赛375元/人：杜鹏君宋鲁任然多布杰俞嵩张一阿不都热而提阿不都米吉帕热撒提刘宏金佘剑涛187.5元/人：刘博艾力阿不都瓦热斯施鹏陈冠宁张志龙王德栋罗喻张可竞李伟孙亮王蔚佳艾克拜尔7、2008年湖北省高校羽毛球赛1350元/人：依俊楠900元/人：饶闻宇叶晨操超800元/人：程翀李惠明750元/人：陈瀑700元/人：张君莉徐雪芳李倩姜涛600元/人：黄粲550元/人：胡佳辰450元/人：邢星金彦妘甘华文丁世东350元/人：杨震林皓魏婉300元/人：宾执朝李正楠林澄8、2008年湖北省高校女子排球赛1050元/人：付祯寰周真乔英莉李倩张方余梦琦525元/人：李佳宝陈飞傅芬宗静怡陆可欣刘超君9、2008年湖北省高校男子排球赛900元/人：孙荣辉黄忠平王焕楠李翔米源刘根450元/人：胡骞毛骞高元江张拯昊肖旺黄勇10、2008年湖北省大学生乒乓球锦标赛1550元/人：周迪1375元/人：王珂1350元/人：鄢斌1125元/人：苗文静1050元/人：谢珺黎毅900元/人：郑华700元/人：陈畅450元/人：邓力合胡鸿图钟宇航潘峰350元/人：杨丹妮吴梦300元/人：刘珍媛200元/人：湛玉婷100元/人：邓磊11、2008年湖北省大学生武术比赛1250元/人：张东涂东方李胜楠张晓文王馨怡1050元/人：王维张南南角田美贵950元/人：孙玉超刘珠妹张斯芬550元/人：俞少俊齐新燕500元/人：王程谦112.5元/人：郝明祥胡桓浚薛蛟马雷宗何川12、2008年湖北省高校女子篮球赛1050元/人：叶晨朱燕娜吴蕾李敏璐张燕华525元/人：陈哲刘美琴刘安琪刘梦龄李瑞芳王丽君陈佩13、2008年湖北省高校男子篮球赛375元/人：唐牛王航叶圣彬蔡佰钊曹宁187.5元/人：许鑫洪一榕高海波葛伟姜辛魏泽张力14、2008年湖北省高校体育舞蹈比赛1150元/人：韩潇900元/人：陶格李娜750元/人：胡华贤曾景575元/人：李聪谭爽500元/人：吕海霞唐甜郑庆安450元/人：张研熊思思陈俩刘仁莉申辰马娟225元/人：刘婷婷罗云潭邹甑莹周捷李春梦翁蓝天陈雪娇15、2008年湖北省高校女子网球团体比赛900元/人：袁昳董妍玲童彤江梦颖朱量余维仪蔡东华450元/人：高侦影柳溜张仪万涛16、2008年湖北省高校男子网球团体比赛600元/人：金钱炜石润孙颖魏昀昭李诗韵肖骁张博均300元/人：董劫孙浩17、第十七届“应氏杯”中国大学生女子围棋赛全国第6名（1200元/集体）武汉大学代表队附件四：社会实践奖获得者名单1、2008年度全国大中专学生志愿者暑期“三下乡”社会实践活动全国一等奖（1000元/集体）武汉大学赴四川绵阳灾区医疗及心理援助志愿服务队2、2008年度湖北省大中专学生志愿者暑期“三下乡”社会实践活动省部级一等奖（500元/集体）武汉大学研究生赴赤壁等地挂职锻炼实践队武汉大学西部助学工程受助学生赴内蒙古实践队武汉大学“关注留守儿童”赴中西部农村服务实践团武汉大学“行走中华，寻访五百强”服务大学生就业创业实践团武汉大学赴四川绵阳灾区医疗及心理援助志愿服务队武汉大学赴北京市奥运志愿服务实践队武汉大学赴神农架野外考察实践队武汉大学“国内临终关怀模式”现状调查分析实践队武汉大学“科技奥运传播先锋”实践队武汉大学城建档案的灾备与研究实践队武汉大学循环经济与节能减排在两型社会中的作用实践队武汉大学“豪迈西行”实践队武汉大学关于中部崛起过程中的武汉、郑州经济发展模式调研实践队武汉大学防震减灾--遥感先行科研实践队武汉大学抗震救灾“爱心病房”志愿服务实践队武汉大学赴神农架林区医疗服务暑期社会实践博士团省部级优秀奖（80元/人）基础医学院：张力国际软件学院：冯广威继续教育学院：王颖第二临床学院程：王堃电气工程学院：杨龙外国语言文学学院：张申威资源与环境科学学院：陈文方水利水电学院：唐栋数学与统计学院：刘小东政治与公共管理学院：王中政法学院：唐盼药学院：陈锂城市设计学院：李文姝文学院：杨柳谢旭杰电子信息学院：唐瑞物理科学与技术学院：王琳化学与分子科学学院：杜勇计算机学院：陈华经济与管理学院：高尚杰附件五：精神文明奖获得者名单1、第七届中国百个优秀志愿服务集体全国标兵级（2000元/集体）武汉大学青年志愿者协会2、2008年省级“五四”评优省部级普通级（1000元/集体）武汉大学经济与管理团委省部级普通级（800元/人）电子信息学院：唐瑞3、第四届湖北省志愿服务奖省部级标兵级（1500元/集体）武汉大学青年志愿者协会省部级普通级（1000元/集体）武汉大学团委“珞珈爱心仓储”志愿服务项目省部级普通级（800元/人）社会学系：魏昊星外国语言文学学院：张梦颖文学院：范云鹿4、2008年思想政治教育进网络工作积极分子名单（共35人）校级普通级（200元/人）政治与公共管理学院：宋杨经济与管理学院：姜旖张倩杨波余昊陈钰君刘皓国际软件学院：刘一丁鄢榆荣满辰亮电气工程学院：郑杰计算机学院：文羽中法学院：张杰宋璧君文学院：张彤霞陆珏媛新闻与传播学院：刘洲贺佳袁喆李怡然付帧张婉杨心田徐燧信息与管理学院：王庭义徐淑乔艺术学系：孙伟春李望动力与机械学院：萧国能张立超遥感信息工程学院：陈自强外国语言文学学院：唐倬电子信息学院：丁建哲学学院：张卓资源与环境科学学院：宋奇鸿5、武汉大学2008学年度学生勤工助学先进个人名单（共161人）校级普通级（200元/人）文学院：严利琼周雯王丹丹历史学院：雷旭丹吴旭张香宋雅娟哲学学院：董文龙丁刚山珊马双兵张丽平唐伟芳吴海霞李世锋艺术学系：鲁蒂外国语言文学学院：赵玉凤饶洋洋新闻与传播学院：付修刚靳玉娥姚四方李新丽王书章经济与管理学院：朱叶领刘芳邵屹莹朱晶晶乔云华刘升有刘洋杨波法学院：姜晓李少文朱瑜王传龙印通李伦李娅裴小满信息管理学院：陈林陈亚森周亚黄路漫张龙忠曾光福社会学系：黄婷周辉剑政治与公共管理学院：孙鑫李永真汪漭何娇王平李江加略宋杨数学与统计学院：贾建卫阮姗物理科学与技术学院：尤娜姚弟吴诚吴江湖化学与分子科学学院：陈瑶李欢刘见功生命科学学院：李继灿李玉恒资源与环境科学学院：陈梦雪韦学成王钰邱庆唐雪梅柯生学杜苹谢锦威水利水电学院：阿不都艾尼·阿不里毛冰李少林屈春梅罗海勇雷成魏飞罗开莎段中德杨昊龙张坤熊玉江赵红颖电气工程学院：马占军万伟民余志飞岳浩江政朱迟锐洪明学马国威胡尧尧向权舟动力与机械学院：龙也马海泉钟全斌燕志鹏王琮翔萧国能耿振鹏卜淑贤高威盛泉建城市设计学院：赵虎土木建筑工程学院：游道炎潘红宝李姣阮从威张晓凤计算机学院：于永伟谢仁泰郑尊李振钊史华新电子信息学院：施智强文舰孙廷乙蒋新新薛德恒遥感信息工程学院：李亮曾也鲁汪奎熊杰杨金鑫艾明耀测绘学院：向锋张文余利波薛蛟赵云祥王健峰药学院：耿俊辉安素珍国际软件学院：于阳谭建坤印刷与包装系：阮海贵李涛基础医学院：别文倩廖海含哈力旦·阿布都于洋龚东魁艾罗燕周龙刘三河周锦屏张雪荣张荣张顺来第一临床学院：王璐曹红李金芯第二临床学院：类成林黎清波翟飞石义华口腔医学院：郑云飞。

863软件园杯第一届河南省大学生程序设计竞赛(正式比赛试题)100主办：河南省计算机学会承办：郑州大学信息工程学院协办：YOCSEF郑州分论坛地点：郑州大学南校区软件学院时间：2008年5月18日【试题一】灾区已经非常困难，灾民需要帐篷、衣物、食品和血浆。

可通往灾区的道路到处都是塌方，70%以上的路面损坏，桥梁全部被毁。

中国空军立即启动应急预案，展开史上最大强度非作战空运行动，准备向灾区空投急需物资。

由于余震不断，天气恶劣，怎样知道空投的物资是否落在某灾区的区域内？经过空中观测，多数灾区为一圆形，空投的物资落在P(X,Y)点。

你能否给出一个正确判断？【标准输入】第1行：N ( N为灾区数)接下有N行：Ri Xi Yi（Ri为圆半径（Xi ，Yi）为空投物资的坐标i=1, 2, …., N ）【标准输出】输出有N行，每行为YES (若物资落在灾区所在的圆上或圆内，输出YES或NO否则输出NO）【约束条件】（1） 3 ≤N≤ 10（2）Ri是一个正整数Ri <=100 i=1, 2, …., N（3）Xi Yi均为整数 -100≤ Xi ，Yi ≤100 i=1, 2, …., N（4）假设所有圆的圆心坐标均为（0，0）（5）时间限制：1000MS【样例】据不完全统计，受地震影响，四川大部分灾区通信陷入瘫痪，数千个基站因断电、传输中断等原因退出服务，目前总公司已紧急部署对受灾地区进行通信抢修。

按照应急通信保障预案，必须尽快、付出代价最小，效率更高来全力恢复通信。

由于四川大部分灾区都处于山区，有很多基站之间不能直接建立通信。

现已知建立各基站之间直接通信的代价，问如何建立总代价最小的通信网，使得任意两个基站之间都能通信？【标准输入】第1行：N M(N为基站数M为能直接建立通信关系数)接下有M行：I J P（每行有三个数。

I J 为基站的编号P为基站I与基站之间直接通信的代价）【标准输出】T（建立通信网的最小代价数）【约束条件】（1）2 ≤N ≤100 10 ≤M≤1000（2） 0 < P ≤ 1000 P为正整数（3）时间限制：1000MS【样例】密码破译某组织欲破获一个外星人的密码，密码由一定长度的字串组成。