模擬題專場了，無語。。。
C
Chinese Zodiac
Time Limit: 2 Seconds Memory Limit: 65536 KB
The Shengxiao , better known in English as the Chinese Zodiac, is a scheme that relates each year to an animal and its reputed attributes, according to a 12-year cycle. The zodiac traditionally begins with the sign of the Rat, and the twelve zodiac signs are Rat, Ox, Tiger, Rabbit, Dragon, Snake, Horse, Ram, Monkey, Rooster, Dog and Pig. The zodiac signs cycles continuously, and determines the animal or sign under which a person is born. This year (2011, more accurately Chinese Xin Mao Year -- 3 February 2011 - 22 January 2012) is the Chinese Year of the Rabbit, so the babies born in this year are said to be born under the Chinese Zodiac sign of the Rabbit.
In China, Xusui , also known as east Asian age reckoning, is used to count a person's age. Newborns start at one year old, and each passing of a Lunar New Year, rather than the birthday, adds one year to the person's age. In other words, the first year of life is counted as one instead of zero, so that a person is two years old in their second year, three years old in their third, and so on.
Given the traditional age ( Xusui ) of someone, you are requested to answer his zodiac sign ( Shengxiao ).
Input
There are multiple test cases. The first line of input is an integer T ≈ 1000 indicating the number of test cases.
Each test case contains only one positive integer y ≤ 200 -- the traditional age.
Output
For each test case, output a string -- the zodiac sign.
Sample Input
5
1
23
40
100
160
Sample Output
Rabbit
Snake
Rat
Rat
Rat
1 #include <iostream>
2 #include <cstdio>
3
4 using namespace std;
5
6 const char *shengxiao[] =
7 {
8 " ",
9 "Rat", "Ox", "Tiger", "Rabbit", "Dragon", "Snake",
10 "Horse", "Ram", "Monkey", "Rooster", "Dog", "Pig"
11 };
12
13 int main() {
14 int td, y, i, t;
15 scanf( "%d", &td );
16 while ( td-- > 0 ) {
17 scanf( "%d", &y );
18 t = 5 - y;
19 while ( t < 1 ) {
20 t += 12;
21 }
22 i = t;
23 puts( shengxiao[ i ] );
24 }
25 return 0;
26 }
27
D
Duck Typing
Time Limit: 2 Seconds Memory Limit: 65536 KB
If it looks like a duck, swims like a duck, and quacks like a duck, then it probably is a duck.
When I see a bird that walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck.
In computer programming with object-oriented programming languages, duck typing is a style of dynamic typing in which an object's current set of methods and properties determines the valid semantics, rather than its inheritance from a particular class or implementation of a specific interface.
Given a chunk of code, your task is to tell the function of each statement. Each statement is a line of one of the following formats:
- begin . This is always the first statement of the code.
- end . This is always the last statement of the code.
- class ClassName [: Super ]. Define a new class ClassName , with its superclass being Super if specified. If ClassName has been defined or Super has not been defined before, then ignore this statement and print "oops!". Otherwise, print " class ClassName [: Super ]".
- def ClassName . MethodName . Define a method named MethodName in class ClassName . If ClassName has never been defined, then ignore this statement and print "oops!". If this method has already been defined before, then print " redef ClassName . MethodName ". Otherwise print " def ClassName . MethodName ".
- undef ClassName . MethodName . If this method has not been defined or the class has not been defined, then ignore this statement and print "oops!". Otherwise, print " undef ClassName . MethodName " and this method is treat as if it has never been defined from now on.
- call ClassName . MethodName . Call the method ClassName . MethodName according the following principle. If the method ClassName . MethodName is defined, then invoke this method. If the class ClassName has superclass Super , then check its superclass recursively until the method is defined or there are no superclasses. Print the actual method invoked " invoke ActualClassName . MethodName " or ignore this statement and print "oops!".
All ClassName and MethodName are valid identifiers, namely a sequence of one or more ASCII letters, digits (these may not appear as the first character), and underscores. Both the length of the identifier and the depth of inheritance tree don't exceed 20.
Input
There are multiple test cases. The first line of input is an integer T ≈ 10 indicating the number of test cases.
Each test case is a chunk of code. There is a blank line after each test case.
Output
For each statement, output as the description says. Output a blank line after each test case.
Sample Input
3
begin
class Sub:Super
class Super
class Sub:Super
end
begin
class Class
call Class.Method
def Class.Method
call Class.Method
end
begin
class Super
class Sub:Super
def Super.Method
call Sub.Method
end
Sample Output
oops!
class Super
class Sub:Super
class Class
oops!
def Class.Method
invoke Class.Method
class Super
class Sub:Super
def Super.Method
invoke Super.Method
1 #include <iostream>
2 #include <cstdio>
3 #include <map>
4 #include <string>
5
6 using namespace std;
7
8 int main() {
9 map< string, string > father;
10 map< string, int > method;
11 map< string, int > defclass;
12 int td, i;
13 string cmd, me, fa, func;
14 cin >> td;
15 while ( td > 0 ) {
16 cin >> cmd;
17 if ( cmd == "begin" ) {
18 father.clear();
19 method.clear();
20 defclass.clear();
21 }
22 else if ( cmd == "end" ) {
23 --td;
24 // if ( td > 0 ) {
25 cout << "\n";
26 // }
27 }
28 else if ( cmd == "class" ) {
29 cin >> me;
30 if ( (i=me.find( ':' )) != string::npos ) {
31 fa = me.substr( i+1 );
32 me.erase( i );
33 if ( (defclass[me]==1) || (defclass[fa]==0) ) {
34 cout << "oops!\n";
35 }
36 else {
37 defclass[ me ] = 1;
38 father[ me ] = fa;
39 cout << "class " << me << ":" << fa << "\n";
40 }
41 }
42 else {
43 if ( defclass[ me ] == 1 ) {
44 cout << "oops!\n";
45 }
46 else {
47 defclass[ me ] = 1;
48 cout << "class " << me << "\n";
49 }
50 }
51 }
52 else if ( cmd == "def" ) {
53 cin >> func;
54 me = func.substr( 0, func.find('.') );
55 if ( defclass[me] == 0 ) {
56 cout << "oops!\n";
57 }
58 else if ( method[ func ] == 1 ) {
59 cout << "redef " << func << "\n";
60 }
61 else {
62 method[ func ] = 1;
63 cout << "def " << func << "\n";
64 }
65 }
66 else if ( cmd == "undef" ) {
67 cin >> func;
68 me = func.substr( 0, func.find('.') );
69 if ( (defclass[me]==0) || (method[func]==0) ) {
70 cout << "oops!\n";
71 }
72 else {
73 cout << "undef " << func << "\n";
74 method[ func ] = 0;
75 }
76
77 }
78 else if ( cmd == "call" ) {
79 cin >> func;
80 me = func.substr( 0, func.find('.') );
81 func.erase( 0, func.find('.')+1 );
82 while ( (!me.empty()) && (method[me+"."+func]==0) ) {
83 me = father[ me ];
84 }
85 if ( !me.empty() ) {
86 cout << "invoke " << me+"."+func << "\n";
87 }
88 else {
89 cout << "oops!\n";
90 }
91 }
92 }
93 return 0;
94 }
95
G
Gaussian Prime
Time Limit: 3 Seconds Memory Limit: 65536 KB
In number theory, a Gaussian integer is a complex number whose real and imaginary part are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i]. The prime elements of Z[i] are also known as Gaussian primes. Gaussian integers can be uniquely factored in terms of Gaussian primes up to powers of i and rearrangements.
A Gaussian integer a + bi is a Gaussian prime if and only if either:
- One of a, b is zero and the other is a prime number of the form 4n + 3 (with n a nonnegative integer) or its negative -(4n + 3), or
- Both are nonzero and a2 + b2 is a prime number (which will not be of the form 4n + 3).
0 is not Gaussian prime. 1, -1, i, and -i are the units of Z[i], but not Gaussian primes. 3, 7, 11, ... are both primes and Gaussian primes. 2 is prime, but is not Gaussian prime, as 2 = i(1-i)2.
Your task is to calculate the density of Gaussian primes in the complex plane [x1, x2] × [y1, y2]. The density is defined as the number of Gaussian primes divided by the number of Gaussian integers.
Input
There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.
Each test case consists of a line containing 4 integers -100 ≤ x1 ≤ x2 ≤ 100, -100 ≤ y1 ≤ y2 ≤ 100.
Output
For each test case, output the answer as an irreducible fraction.
Sample Input
3
0 0 0 0
0 0 0 10
0 3 0 3
Sample Output
0/1
2/11
7/16
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4
5 using namespace std;
6
7 void init() {
8 }
9
10 int gcd( int a, int b ) {
11 if ( b == 0 ) {
12 return a;
13 }
14 return gcd( b, a%b );
15 }
16
17 int isPrime( int n ) {
18 int i;
19 if ( n < 2 ) {
20 return 0;
21 }
22 for ( i = 2; i*i <= n; ++i ) {
23 if ( n % i == 0 ) {
24 return 0;
25 }
26 }
27 return 1;
28 }
29
30 int isGaussPrime( int a, int b ) {
31 a = abs( a );
32 b = abs( b );
33 if ( (a==0) && (b==0) ) {
34 return 0;
35 }
36 if ( b == 0 ) {
37 if ( (a<3) || ((a-3)%4) || (!isPrime(a)) ) {
38 return 0;
39 }
40 return 1;
41 }
42 if ( a == 0 ) {
43 if ( (b<3) || ((b-3)%4) || (!isPrime(b)) ) {
44 return 0;
45 }
46 return 1;
47 }
48 a = a*a + b*b;
49 return isPrime(a) && ( (a<3) || ((a-3)%4) );
50 }
51
52 int main() {
53 int td, x1, x2, y1, y2, i, j, cnt, fm, fz;
54 init();
55 scanf( "%d", &td );
56 while ( td-- > 0 ) {
57 scanf( "%d%d%d%d", &x1, &x2, &y1, &y2 );
58 cnt = 0;
59 for ( i = x1; i <= x2; ++i ) {
60 for ( j = y1; j <= y2; ++j ) {
61 cnt += isGaussPrime( i, j );
62 }
63 }
64 fm = (x2-x1+1)*(y2-y1+1);
65 fz = cnt;
66 i = gcd( fz, fm );
67 fz /= i;
68 fm /= i;
69 printf( "%d/%d\n", fz, fm );
70 }
71 return 0;
72 }
73
I
Identification Number
Time Limit: 3 Seconds Memory Limit: 65536 KB Special Judge
Mr. Wu, the inspector of the district, is really angry for a robbery happened last night. The robber escaped while Mr. Wu knows nothing about him. The only clue Mr. Wu has is a photo of the robber, which is recorded by the security camera.
Fortunately, the robber was seen by a witness in a train station, and his identity card was captured on a video camera when he was passing security check. As you know, each identity card in China has a unique identification number. Therefore Mr. Wu can easily find who the robber is by looking up the ID in computer database. But he failed, and found the number was not in the database. He guesses some digits in the identification number are misinterpreted because the picture of the robber's identity card is in bad quality.
To find the original identification number, Mr. Wu assumes that only a minimal number of characters are misinterpreted. While this assumption may be reasonable, he finds it hard for him to determine the correct number. So he turns you, a talented programmer, to help him find the correct answer.
To accomplish this task, you need to have some basic knowledge about identity cards used in China. There are two number system used for identification number, namely the first generation and the second generation. The first generation consists of a 15-digit code while the second generation consists of an 18-digit code. See following tables for details.
Number system for the first generation identity card
| 1 |
2 |
3 |
4 |
5 |
6 |
Y |
Y |
M |
M |
D |
D |
8 |
8 |
8 |
| Address code |
Date of Birth |
Order code |
Number system for the second generation identity card
| 1 |
2 |
3 |
4 |
5 |
6 |
Y |
Y |
Y |
Y |
M |
M |
D |
D |
8 |
8 |
8 |
X |
| Address code |
Date of Birth |
Order code |
Checksum |
The identification number must obey the following constraints:
- The address code refers to the resident's location. For simplicity, here we consider any digits are legal.
- The Date of Birth must be a legal date. Since the robbery happened last night, we assume any date from Jan 1, 1900 to Apr 2, 2011 (inclusive) is legal, and others are illegal. For identification number in first generation card, the first 2 digits of year are omitted, and the date is considered legal if one of the two interpretations (19xx or 20xx) is legal.
- Order code is the code used to disambiguate people with the same date of birth and address code. We consider any digits are legal.
- Checksum confirms the validity of the ID number from the first 17 digits in second generation identity card. It is calculated by:
- Mark the identification code right-to-left a1, a2, ... , a18. a1 is the checksum digit.
- Calculate coefficient for each digit: Wi = 2i - 1 mod 11. For simplicity, Wi is given in the following table:
| i |
18 |
17 |
16 |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
| Wi |
7 |
9 |
10 |
5 |
8 |
4 |
2 |
1 |
6 |
3 |
7 |
9 |
10 |
5 |
8 |
4 |
2 |
1 |
- Calculation of
- a1 = (12 - (S mod 11)) mod 11
- If a1 is between 0 and 9, the checksum code is a1 itself. If a1 is 10, the checksum code is "X" (upper case).
Now given an identification number either in 15-digit format or 18-digit format, you need to output a legal identification number by changing minimal number of digits in original one.
Input
There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.
Each test case consists of a line of identification number, in either 15-digit format or in 18-digit format. All characters are digits except the last character in an 18-digit-format code may be a capital 'X'. There will be no extra characters.
Output
For each test case, you need to output the correct identification number described above. If there are multiple solutions, any one is OK.
Sample Input
2
111111111111111111
111111111111111
Sample Output
111111191110111111
111111111111111
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4
5 using namespace std;
6
7 const int monthday[] =
8 {
9 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
10 };
11
12 const int wi[] =
13 {
14 7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2, 1
15 };
16
17 char id[ 100 ], ans[ 100 ], tmp[ 100 ];
18 int y, m, d, md, ck, tp; // 0 15 1 18
19
20 #define ISR ( (y%400==0) || ((y%100!=0)&&(y%4==0)) )
21
22 int changeNum() {
23 int i, res = 0;
24 for ( i = 0; id[ i ]; ++i ) {
25 if ( id[ i ] != tmp[ i ] ) {
26 ++res;
27 }
28 }
29 return res;
30 }
31
32 void toTmp() {
33 int off = 6, ty = y;
34 strcpy( tmp, id );
35 if ( tp == 1 ) {
36 off = 8;
37 tmp[ 6 ] = '0' + ( ty / 1000 );
38 ty %= 1000;
39 tmp[ 7 ] = '0' + ( ty / 100 );
40 }
41 ty %= 100;
42 tmp[ off++ ] = '0' + ( ty / 10 );
43 tmp[ off++ ] = '0' + ( ty % 10 );
44 tmp[ off++ ] = '0' + ( m / 10 );
45 tmp[ off++ ] = '0' + ( m % 10 );
46 tmp[ off++ ] = '0' + ( d / 10 );
47 tmp[ off++ ] = '0' + ( d % 10 );
48 if ( tp == 1 ) {
49 int s = 0, i;
50 for ( i = 0; i < 17; ++i ) {
51 s += (tmp[i]-'0') * wi[ i ];
52 }
53 ck = ( 12 - (s%11) ) % 11;
54 tmp[ 17 ] = ( ( ck < 10 ) ? (ck+'0') : 'X' );
55 }
56 }
57
58 int legal() {
59 if ( !( (y>=1900) && (m>=1) && (d>=1) ) ) {
60 return 0;
61 }
62 if ( y > 2011 ) {
63 return 0;
64 }
65 if ( (y==2011) && (m>4) ) {
66 return 0;
67 }
68 if ( (y==2011) && (m==4) && (d>2) ) {
69 return 0;
70 }
71 return 1;
72 }
73
74 void solve() {
75 int min = 10000, tn;
76 for ( y = 1900; y <= 2011; ++y ) {
77 for ( m = 1; m <= 12; ++m ) {
78 md = monthday[ m ];
79 if ( (m==2) && (ISR) ) {
80 ++md;
81 }
82 for ( d = 1; d <= md; ++d ) {
83 toTmp();
84 if ( legal() ) {
85 tn = changeNum();
86 if ( tn < min ) {
87 min = tn;
88 strcpy( ans, tmp );
89 }
90 }
91 }
92 }
93 }
94 }
95
96 int main() {
97 int td;
98 scanf( "%d", &td );
99 while ( td-- > 0 ) {
100 scanf( "%s", id );
101 if ( strlen( id ) == 15 ) {
102 tp = 0;
103 }
104 else {
105 tp = 1;
106 }
107 solve();
108 puts( ans );
109 }
110 return 0;
111 }
112
J
Judge Internal Error
Time Limit: 2 Seconds Memory Limit: 65536 KB
The online judge system developed by Zhejiang University ACM/ICPC team (that is the system used during this contest) is designed to be robust. It can execute all kinds of user-submitted programs, including unsafe or malicious ones, and remain working and stable. However, it does report mysterious "Judge Internal Error" ("JIE" in short), occasionally.
JIE happens due to various reasons, such as crashes of special judge programs, poor network conditions, incredible large test data, extremely high system load, failures of hard disks, bugs of online judge system, cosmic radiation and so on. In our experience, real world JIE often reflects one or more problematic problems. Every time JIE happens, the corresponding problem ID is written to a special system log. Given the system log, your task is to find out the ID of the most problematic problem.
Input
The first line contains an integer T (T ≈ 10), the number of test cases. The following are test cases, separated by one blank line.
For each test case, the first line contains an integer N (1 ≤ N ≤ 1000), the size of system log. Following N lines, each line contains an integer Pi (1001 ≤ Pi ≤ 9999), which is the problem ID causing JIE.
Output
For each test case, output one integer in one line, which is the ID of the most problematic problem (that is, this ID occurs the most frequently in the log). When multiple IDs occur with a same frequency, prefer the largest ID.
Sample Input
2
4
1001
1003
1003
1002
2
1001
1003
Sample Output
1003
1003
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4
5 using namespace std;
6
7 #define L 1009
8
9 int a[ L ], n, cnt[ L ];
10
11 int main() {
12 int td, i, j, max;
13 scanf( "%d", &td );
14 while ( td-- > 0 ) {
15 scanf( "%d", &n );
16 for ( i = 0; i < n; ++i ) {
17 scanf( "%d", a+i );
18 }
19 sort( a, a+n );
20 cnt[ 0 ] = 1;
21 i = 1;
22 for ( j = 1; j < n; ++j ) {
23 if ( a[ j ] == a[ j - 1 ] ) {
24 ++cnt[ i - 1 ];
25 }
26 else {
27 a[ i ] = a[ j ];
28 cnt[ i ] = 1;
29 ++i;
30 }
31 }
32 n = i;
33 i = 0;
34 for ( j = 1; j < n; ++j ) {
35 // if ( (cnt[j]>cnt[i]) || ((cnt[j]==cnt[i])&&(a[j]>a[i])) ) {
36 if ( cnt[ j ] >= cnt[ i ] ) {
37 i = j;
38 }
39 }
40 printf( "%d\n", a[ i ] );
41 }
42 return 0;
43 }
44