Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1006P-DoTheUntwist-ZJU
发信站: 哈工大紫丁香 (2002年10月11日11:41:59 星期五), 站内信件

Do the Untwist
----------------------------------------------------------------------------
----
Time limit: 1 Seconds   Memory limit: 32768K
Total Submit: 366   Accepted Submit: 144
----------------------------------------------------------------------------
----
Cryptography deals with methods of secret communication that transform a mes
sage (the plaintext) into a disguised form (the ciphertext) so that no one s
eeing the ciphertext will be able to figure out the plaintext except the int
ended recipient. Transforming the plaintext to the ciphertext is encryption;
 transforming the ciphertext to the plaintext is decryption. Twisting is a s
imple encryption method that requires that the sender and recipient both agr
ee on a secret key k, which is a positive integer.
The twisting method uses four arrays: plaintext and ciphertext are arrays of
 characters, and plaincode and ciphercode are arrays of integers. All arrays
 are of length n, where n is the length of the message to be encrypted. Arra
ys are origin zero, so the elements are numbered from 0 to n - 1. For this p
roblem all messages will contain only lowercase letters, the period, and the
 underscore (representing a space).
The message to be encrypted is stored in plaintext. Given a key k, the encry
ption method works as follows. First convert the letters in plaintext to int
eger codes in plaincode according to the following rule: '_' = 0, 'a' = 1, '
b' = 2, ..., 'z' = 26, and '.' = 27. Next, convert each code in plaincode to
 an encrypted code in ciphercode according to the following formula: for all
 i from 0 to n - 1,
ciphercode[i] = (plaincode[ki mod n] - i) mod 28.
(Here x mod y is the positive remainder when x is divided by y. For example,
 3 mod 7 = 3, 22 mod 8 = 6, and -1 mod 28 = 27. You can use the C '%' operat
or or Pascal 'mod' operator to compute this as long as you add y if the resu
lt is negative.) Finally, convert the codes in ciphercode back to letters in
 ciphertext according to the rule listed above. The final twisted message is
 in ciphertext. Twisting the message cat using the key 5 yields the followin
g:
Array 0 1 2
plaintext 'c' 'a' 't'
plaincode 3 1 20
ciphercode 3 19 27
ciphertext 'c' 's' '.'
Your task is to write a program that can untwist messages, i.e., convert the
 ciphertext back to the original plaintext given the key k. For example, giv
en the key 5 and ciphertext 'cs.', your program must output the plaintext 'c
at'.
The input file contains one or more test cases, followed by a line containin
g only the number 0 that signals the end of the file. Each test case is on a
 line by itself and consists of the key k, a space, and then a twisted messa
ge containing at least one and at most 70 characters. The key k will be a po
sitive integer not greater than 300. For each test case, output the untwiste
d message on a line by itself.
Note: you can assume that untwisting a message always yields a unique result
. (For those of you with some knowledge of basic number theory or abstract a
lgebra, this will be the case provided that the greatest common divisor of t
he key k and length n is 1, which it will be for all test cases.)
Example input:
5 cs.
101 thqqxw.lui.qswer
3 b_ylxmhzjsys.virpbkr
0
Example output:
cat
this_is_a_secret
beware._dogs_barking

--
５、在快餐店送汉堡包并不是作践自己，你的祖父母对此

有另外的理解：机会。

                                    ——比尔·盖茨

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.235]