ICPC ECNA 2016 C - The Key to Cryptography

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
ICPC East Central NA Regional Contest 2016, Problem C

Suppose you need to encrypt a top secret message like SEND MORE MONKEYS. You could use a simple substitution cipher, where each letter in the alphabet is replaced with a different letter. However, these ciphers are easily broken by using the fact that certain letters of the alphabet (like E, S, and A) appear more frequently than others (like Q, Z, and X). A better encryption scheme would vary the substitutions used for each letter. One such system is the autokey cipher.

To encrypt a message, you first select a secret word – say ACM – and prepend it to the front of the message. This longer string is truncated to the length of the message and called the key, and the n^{th} letter of the key is used to encrypt the n^{th} letter of the original message. This encryption is done by treating each letter in the key as a cyclic shift value for the corresponding letter in the message, where A indicates a shift of 0, B a shift of 1, and so on. Using ACM as the secret word, we would encrypt our message as follows:

SENDMOREMONKEYS (message)
ACMSENDMOREMONK (key)
SGZVQBUQAFRWSLC (ciphertext)

Note that the letter E in the message was encrypted as G the first time it was encountered (since the corresponding letter in the key was C indicating a shift of 2), but then as Q and S the next two times.

Your task is simple: given a ciphertext and the secret word, you must determine the original message.

Input Specification

Input consists of two lines. The first contains the ciphertext and the second contains the secret word. Both lines contain only uppercase alphabetic letters.

Output Specification

Display the original message that generated the given ciphertext using the given secret word.

Sample Input

SGZVQBUQAFRWSLC
ACM

Sample Output

SENDMOREMONKEYS
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.