Wednesday, November 26, 2008

ACM ICPC Philippines 2008: Problem C

.
2nd Philippine National Inter-Collegiate Programming Competition
(ACM Philippines 2008)
22 November 2008, Cebu City

Problem C: “I came, I saw, I conquered!”
Input File: c.in

Introduction:

As early as the first century B.C., the Roman general Gaius Julius Caesar (100 B.C. – 44 B.C.) used a cipher shift to make the contents of certain messages understandable only for those he intended the message to reach. To describe this early form of cryptosystem – often termed the Caesar cipher – we shall make certain conventions to simplify the presentation. First, we shall write the original message, the plaintext, using only lower case letters, with no punctuation or spaces. Then to encrypt the plaintext, each lowercase letter, from a to w, is shifted to the letter three places forward in the alphabet, and the last three letters – namely x, y and z, are shifted to the first three letters, respectively. We use the uppercase letters for the resulting cyphertext. Consequently, a is encrypted as D, b as E, c as F ….. j as M….. m as P, y as B and z as C. In this example, the key (or cipher shift) equals 3.

If Caesar wanted to inform a senator in Rome of a recent victory, he might have sent the message “I came, I saw, I conquered!” Encryption of this message takes place as follows:

Message: I came, I saw, I conquered!
Plaintext: icameisawiconquered
Ciphertext: LFDPHLVDZLFRQTXHUHG

Upon receiving the ciphertext, as long as this senator knows the size and direction of the shift, he can reverse the process. Decryption then results by replacing each uppercase letter, from D to Z, in the ciphertext by the lowercase letter three places back in the alphabet, and A by x, B by y and C by z. After decrypting, one then inserts the appropriate spaces and punctuations in the plaintext. (Note that by removing spaces in the plaintext, the resulting absence of spaces in the ciphertext helps make the message more unintelligible. If one does not know the size and direction of the shift for decryption, the presence of spaces may suggest certain information about the structure of the original message.)

Task:

Given the key (or cipher shift) and the message written in separate lines in the input file, write a computer program to encrypt the message using the Caesar cipher as described above.

The key (an integer) shall range from the number 0 to 25. The message can contain an array (or string) of alphanumeric and special characters of minimum length 1 and maximum length 50 chararacters. If the message does not contain a letter, or the message length is not within the required range the program should output the phrase ‘Message not valid’.

Sample Input

3
I came, I saw, I conquered!
2
I came, I saw, I conquered!
5
*14344&

Sample Output

Case 1: LFDPHLVDZLFRQTXHUHG
Case 2: KECOGKUCYKEQPSWGTGF
Case 3: Message not valid

-----------------------------------------------------------

Problem Category: Easy

Number of teams which solved the problem: 24 (out 39)

Success rate: 80 %

For more information, contact: computingsoc@gmail.com

.

No comments: