GCPC11F - Diary
Nowadays, people who want to communicate in a secure way use asymmetric encryption algorithms such as RSA. However, my older brother uses another, simpler encryption method for his diary entries. He uses a substitution cipher where each letter in the plaintext is substituted by another letter from the alphabet. The distance between the plaintext letter and the encrypted letter is fixed. If we would define this fixed distance d to 5, A would be replaced by F, B by G, C by H ... Y by D, Z by E.
With a fixed and known distance d the decryption would be somewhat simple. But my brother uses random distances for each of his diary entries. To decrypt his diary I have to guess the distance d for each entry. Thus, I use the well known phenomenon that the letter E is used more often in English words than other letters. Can you write a program for me that calculates the distance d based on the fact that the most used letter in the encrypted text corresponds to the letter E in plaintext? Of course, I am interested in the decrypted text, too.
The input consists of several test cases c that follow (1 ≤ c ≤ 100). Each test case is given in exactly one line containing one diary entry. Diary entries only use upper case letters (A-Z) and spaces. Each diary entry consists of at most 1000 encrypted letters (including spaces).
For each test case, print one line containing the smallest possible distance d (0 ≤ d ≤ 25) and the decrypted text. If the decryption is not possible because there are multiple distances conforming to the rules above, print NOT POSSIBLE instead. Spaces are not encrypted.
Input: 4 RD TQIJW GWTYMJWX INFWD JSYWNJX ZXJ F XNRUQJ JSHWDUYNTS YJHMSNVZJ THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG XVIDRE TFCCVXZRKV GIFXIRDDZEX TFEKVJK UVTIPGKZFE XVIDRE TFCCVXZRKV GIFXIRDDZEX TFEKVJK Output: 5 MY OLDER BROTHERS DIARY ENTRIES USE A SIMPLE ENCRYPTION TECHNIQUE 10 JXU GKYSA RHEMD VEN ZKCFI ELUH JXU BQPO TEW 17 GERMAN COLLEGIATE PROGRAMMING CONTEST DECRYPTION NOT POSSIBLE
@adrian i realised that mistake later but it is still gibing me WA
My code produce right answers, is there special test case with d>21?
@gaurav: why do you think that abs(d) should work? if you get a negative value, you should add 26 instead (you need the same result modulo 26).
Well, as hbm said, in fact you want the distance to be between 0 and 25; forget about smallest. If the answer is not "NOT POSSIBLE", there is exactly one distance value between 0 and 25 that will work.
what is the use of the statement of smallest possible distance here....
The trick for me was ignoring the phrase, "smallest possible distance". Because really, two letters cannot be more than 13 apart, right? The key is the definition, 0<=d<=25.
is there any hidden trick or what...why do i keep gettin WA..:(
|Added by:||Adrian Kuegel|
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM64|
|Resource:||German Collegiate Programming Contest 2011 (Author: Tobias Werth)|