24h購物| | PChome| 登入
2011-06-15 07:32:57| 人氣885| 回應0 | 上一篇 | 下一篇

c109. Cipher

推薦 0 收藏 0 轉貼0 訂閱站台

http://zerojudge.tw/ShowProblem?problemid=c109

內容 :

Bob和Alice開始使用一種全新的編碼策 略。令人訝異的他們並未採用公開金鑰密碼系統(Public Key Cryptosystem),而是採用秘密鍵(secret keys)的方式來編碼及解碼。在1996年2月16日在費城他們上次見面的時候,他們選定了他們的秘密鍵。這些秘密鍵是由1到n的整數所構成,但是排列 的順序卻是他們任意挑選的。在編碼的時候採用以下的原則:

把要編碼的訊息(明文)寫在秘密鍵下面,每個字元與秘密鍵的一數字對齊。位於位置i的字元經編碼後其位置為 ai,ai為秘密鍵中第i個位置的值。明文中的每個字元編碼後就得到密文了。這密文還可以用同樣的策略再加密,經過了k次加密後他們交換他們的密文。

明文的長度一定小於等於n。如果明文的長度小於n,就在其後方加上空白字元使得其長度剛好為n。你的任務是幫助Bob和Alice寫一個程式讀入秘密鍵,以及k,以及一連串要加密的明文,然後輸出密文。

輸入說明 :

輸入含有多組測試資料,每組測試資料的第一列 有一個整數n(0 < n <= 200),代表秘密鍵的長度。接下來的一列為秘密鍵,含有n個整數,內容為1到n的某種排列。再接下來的每列為k與明文,其中以一空白字元分隔。請注意: 每列以換列符號(End of Line)當作結束,但是換列符號不列入明文。當遇到k=0的一列時代表此組測試資料結束。另外,k可能相當大(但是不會超出C語言中int的範圍),所 以請注意你程式的演算法,否則可能導致Time Limit Exceeded.

當遇到n=0時代表整個輸入結束。請參考Sample Input。

輸出說明 :

對每一組測試資料中的每列明文,輸出加密後的密文(長度一定為n)。每組測試資料後請空一列。請參考Sample Output。

範例輸入 :

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

範例輸出 :

BolHeol  b
lelBo Hob 
C RCE     

Helol

提示 :

* Luck 貓翻譯

出處 :

ACM 306



作法 : 找循環

/**********************************************************************************/
/*  Problem: c109 "Cipher" from ACM 306                                           */
/*  Language: C                                                                   */
/*  Result: AC (68ms, 250KB) on ZeroJudge                                         */
/*  Author: morris1028 at 2011-06-13 21:41:02                                     */
/**********************************************************************************/


#include<stdio.h>
#include<string.h>
main() {
    int n, k, a, b, c, A[201], Cycle[201];
    char s[201], Ans[201];
    while(scanf("%d", &n) == 1 && n) {        
        for(a = 1; a <= n; a++)
            scanf("%d", &A[a]);
        while(scanf("%d", &k) == 1 && k) {

            getchar(), gets(s);
            
            int L = strlen(s), cnt, t, pos;
           
            for(a = L; a < n; a++) s[a] = ' ';
           
            for(a = 1; a <= n; a++) {
                t = A[a];
                cnt = 1;
                while(a != t) {
                    cnt++, t = A[t];
                }
                Cycle[a] = cnt;
            }
            for(a = 1; a <= n; a++) {
                pos = a;
                for(b = 0, c = k%Cycle[a]; b < c; b++)
                    pos = A[pos];
                Ans[pos-1] = s[a-1];
            }
            Ans[n] = '\0';
            puts(Ans);
        }
        puts("");
    }
    return 0;
}

台長: Morris
人氣(885) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:c112. Optimal Array Multiplication Sequence
此分類上一篇:c083. Roman Roulette

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文