AIOC Banner

Problem: Zig-Zag Cipher

Want to try solving this problem? You can submit your code online if you log in or register.


Zig-Zag Cipher

Input File: zigin.txt
Output File: zigout.txt
Time Limit: 0.2 second

The latest development in cryptography, certain to be adopted by the military, governments and anyone else who is paranoid, is the zig-zag cipher.

To encrypt a message using the zig-zag cipher, the letters of the message are written on the page in a zig-zag pattern. This is illustrated below for the message "CARTOGRAPHY".

    C       O       P
      A   T   G   A   H
        R       R       Y

The letters are then read one row at a time, from the top row down to the bottom. In the diagram above, the first row spells "COP", the second spells "ATGAH" and the third spells "RRY". Finally these are combined to obtain the final encrypted message, which is "COPATGAHRRY".

The zig-zag cipher can be extended to use as many rows as you like. For instance, using a zig-zag cipher with six rows, the message "CHARLIETHEWONDERBUDGIE" is encrypted to become "CWIHEOGEAHNDRTDULEEBIR" as seen in the following diagram.

    C                   W                   I
      H               E   O               G   E
        A           H       N           D
          R       T           D       U
            L   E               E   B
              I                   R

Your task is to write a program that can decrypt messages written in the zig-zag cipher. Your program must read the number of rows used in the cipher as well as an encrypted message, and must output the original (decrypted) message.

Input

The first line of input will consist of a single integer r, the number of rows used in the zig-zag cipher (2 <= r <= 100).

Following this will be the encrypted message. The encrypted message will consist entirely of upper-case letters, with no spaces or punctuation. This message may be split across several lines in the input file; each line will contain between 1 and 70 letters inclusive. The entire encrypted message will be between 1 and 10,000 letters long.

Following the encrypted message will be a final line containing a single hash (#).

Output

Your output should consist of a single line containing the entire decrypted message (note that this line might be very long). The output line should contain no spaces or punctuation.

Sample Input 1

3
COPATGAHRRY
#

Sample Output 1

CARTOGRAPHY

Sample Input 2

6
CWIHEOGE
AHNDRTDU
LEEBIR
#

Sample Output 2

CHARLIETHEWONDERBUDGIE

Scoring

The score for each input file will be 100% if the correct decrypted message is written to the output file and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 15 November 2019,  5:32am AEDT