第31届ICPC北京赛区网络试题(C,D)(页 1) - 网络技术

蓝色神话 发表于 2006-10-11 12:01

第31届ICPC北京赛区网络试题(C,D)

Encryption(C) Time Limit:5S Memory Limit:32768K Description Country C recently intercepts a telegram from enemy army, but the telegram is encrypted. Analysis indicates that it is encrypted in WLE method. The decoding team spends a week to make a decoding solution: The encrypted message is a non-decreasing nonnegative integer sequence with the length of m. The decoding solution consists of several steps, each of which is one of the following cases: 1. Subtract a positive integer from every number in the sequence, then delete negative terms. 2. Delete the first t terms of the sequence (t is a positive integer). If t is bigger than the length of the sequence, the sequence is empty. 3. Generate a new sequence with the same length as the original one. The nth term in the new sequence is the number of terms that are smaller than n in the original sequence. (n=1,2,...) As a senior software engineer of Country C, you need to make a decoder. Input Input consists of multiple test cases. Each case begins with a line containing n (100<=n<=10000), the length of the encrypted sequence, followed by n nonnegative integers in non-decreasing order. The next line contains m (100<=m<=10000), the number of decoding steps. The following m lines specify the operation of each step in such format as (corresponding to the problem description): The first case: a single character 'M' followed by a positive integer. The second case: a single character 'D' followed by a positive integer. The third case: a single character 'N'. There is no blank between the character and the integer. Every positive integer except m and n is less than or equal to 50. The last case is followed by a line containing a zero. Output For each case, output the decoded sequence. If the decoded sequence is empty, output 'Empty'. Sample Input 5 1 2 3 4 5 3 M1 D1 N 5 1 2 3 4 5 3 M1 D1 N 5 1 2 3 4 5 1 D10 0 Sample Output Case 1: 0 1 2 3 Case 2: 0 1 2 3 Case 3: Empty

Genius(D) Time Limit:1.5S Memory Limit:65536K Description For each natural number N (N>0), Primary school students know if there exists an integer a, such that a2=N, then N is a perfect square. Junior school students know if sqrt(N) is an irrational number, N is not a perfect square(square-free). High school students know that N is a perfect square if and only if there exists two positive integers X and Y, such that N=X2/Y2. College students know that N is square-free if and only if there exists two positive integers X and Y, such that N=(X2-1)/Y2. As a mathematics and programming genius, you know far more than them. Not only are the above four simple propositions a piece of cake to you, but also you can tell them how much X and Y are for each square-free N, such that (X2-1)/Y2=N. You need to write a program which inputs an integer N and outputs X and Y. Such X and Y may be multiple. Please output the minimum X and Y. Input The input consists of several test cases. Each test case is in a separate line, and consists of a single integer in the range 1 ... 10^8. The last case is followed by a line containing an integer zero. Output For each test case, display a line that contains X and Y. if either X or Y is greater than or equal to 10^1000, output 'No solution!'. Sample Input 3 57 81 0 Sample Output Case 1: 2 1 Case 2: 151 20 Case 3: No solution!

页: [1]