DMOPC '15 Contest 1 P3 - Itami and Cipher

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

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

Itami has just received an encoded message of length N (1 \le N \le 5\,000) from the army headquarters. As the army prefers simplicity, all their messages are encoded with the Caesar Cipher, and all encryption will be done with a right shift. Prior to departure, Itami had been given a secret document containing the different shifts that will be used for each day. Unfortunately, being an airhead, he has lost the document.

Fortunately, Itami knows that every decrypted message will always contain the army's motto. Given the encoded message S and the army's motto T, please help Itami figure out the minimum possible nonnegative right shift used in the encryption, as well as the decrypted message.

Input Specification

The only two lines of input will contain strings S and T respectively, both containing only lowercase letters. It is guaranteed that |T| \le N.

Output Specification

The first line of output should contain the shift used in the encryption (0 \le shift \le 25). It is guaranteed that at least one exists. If there are multiple possible shifts, output the smallest. The second line should contain the decrypted message, using the correct shift.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2


Sample Input 3


Sample Output 3