新手菜菜 2008-9-9 15:50
小妹求教几道ACM的题目。。。紧求助
题目来源：acm.tju.edu.cn
toj题库。题号：3059，2628，2502，1132，3016
1）
Rock, Paper, Scissors is a two player game, where each player simultaneously chooses one of the three items after counting to three. The game typically lasts a pre-determined number of rounds. The player who wins the most rounds wins the game. Given the number of rounds the players will compete, it is your job to determine which player wins after those rounds have been played.
The rules for what item wins are as follows:
• Rock always beats Scissors (Rock crushes Scissors)
• Scissors always beat Paper (Scissors cut Paper)
• Paper always beats Rock (Paper covers Rock)
Input Format: (c1.in)
The first value in the input file will be an integer t (0 < t < 1000) representing the number of test cases in the input file. Following this, on a case by case basis, will be an integer n (0 < n < 100) specifying the number of rounds of Rock, Paper, Scissors played. Next will be n lines, each with either a capital R, P, or S, followed by a space, followed by a capital R, P, or S, followed by a newline. The first letter is Player 1's choice; the second letter is Player 2's choice.
Output Format: (c1.out)
For each test case, report the name of the player (Player 1 or Player 2) that wins the game, followed by a newline. If the game ends up in a tie, print TIE.
Sample Input:
3
2
R P
S R
3
P P
R S
S R
1
P R
Sample Output:
Player 2
TIE
Player 1
2）
Given a string s of length n, a subsequence of it, is defined as another string s' = su1 + su2 ... sum where 1 ≤ u1 < u2 < ... < um ≤ n and si is the ith character of s. Your task is to write a program that, given two strings s1 and s2, checks whether either s2 or its reverse is a subsequence of s1 or not.
Input Format: (c2.in)
The first line of input contains an integer T, which is the number of test cases. Each of the next T lines contains two non-empty strings s1 and s2 (with length at most 100) consisted of only alpha-numeric characters and separated from each other by a single space.
Output Format: (c2.out)
For each test case, your program must output “YES”, in a single line, if either s2 or its reverse is a subsequence of s1. Otherwise your program should write “NO”.
Sample Input:
5
arash aah
arash hsr
kick kkc
A a
a12340b b31
Sample Output:
YES
YES
NO
NO
YES
3）
For a positive integer N, the digit-sum of N is defined as the sum of N itself and its digits. When M is the digitsum of N, we call N a generator of M.
For example, the digit-sum of 245 is 256 (= 245 + 2 + 4 + 5). Therefore, 245 is a generator of 256.
Not surprisingly, some numbers do not have any generators and some numbers have more than one generator. For example, the generators of 216 are 198 and 207.
You are to write a program to find the smallest generator of the given integer.
Input Format: (c3.in)
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case takes one line containing an integer N, 1 ≤ N ≤ 100,000.
Output Format: (c3.out)
Your program is to write to standard output. Print exactly one line for each test case. The line is to contain a generator of N for each test case. If N has multiple generators, print the smallest. If N does not have any generators, print 0.
The following shows sample input and output for three test cases.
Sample Input:
3
216
121
2005
Sample Output:
198
0
1979
4）
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input Format: (c4.in)
The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output Format: (c4.out)
For each test case, print one line saying "To get from xx to yy takes n knight moves.".
Sample Input:
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output:
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
5）
Bruce Force has had an interesting idea how to encode strings. The following is the description of how the encoding is done:
Let x1,x2,...,xn be the sequence of characters of the string to be encoded.
1. Choose an integer m and n pairwise distinct numbers p1,p2,...,pn from the set {1, 2, ..., n} (a permutation of the numbers 1 to n).
2. Repeat the following step m times.
3. For 1 ≤ i ≤ n set yi to xpi, and then for 1 ≤ i ≤ n replace xi by yi.
For example, when we want to encode the string "hello", and we choose the value m = 3 and the permutation 2, 3, 1, 5, 4, the data would be encoded in 3 steps: "hello" -> "elhol" -> "lhelo" -> "helol".
Bruce gives you the encoded strings, and the numbers m and p1, ..., pn used to encode these strings. He claims that because he used huge numbers m for encoding, you will need a lot of time to decode the strings. Can you disprove this claim by quickly decoding the strings?
Input Format: (c5.in)
The input contains several test cases. Each test case starts with a line containing two numbers n and m (1 ≤ n ≤ 80, 1 ≤ m ≤ 109). The following line consists of n pairwise different numbers p1,...,pn (1 ≤ pi ≤ n). The third line of each test case consists of exactly n characters, and represent the encoded string. The last test case is followed by a line containing two zeros.
Output Format: (c5.out)
For each test case, print one line with the decoded string.
Sample Input:
5 3
2 3 1 5 4
helol
16 804289384
13 10 2 7 8 1 16 12 15 6 5 14 3 4 11 9
scssoet tcaede n
8 12
5 3 4 2 1 8 6 7
encoded?
0 0
Sample Output:
hello
second test case
encoded?
以上是5道题目。谢谢各位大侠帮忙