joj1019

joj1019

• Authors
• Contests
•  
• Problems
•  
• Status
•  
• Links

[新版judge已支持special judge；增加了提交后的状态页面；增加对提交代码的语言检查] [新版judge系统近日试运行，希望可以解决内存越界导致Waiting的问题]  [more] [You've not  logged in.]

 1019: Do the Untwist

---

Result	TIME Limit	MEMORY Limit	Run Times	AC Times	JUDGE
	3s	8192K	1057	596	Standard

Cryptography deals with methods of secret communication that transform a message (theplaintext) into a disguised form (the ciphertext) so that no one seeing the ciphertext will be able to figure out the plaintext except the intended recipient. Transforming the plaintext to the ciphertext is encryption; transforming the ciphertext to the plaintext is decryption. Twistingis a simple encryption method that requires that the sender and recipient both agree on a secret key k, which is a positive integer.

The twisting method uses four arrays: plaintext and ciphertext are arrays of characters, andplaincode and ciphercode are arrays of integers. All arrays are of length n, where n is the length of the message to be encrypted. Arrays are origin zero, so the elements are numbered from 0 to n - 1. For this problem 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 encryption method works as follows. First convert the letters in plaintext to integer codes in plaincode according to the following rule: '_' = 0, 'a' = 1, 'b' = 2, ..., 'z' = 26, and '.' = 27. Next, convert each code inplaincode 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 '%' operator or Pascal 'mod' operator to compute this as long as you add y if the result is negative.) Finally, convert the codes inciphercode 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 following:

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, <, 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 keyk 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.)

Sample Input

5 cs.
101 thqqxw.lui.qswer
3 b_ylxmhzjsys.virpbkr
0

Sample Output

cat
this_is_a_secret
beware._dogs_barking

---

Submit / Problem List / Status / Discuss

Problem Set with Online Judge System Version 3.12
Jilin University

Developed by skywind, SIYEE

这个题目叙述很繁杂，同时也让我比较蛋疼。前几次提交

都没有给我通过原因是在算plaincode的时候忘记了cipheercode+i会是28的好几倍的问题。
这个题还需要注意的是（n-i)%28=m,则(m+i)%28=n;



#include<cstdio>
using namespace std;
char plaintext[80];
int plaincode[80];
int ciphercode[80];
char ciphertext[80];
void decryption(int n,int k)
{
for(int i=0;i<n;i++)
{
plaincode[(k*i)%n]=(ciphercode[i]+i)%28;
}
}
void out(int n)
{
for(int i=0;i<n;i++)
{
if(plaincode[i]==0)printf("_");
else if(plaincode[i]==27)printf(".");
else
{
printf("%c",plaincode[i]+'a'-1);
}
}
printf("n");
}
int main()
{
//freopen(&#","r",stdin);
int key;
int i;
while(scanf("%d",&key),key)
{
getchar();
gets(ciphertext);
for(i=0;ciphertext[i]!='';i++)
{
if(ciphertext[i]=='_')ciphercode[i]=0;
else if(ciphertext[i]=='.')ciphercode[i]=27;
else ciphercode[i]=ciphertext[i]-'a'+1;
}
decryption(i,key);
out(i);
}
return 0;
}