华南师范大学ACM初赛题.doc

2010华南师范大学ACM程序设计竞赛初赛注意事项：1， 题目一共有10个2， 题目有严格的时间限制，请做好程序的优化3， 题目采用标准读入，标准输出If the problem is a+b,Then the code is:C: #include int main(void) int a, b; while(scanf(%d%d, &a, &b)!=EOF) printf(%d, a + b); return 0;C+: #include using namespace std;int main(void) int a, b; while(cin a b) cout a + b; return 0; Java : import java.util.Scanner;public class Main public static void main(String args) Scanner in = new Scanner(System.in); int a = in.nextInt(); int b = in.nextInt(); System.out.println(a + b); 4, 即时的排名和各队解题情况，可访问35/summary.html5, 比赛中不能使用电子设备，如U盘、手机等，一旦发现，立即取消比赛资格6, 登录PC2，单击pc2team.bat ,用户名和密码皆为team*（*为你们队伍编号）Problem ATime Limit: 1000 mSecMemory Limit : 65535 KBProblem Description The algorithm of matching String is based knowledge of ACMer,including Rabin-Karp, Knuth-Morris-Pratt , and AC automaton etc. Our Fat LYF has learned them in heart well , but “Transforming letters from Upper case to lower case,or lower case to Upper case, which depends on the letter given” this problem daunts him. As a smart programmer, you can solve it without doubt.Input Multiple test cases, for each case, youve got only one letter as an input. Input terminated by EOF. Output Output one letter per line for each case.Sample Input aSample OutputAProblem BTime Limit: 1000 mSecMemory Limit : 65535 KBProblem Description This is a problem you can find easily in your C/C+ book. Given the lengths of three segments, if those segments could form a triangle, tell the square of the triangle , otherwise just output“Error”.Input Multiple test cases ,Three numbers a,b,c in Integer Type.（0a,b,c=108）OutputThe required square value(rounded to integer) or “Error”. Sample Input 3 4 5Sample Output6Problem CTime Limit: 1000 mSecMemory Limit : 65535 KBProblem DescriptionThis is also a problem you can find easily in your C/C+ book. Its well-known that the famous formula =,now youre given the number n,please tell the approximate value of guided by .Input Multiple test cases , An integer n （1n104）Output One real number per line, rounded to .Sample Input1Sample Output2.66666667Problem DTime Limit: 2000 mSecMemory Limit : 65535 KBProblem DescriptionAs we all know, girls love necklaces, especially nice necklaces. Recently, LYF has fallen in love with a girl whose name is *; he wants to bring her a necklace as a gift. Now he has n colors, and the necklace is circular and it has n beads, LYF can use his colors to color the necklace. he wants to know how many different kinds of necklaces he can make，he may not use all the n colors. In this problem, the necklace is same when you rotate it around the center of the necklace or turn it over.Input First line is the test case T. Following T lines, each line is an integer n ( 1 n 109 )OutputOutput the answer mod 20090531.Sample Input41234 Sample Output131055Problem ETime Limit: 1000 mSecMemory Limit : 65535 KBProblem Description Sir Wang is our drill master and our amicability .One day, Sir Wang cuts a string S into N pieces, s1,sN. Now, Wang Sir gives you these N sub-strings : s1, ,sN. There might be several possibilities that the string S could be. For example, if Dr Wang gives you three sub-strings “a”,”ab”,”ac”, the string S could be” aabac”,”aacab”,”abaac”, Your task is to output the lexicographically smallest S.InputThe first line of the input is a positive integer T.T is the number of the test cases followed. The first line of each case is positive integer N (0N9) which represents the number of sub-strings.After that, N lines followed. The i-th line is the i-th sub-string si.Assume that the length of each sub-string is positive and less than 100.Output The output is each test is the lexicographically smallest S.No redundant spaces are needed.Sample Input13aabacSample OutputaabacProblem FTime Limit: 1000 mSecMemory Limit : 65535 KBProblem Description As We have Known, Little LYF is daffy at MATHS and always crows about himself when chatting to others. All these things giving an incorrect impression to younger learners in CS & MA. One day, his * want to test how clever he is , she gives him several formula like “variable1 relation variable2”,where relation may be , =,variables may contain up to 10 letters or digits and are case=sensitive. The task is to determine whether there is conflict. O()o Now ,he betrays himself with the strong feel of Tears and Penitence. O(_)O As a smart and compassionate programmer, pleases give him a strong hand.Input There are several cases. Each case begins with a line “Case %n:” (%n is the case number),and contains several formulas, one per line. There are no more than 100 formulas for each case. Please see sample for more details. Input is terminated by EOF.OutputIf there is no conflict, output” YES”, otherwise, output” NO”. Please refer to sample output for the exact output format.Sample InputCase1:xyz12312345Case2:xyyb , bc, then ac and ac is both regarded correct propositions.Problem GTime Limit: 2000 mSecMemory Limit : 65535 KBProblem DescriptionLYF is a lazy and smart boy in his words. So he is trying to develop an examine system under the directive book. He finds it not so easy to judge filling question. There may be multiple answers for a blank, For example, The 2008 Olympic games was hold in _City，The answer can be “Beijing”, and it can also be “Peking”, he made the answer like this: Beijing(Peking), which means that Beijing, Peking are both correct answers; A filling question may have several blanks, For some problems those blanks should be answered in order, for example, The 2000, 2004 Olympic games was hold respectively in _City and _City, The answer should be “Sydney Athens”; For other problems those blanks dont need be answered in order, for example, ACRush has taken part in the ICPC world finals in the year _ and _, The answer could be “2007|2009”, and it can also be “2009|2007”. Now you are required to help him to write a program to judge the filling problems.InputThe first line contains an integer N, indicate the number of problems. The following N*3 lines, each 3 lines indicate a filling problem, the first line is the question, the second line is the answer(There will not be a answer contains |, (, ) for every blank, For one problem every neighboring blanks are separated by “|” ), the third line indicate if the blanks should be filled in order, the word “True” means the blanks should be filled in order while “False” means that filling the blanks in order is not necessary. The following line contains an integer M, indicate the number of person, each person will fill all the problems, so there follows N*M lines, each N lines indicate a persons answer for the N problems (There will not be a answer contains |, (, ) for every blank, For one problem every neighboring blanks are separated by “|” ), according to the sequence of the N problems.OutputThere are M lines, for each person, write the number of blanks he/she filled correctly.Sample Input3The 2004, 2008 Olympic Games was hold respectively in _City and _City.Athens|Beijing (Peking)TrueACRush has taken part in the ICPC world finals in the year _ and _.2007|2009FalseAaaa_bbbb_.Ccc(cc)|Ddd(dd)False2Athens|Beijing2007|2009Dd|ccBeijing|Athens2009|2008Ddd|ccSample Output53Tips: For each question, any two of the blanks have different answers.Problem HTime Limit: 3000 mSecMemory Limit : 65535 KBProblem DescriptionSupernatural Cow LYF has developed a new kind of multi-core CPU, it works as follow. There are q (1 q 50) identical cores in the CPU, and there are p (0 p 200) jobs need to be done. Each job should run in some core and need only one unit time. The cores in the CPU can work simultaneously but each core can implement only one job at a time. When a job completed, it will incur a deferral cost. Job i has a deferral cost c(i, j) (0 c(i, j) 1000000), where j is the completion time of the job (1 j p because any job done in the time later than p obviously not the optimal solution). Here we assume that c(i, j) is a monotonically no decreasing function of j. Now you are asked to find the schedule which have the minimum overall deferral cost. Input An integer T indicated the number of test cases. For each test case: And Following is p lines, each line contain p integer, the jth integer of the ith line is the deferral cost c(i, j). Output For each test case, output a singer integer, which is the minimum total deferral cost of the Problem.Sample Input12 489 145 181 2694 86 158 16460 143 157 1654 45 109 207Sample Output254Hint； The idea of Cost-Flow is available.Problem ITime Limit: 1000 mSecMemory Limit : 65535 KBProblem DescriptionA triangle is the most beautiful image in the world in LYFs mind. So please help to print a triangle with the Upper letters.InputMultiple test cases, one integerN (0N27) OutputA triangle of