poj 2026 Cipher

Cipher

Description

Bob and Alice started to use a brand-new encoding scheme. Surprisingly it is not a Public Key Cryptosystem, but their encoding and decoding is based on secret keys. They chose the secret key at their last meeting in Philadelphia on February 16th, 1996. They chose as a secret key a sequence of n distinct integers, a1 ; . . .; an, greater than zero and less or equal to n. The encoding is based on the following principle. The message is written down below the key, so that characters in the message and numbers in the key are correspondingly aligned. Character in the message at the position i is written in the encoded message at the position ai, where ai is the corresponding number in the key. And then the encoded message is encoded in the same way. This process is repeated k times. After kth encoding they exchange their message.

The length of the message is always less or equal than n. If the message is shorter than n, then spaces are added to the end of the message to get the message with the length n.

Help Alice and Bob and write program which reads the key and then a sequence of pairs consisting of k and message to be encoded k times and produces a list of encoded messages.

Input

The input file consists of several blocks. Each block has a number 0 < n <= 200 in the first line. The next line contains a sequence of n numbers pairwise distinct and each greater than zero and less or equal than n. Next lines contain integer number k and one message of ascii characters separated by one space. The lines are ended with eol, this eol does not belong to the message. The block ends with the separate line with the number 0. After the last block there is in separate line the number 0.

Output

Output is divided into blocks corresponding to the input blocks. Each block contains the encoded input messages in the same order as in input file. Each encoded message in the output file has the lenght n. After each block there is one empty line.

Sample Input

10
4 5 3 7 2 8 1 6 10 9
1 Hello Bob
1995 CERC
0
0

Sample Output

BolHeol  b
C RCE

密码

描述

      鲍勃和爱丽丝开始使用一种全新的编码方案。令人惊讶的是，它不是公钥密码系统，但它们的编码和解码是基于密钥的。他们在1996年2月16日在费城的最后一次会议上选择了密钥。他们选择了一个由n个不同整数组成的序列a1作为密钥;。;该编码基于以下原则。信息写在键的下面，这样信息中的字符和键中的数字就相应对齐了。消息中位于i位置的字符被写入编码消息中位于ai位置的字符，其中ai是密钥中对应的数字。然后用同样的方式对编码后的信息进行编码。这个过程重复k次。在第k次编码之后，他们交换了他们的消息。

        消息的长度总是小于等于n。如果消息长度小于n，则在消息末尾添加空格，得到长度为n的消息。

        帮助Alice和Bob，编写程序，读取密钥，然后是一个由k和要编码的消息组成的对序列，并生成一个编码消息列表。

输入

输入文件由几个块组成。每个块在第一行有一个数字0 < n <= 200。下一行包含一个由n个数字组成的序列，每个数字对不同，且每个数字大于零且小于或等于n。下一行包含整数k和一条由一个空格分隔的ascii字符信息。行以eol结束，此eol不属于该消息。该块以数字0的单独行结束。在最后一个块之后的另一行是数字0。

输出

输出被分成与输入块相对应的块。每个块以与输入文件相同的顺序包含编码后的输入消息。输出文件中的每条编码消息的长度都是n。每个块之后都有一个空行。

Sample Input

10
4 5 3 7 2 8 1 6 10 9
1 Hello Bob
1995 CERC
0
0

Sample Output

BolHeol  b
C RCE

题目大意：给出一个编码的顺序，每经过一次编码第i位上的字符回到第a[i]位上。然后给出一个k，和初始的串，问编码k次后的串是什么。

k可能会很大，不能暴力，所以要用置换群，找出轮换的环，假设环中有m个数，那么每编码m次，就代表这又回到了初始状态，可以用k%m，这样减少编码的次数。如果在记录轮换的位置，那么对于轮换中的第i个字符编码k次，就变成了轮换中的第(i+k)%m个字符。这样直接可以计算出最终的结果。

注意，题目不难，但是输入让人头疼，，，，经过多次wa，测试出只有(getline除外)：

gets(str) ;

int len = strlen(str) ;

for(i = len ; i <= n ; i++)

str[i] = ' ' ;

而且一定要有后面的for，不然就错误.

代码：

#include 
#include 
#include 
#include 
using namespace std ;
char str[210] , s[210] , ch ;
int cnt ;
int a[210] , vis[210] ;
vector  vec[210] ;
int vec_num ;
void grop(int n) {
    int i , j ;
    vec_num = 0 ;
    memset(vis,0,sizeof(vis)) ;
    for(i = 1 ; i <= n ; i++) {
        if( vis[ a[i] ] ) continue ;
        j = i ;
        while( !vis[ a[j] ] ) {
            vis[ a[j] ] = 1 ;
            vec[ vec_num ].push_back( j ) ;
            j = a[j] ;
        }
        vec_num++ ;
    }
}
int main() {
    int n , m , k , i , j , l , num , mod , temp ;
    while( scanf("%d", &n) && n ) {
        for(i = 1 ; i <= n ; i++) {
            scanf("%d", &a[i]) ;
        }
        for(i = 0 ; i < n ; i++) vec[i].clear() ;
        grop(n) ;
        while( scanf("%d", &k) && k ) {
            cnt = 0 ;
            memset(s,0,sizeof(s)) ;
            memset(str,0,sizeof(str)) ;
            gets(str) ;
            int len = strlen(str) ;
            for(i = len ; i <= n ; i++)
                str[i] = ' ' ;
            for(i = 0 ; i < vec_num ; i++) {
                num = vec[i].size() ;
                for(j = 0 ; j < num ; j++) {
                    l = (j+k)%num ;
                    s[ vec[i][l] ] = str[ vec[i][j] ] ;
                }
            }
            for(i = 1 ; i <= n ; i++) {
                printf("%c", s[i]) ;
            }
            printf("\n") ;
        }
        printf("\n") ;
    }
    return 0 ;
}