Saturday, June 16, 2007

Final Indonesia National Contest 2007 :: Problem D - Email from The Professor

ACM/ICPC Indonesia National Contest 2007

Problem D

Email from The Professor

Time Limit: 1s

Being a judge in a programming contest like ACM/ICPC INC sometimes means trouble. They have to prepare challenging and interesting problems, and most importantly, they should keep the problems secret before the contest day. Usually, the judges use email as a main device to communicate and discuss on problems. As you might think, this is not a secure way to communicate confidentially since emails can be unintentionally sent to unexpected recipients, e.g. his/her student or worst, the contestant.

Considering those issues, Prof. Nash V. Ruhdney, one of the judges, has proposed a method to communicate confidentially amongst judges. Supposed there is a message of length n, write the message in a rectangle of width k, row by row, and read it column by column in a permuted order. The order of columns will then be the encryption key for the message. For example,
Message     : I am Prof. Nash V. Ruhdney
Key         : 3 7 4 1 2 6 5
Plain Text  : I   a m   P r
              o f .   N a s
              h   V .   R u
              h d n e y * *     note: '*' means blank and is not part of the message.
Column      : 11112222333344445556667777
Cipher Text : m .e N yIohha.VnrsuPaR f d
Prof. Nash then send this encrypted message (cipher text) through email, while the encryption key is sent through other means, such as phone or SMS. This way he can reduce the risk of erroneously sent email.

Of course there is no way that the professor would use paper & pencil to encrypt those messages. So, would you be kind to help him while he is preparing a nice problem for you?


Input consists of several test cases. The first line of each test case contains a message of length n (1 <= n <= 1,000) in a line (the message consists of ASCII characters). The next line contains k, (1 <= k <= 1,000) the width of rectangle, followed by k integer(s) separated by a single space, the permutation of 1 to k which represents the encryption key.


For each message, output the encrypted message in a single line.

Sample Input

I am Prof. Nash V. Ruhdney
7 3 7 4 1 2 6 5
give no easy problem this year.
5 1 4 3 2 5

Sample Output

m .e N yIohha.VnrsuPaR f d
gnso  .eepeiav  lheioybty armsr

Problem Setter: Suhendry Effendy

Pembahasan Problem D - Email from the Professor

Diberikan string plaintext, dan sebuah key untuk meng-enkripsi-nya. Cara meng-enkripsi plaintext tersebut adalah dengan me-wrap around plaintext dengan width K (sehingga tercipta K columns of characters dan R baris). Lalu pengkodeannya adalah dengan membaca column (a1,a2,a3..aK) dari baris paling atas ke paling bawah dimana a1..aK adalah permutasi dari 0..K-1.

Soal ini hanya men-simulasikan apa yang ada di soal, jadi pintar-pintarnya kalian membuat program tanpa bug. Algoritmanya simple, anda cukup melakukan inverse dari key yang diberikan, lalu tinggal anda print per kolom dari baris pertama sampai terakhir, tetapi hati-hati dengan baris terakhir, bisa jadi sudah melebihi panjang string inputnya. Untuk lebih jelasnya lihat source code dibawah.

#include <stdio.h>
#include <string.h>

int idx[1000], inv[1000];
char s[1001];

int main(){
    while (gets(s)){
        int i,j,k,row,len=strlen(s);

        for (i=0; i<k; i++)
        scanf("\n");                             // baca ending new line

        for (i=0; i<k; i++)
            inv[idx[i]-1] = i;                   // inverse idx, tampung di inv

        row = (len+k-1)/k;                       // berapa baris yang tercipta, dibulatkan keatas

        for (i=0; i<k; i++)                      // looping pertama, untuk setiap kolum dari 0..k-1
            for (j=0; j<row; j++){               // looping kedua, print dari baris atas sampai bawah
                if (inv[i]<len)                  // hati hati, cek apakah index sekarang melebihi input?
                inv[i] += k;                     // lanjutkan ke baris berikutnya

Kembali ke halaman utama

No comments:

Post a Comment