2004ACM杯比賽往年試題集錦.doc

參賽資格與報名：1、參賽者的范圍包括：各高校在校本科生、碩士生、博士生，以及被北京大學預錄取的應(yīng)屆高三保送生。其他人員如欲報名，請先詢組委會。2、競賽以組隊形式進行，每支隊伍一名、兩名或三名隊員，設(shè)隊長一名。3、參賽隊在截止時間前下載報名表并提交，組委會在收到報名后會給予回復。4、外校參賽隊如有需要，可向組委會申請?zhí)峁┭埡?、本次競賽不收取報名費。競賽流程與規(guī)則：1、參賽者應(yīng)當在競賽的前一天查看競賽網(wǎng)站，或檢查報名時所留的郵箱，以了解第二天競賽細節(jié)方面可能的變動，并閱讀最新通知。2、參賽者須攜帶以下證件進入考場： * 校園卡或?qū)W生證（北京大學在校生） * 學生證，和有效身份證件（其它高校在校生） * 學生證、北京大學預錄取通知書，和有效身份證件（應(yīng)屆高三保送生） 有效身份證件，是指以下證件之一：身份證、護照、往來港澳通行證，或戶口簿（僅適用于未滿16周歲的參賽者）。3、參賽者可以攜帶書、手冊、英語詞典、程序清單等紙質(zhì)參考資料；但不得攜帶任何電子媒質(zhì)的資料，例如移動硬盤、U盤、光盤、電子詞典等。4、每支隊伍只能使用一臺計算機，所有隊伍使用計算機的規(guī)格配置均相同。5、競賽時可能會提供打印服務(wù)，參賽者可向賽場工作人員提出。6、競賽當天提供飲用水、巧克力（或其它食品），無需自備午餐。評獎：1、參賽隊正確解答試題的數(shù)量，是評獎的依據(jù)。2、如果多支隊伍解題數(shù)量相同，則根據(jù)總用時加上懲罰時間進行排名?？傆脮r和懲罰時間由每道解答正確的試題的用時加上懲罰時間組成。每道試題用時將從競賽開始到試題解答被判定為正確為止，期間每一次錯誤的提交將被加罰20分鐘時間，未正確解答的試題不計時。3、競賽設(shè)一、二、三等獎，具體數(shù)量由組委會在競賽結(jié)束后，根據(jù)結(jié)果決定。4、競賽設(shè)最佳女生獎，頒給排名最高的女生隊。所謂女生隊，是指所有隊員均為女生的參賽隊。硬件平臺： CPU 3.0GHz(HT) RAM 1GB 硬盤 80GB 顯示器 17英寸 鍵盤 國際標準鍵盤 鼠標 光電鼠標軟件平臺： Windows 2000 Professional 或 Windows XP Microsoft Visual C+ 6.0 Eclipse 3.2 Dev-C+ 4.9.9.2 AreaTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 6845Accepted: 1856DescriptionYou are going to compute the area of a special kind of polygon. One vertex of the polygon is the origin of the orthogonal coordinate system. From this vertex, you may go step by step to the following vertexes of the polygon until back to the initial vertex. For each step you may go North, West, South or East with step length of 1 unit, or go Northwest, Northeast, Southwest or Southeast with step length of square root of 2. For example, this is a legal polygon to be computed and its area is 2.5: InputThe first line of input is an integer t (1 = t = 20), the number of the test polygons. Each of the following lines contains a string composed of digits 1-9 describing how the polygon is formed by walking from the origin. Here 8, 2, 6 and 4 represent North, South, East and West, while 9, 7, 3 and 1 denote Northeast, Northwest, Southeast and Southwest respectively. Number 5 only appears at the end of the sequence indicating the stop of walking. You may assume that the input polygon is valid which means that the endpoint is always the start point and the sides of the polygon are not cross to each other.Each line may contain up to 1000000 digits.OutputFor each polygon, print its area on a single line.Sample Input4582567256244865Sample Output000.52SourcePOJ Monthly-2004.05.15 Liu RujiaPOJSubmit Go Back Status Discuss Home Page Go BackTo topAll Rights Reserved 2003-2007 Ying Fuchen,Xu Pengcheng,Xie DiAny problem, Please Contact Balancing ActTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 4447Accepted: 1756DescriptionConsider a tree T with N (1 = N = 20,000) nodes numbered 1.N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T. For example, consider the tree: Deleting node 4 yields two trees whose member nodes are 5 and 1,2,3,6,7. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: 2,6, 3,7, and 4,5. Each of these trees has two nodes, so the balance of node 1 is two. For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number. InputThe first line of input contains a single integer t (1 = t = 20), the number of test cases. The first line of each test case contains an integer N (1 = N = 20,000), the number of congruence. The next N-1 lines each contains two space-separated node numbers that are the endpoints of an edge in the tree. No edge will be listed twice, and all edges will be listed.OutputFor each test case, print a line containing two integers, the number of the node with minimum balance and the balance of that node.Sample Input172 61 21 44 53 73 1Sample Output1 2SourcePOJ Monthly-2004.05.15 IOI 2003 sample taskSubmit Go Back Status Discuss Home Page Go BackTo topAll Rights Reserved 2003-2007 Ying Fuchen,Xu Pengcheng,Xie DiAny prCounting BlackTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 6990Accepted: 4448DescriptionThere is a board with 100 * 100 grids as shown below. The left-top gird is denoted as (1, 1) and the right-bottom grid is (100, 100). We may apply three commands to the board: 1.WHITE x, y, L / Paint a white square on the board, / the square is defined by left-top grid (x, y) / and right-bottom grid (x+L-1, y+L-1)2.BLACK x, y, L / Paint a black square on the board, / the square is defined by left-top grid (x, y) / and right-bottom grid (x+L-1, y+L-1)3.TEST x, y, L / Ask for the number of black grids / in the square (x, y)- (x+L-1, y+L-1) In the beginning, all the grids on the board are white. We apply a series of commands to the board. Your task is to write a program to give the numbers of black grids within a required region when a TEST command is applied. InputThe first line of the input is an integer t (1 = t = 100), representing the number of commands. In each of the following lines, there is a command. Assume all the commands are legal which means that they wont try to paint/test the grids outside the board.OutputFor each TEST command, print a line with the number of black grids in the required region.Sample Input5BLACK 1 1 2BLACK 2 2 2TEST 1 1 3WHITE 2 1 1TEST 1 1 3Sample Output76SourcePOJ Monthly-2004.05.15 Liu RujiaPOJSubmit Go Back Status Discuss Home Page Go BackTo topAll Rights Reserved 2003-2007 Ying Fuchen,Xu Pengcheng,Xie DiAny problem, Please Distance on ChessboardTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 16356Accepted: 5719Description國際象棋的棋盤是黑白相間的8 * 8的方格，棋子放在格子中間。如下圖所示： 王、后、車、象的走子規(guī)則如下： 王：橫、直、斜都可以走，但每步限走一格。 后：橫、直、斜都可以走，每步格數(shù)不受限制。 車：橫、豎均可以走，不能斜走，格數(shù)不限。 象：只能斜走，格數(shù)不限。寫一個程序，給定起始位置和目標位置，計算王、后、車、象從起始位置走到目標位置所需的最少步數(shù)。 Input第一行是測試數(shù)據(jù)的組數(shù)t（0 = t = 20）。以下每行是一組測試數(shù)據(jù)，每組包括棋盤上的兩個位置，第一個是起始位置，第二個是目標位置。位置用字母-數(shù)字的形式表示，字母從a到h，數(shù)字從1到8。 Output對輸入的每組測試數(shù)據(jù)，輸出王、后、車、象所需的最少步數(shù)。如果無法到達,就輸出Inf.Sample Input2a1 c3f5 f8Sample Output2 1 2 13 1 1 InfSourcePOJ Monthly-2004.05.15 Liu RujiaPOJSubmit Go Back Status Discuss Home Page Go BackTo topAll Rights Reserved 2003-2007 Ying Fuchen,Xu Pengcheng,Xie DiAny problem, Please Contact Evas ProblemTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 12313Accepted: 7497DescriptionEva的家庭作業(yè)里有很多數(shù)列填空練習。填空練習的要求是：已知數(shù)列的前四項，填出第五項。因為已經(jīng)知道這些數(shù)列只可能是等差或等比數(shù)列，她決定寫一個程序來完成這些練習。Input第一行是數(shù)列的數(shù)目t（0 = t = 20）。以下每行均包含四個整數(shù)，表示數(shù)列的前四項。約定數(shù)列的前五項均為不大于105的自然數(shù)，等比數(shù)列的比值也是自然數(shù)。Output對輸入的每個數(shù)列，輸出它的前五項。Sample Input21 2 3 41 2 4 8Sample Output1 2 3 4 51 2 4 8 16SourcePOJ Monthly-2004.05.15 NullSubmit Go Back Status Discuss Home Page Go BackTo topAll Rights Reserved 2003-2007 Ying Fuchen,Xu Pengcheng,Xie DiAny problem, Please Contact Frogs NeighborhoodTime Limit: 5000MSMemory Limit: 10000KTotal Submissions: 2985Accepted: 1242Special JudgeDescription未名湖附近共有N個大小湖泊L1, L2, ., Ln(其中包括未名湖)，每個湖泊Li里住著一只青蛙Fi(1 i N)。如果湖泊Li和Lj之間有水路相連，則青蛙Fi和Fj互稱為鄰居?，F(xiàn)在已知每只青蛙的鄰居數(shù)目x1, x2, ., xn，請你給出每兩個湖泊之間的相連關(guān)系。Input第一行是測試數(shù)據(jù)的組數(shù)T(0 T 20)。每組數(shù)據(jù)包括兩行，第一行是整數(shù)N(2 N 10)，第二行是N個整數(shù)，x1, x2,., xn(0 xi N)。Output對輸入的每組測試數(shù)據(jù)，如果不存在可能的相連關(guān)系，輸出NO。否則輸出YES，并用NN的矩陣表示湖泊間的相鄰關(guān)系，即如果湖泊i與湖泊j之間有水路相連，則第i行的第j個數(shù)字為1，否則為0。每兩個數(shù)字之間輸出一個空格。如果存在多種可能，只需給出一種符合條件的情形。相鄰兩組測試數(shù)據(jù)之間輸出一個空行。Sample Input374 3 1 5 4 2 1 64 3 1 4 2 0 62 3 1 1 2 1 Sample OutputYES0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 NOYES0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 SourcePOJ Monthly-2004.05.15 AlcyonepkuSubmit Go Back Status Discuss Home Page Go BackTo topAll Rights Reserved 2003-2007 Ying Fuchen,Xu Pengcheng,Xie DiPrincess FroGTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 1115Accepted: 464DescriptionLong, long ago there was a monster lived in Adventure Castle of Magic. One day he saw that the prince Infante Concord and his wife Princess Charm were living so sweet a life. Couldnt help becoming jealous, he used his powerful magic to turn the prince to an ugly frog. The brave and smart princess made up her mind to rescue her husband. After overcomed thousands of difficulties and challenges, she finally arrived at the Adventure Castle of Magic. When she saw her dearest handsome husband had become an ugly and awful frog by the curse of the monster, her heart almost broken. The monster gave her a very hard puzzle as a condition to exchange the prince. The princess was required to choose the right ones from some given ropes. A right rope means that the rope wouldnt make a knot by pulling up its two ends. If the princess chose all the right ones, the curse would disappear and the price would be rescued, otherwise he would be strangled to death. In order to rescue her husband, without hesitation, the princess accepted the challenge. Here are two example ropes. Figure_1 is a right rope while Figure_2 is not a right rope: Figure_1InputThe first line of the input is an integer t (1 = t = 20), representing the number of ropes. Each of the following lines describes a rope. We describe the rope by pointing out the cross-point (See Figure_2). We first number all the cross-point. Then, our fingers go along the rope from one end to the other, whenever we encounter a cross-point we will record its number on the paper. If the rope goes above the point, we write down a positive number. If the rope goes under the point, we write down a negative number. In the end, we put a zero as an end sign. For example, the rope shown in Figure_2 is recorded as: +1 -2 +3 -4 +5 -6 -7 +8 +2 -1 -10 +9 -8 -3 +4 -5 +6 +7 -9 +10 0 Figure_2OutputFor each rope, output one line. If the rope will make a knot by pulling up its ends, output Not right. Otherwise, output Right. Sample Input3+1 -1 0-1 -2 -3 +1 +2 +3 0+1 -2 +3 -4 +5 -6 -7 +8 +2 -1 -10 +9 -8 -3 +4 -5 +6 +7 -9 +10 0Sample OutputRightRightNot rightSourcePOJ Monthly-2004.05.15 duoshutepkuSubmit Go Back Status Discuss Home Page Go BackTo topAll Rights Reserved 2003-2007 Ying Fuchen,Xu Pengcheng,Xie DiAny problem, Please Help JimmyTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 5864Accepted: 1789DescriptionHelp Jimmy 是在下圖所示的場景上完成的游戲。 場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。 Jimmy老鼠在時刻0從高于所有平臺的某處開始下落，它的下落速度始終為1米/秒。當Jimmy落到某個平臺上時，游戲者選擇讓它向左還是向右跑，它跑動的速度也是1米/秒。當Jimmy跑到平臺的邊緣時，開始繼續(xù)下落。Jimmy每次下落的高度不能超過MAX米，不然就會摔死，游戲也會結(jié)束。