Array plaintext plaincode ciphercode ciphertext 0 'c' 3 3 'c' 1 'a' 1 19 's' 2 't' 20 27 '.' 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, given the key 5 and ciphertext 'cs.', your program must output the plaintext 'cat'.
The input file contains one or more test cases, followed by a line containing 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 message containing at least one and at most 70 characters. The key k will be a positive integer not greater than 300. For each test case, output the untwisted 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 algebra, this will be the case provided that the greatest common divisor of the 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
【全文翻译】
加密技术是把消息（明文）变换成一种伪装的形式（密文）进行秘密通信的一种方法，除收件人之外，任何人看了密文也不能翻译成明文。把明文变换成密文称为加密，把密文转换成明文称为解密。Twisting(扭曲)是一个简单的加密方法，它需要发送者和接受者都共同认可的加密关键字k，是一个正整数。
Twisting方法使用4个数组：plaintext和ciphertext是字符数组，plaincode和ciphercode是整数数组。所有数组的长度为n，这是对信息加密的长度。所有数组初始时为空，下标从0到n-1。消息只包含小写字母，句号和下划线（代表空格）。
消息存储在数组plaintext中。给定关键k，加密方法如下：首先把plaintext的字母转换成数字编码存放到数组plaincode中，转换规则：'_' = 0，'a' =1，'b' =2，……'z' = 26 ，'.' = 27。然后将存放在数组plaincode中的数字编码按下列公式转换成加密代码存放到数组ciphercode中：i从0到n-1，
ciphercode[i] = (plaincode[k×i mod n] - i) mod 28.
（这里mod是模运算，例如，3 mod 7 = 3，22 mod 8 = 6，-1 mod 28 = 27。C语言中使用’%’运算符，Pascal语言中使用’mod’运算符）。最后，把存放在ciphercode中的数字编码
按上述方法转换成密文存放到数组ciphertext中。
你的任务是编写程序，实现消息的untwist（解密），即给定关键字k，将密文恢复至原来的明文。例如，关键字是5，密文是'cs.'，程序必须输出明文'cat'。
输入文件包含一个或多个测试例，数字0表示输入结束。每个测试例一行：关键字k，空格，然后是密文，密文至少一个字符，最多70个字符。关键k是一个正整数，不超过300。对每个测试例，输出一行解密的明文。
注意：你可以假定解密消息的结果是唯一的。
【算法分析】
本题是属于加密和解密类型的题目，当然加密和解密的方法是比较简单的。题目中给出了加密的过程，要求我们给出解密的结果。分为以下三步：
(1) 根据原始密文，计算ciphercode
原始密文 a~z _ . ciphercode ASCII值-96，其结果表明为： 'a'→1, 'b'→2, ..., 'z'→26 0 27 (2) 根据ciphercode，计算plaincode
题目中给出了由plaincode计算ciphercode的公式：
ciphercode[i] = (plaincode[k* i mod n] - i) mod 28
现在求plaincode，令t=k*i % n (运算符*比%高一个优先级)，t是密文的坐标转换成明文的坐标，则：
plaincode[t] = (ciphercode[i] + i) % 28
(3) 根据plaincode,计算解密后的明文
plaincode 值为1~26时 0 27 以测试数据1为例：
密文坐标 密文 ciphercode 转换成明文的坐标t plaincode 明文 【程序代码】
程序名称：
题目： 提交语言： 运行时间： 运行内存：
zju1006.cpp Do the Untwist C++ 10ms 836K
0 c 3 0 3 c 1 s 19 2 20 t 2 . 27 1 1 a 解密后的明文 a~z：1→'a'，2→'b'，?，26→'z' _ . #include ZJU2109-FatMouse' Trade3 Time limit: 1 Seconds Memory limit: 32768K FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain. Input The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000. Output For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain. Sample Input 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1 Sample Output 13.333 31.500 Author: CHEN, Yue 【全文翻译】 FatMouse准备了M磅的猫粮，打算与看守仓库的猫交换食品，仓库里存放着它喜爱的食物JavaBean。 仓库有n个库房，库房i存放J[i]磅JavaBean，需要F[i]磅猫粮予以交换。FatMouse不需要交换库房里所有的JavaBean，可以按比例交换。如果它支付F[i]×a%磅的猫粮，就可以换取J[i]×a%磅的JavaBean，其中a是实数。 3 浙江省大学生程序设计竞赛，Sunny Cup 2004，http://acm.zju.edu.cn/show_problem.php?pid=2109 现在明确编程任务：FatMouse最多能换取多少JavaBean。 输入 输入包含多组测试例！ 对每个测试例，第一行是两个非负整数M和N。接下来N行，每行两个非负整数J[i]和F[i]。最后一个测试例是两个—1，不需要处理。所有的整数都不超过1000. 输出 对每个测试例，输出一行：是一个实数，精确到小数点后3位，表示FatMouse最多能换取的JavaBean数量。 输入样例 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1 输出样例 13.333 31.500 Author: CHEN, Yue 【题目分析】 FatMouse用M磅猫食与猫换取它喜爱的食物JavaBean。JavaBean存储在一个仓库的N个库房中，而且每个库房的JavaBean所需要的猫食代价是不一样的。以第一组数据为例，如下表所示： 库房号 存储的JavaBean 所需要的猫食代价 1 7 2 2 4 3 3 5 2 当FatMouse剩余的猫食不够换取整个库房的JavaBean时，可以按比例换取。题目要求猫能够换取尽可能多的JavaBean。 【算法分析】 本题采用贪心算法。 (1) 为了使猫能够换取尽可能多的猫食，就要计算出每个库房的性价比，并按降序排序。 定义数据结构： struct Fat { int bean; //存放该库房中JavaBean int food; //存放换取该库房中的JavaBean所需要的猫食代价 double good; //用猫食换取JavaBean时的性价比 }; 对第一组数据：