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.
Input
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 (AZ) and spaces. Each diary entry consists of at most 1000 encrypted letters (including spaces).
Output
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.
Example
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
hide comments
sri:
20111011 18:36:04
its WA again and again??


Adrian Kuegel:
20110722 07:42:23
@anksanu: distance is defined as a directional distance, you can only go in one direction! Therefore, if d is a possible distance, then d+26, d+2*26, ... are also possible distances, but 26d usually is not a possible distance (only for d = 13). 

anksanu:
20110721 18:46:14
in the 3rd case the answer can also be 9 then why 17 is the answer


Pranay:
20110719 14:21:19
@Adrian: thanks a lot :) Last edit: 20110719 14:27:26 

Adrian Kuegel:
20110719 08:24:02
@Pranay: you print negative values as distance. 

Pranay:
20110718 12:47:58
why am i getting WA?? 

Filip Zymek:
20110711 09:18:22
well.. your answer helped me to undredstand how does SPOJ work (sicne I'm new to SPOJ). I guess you're right about mixing Scanner and BufferedReader. It was my first thought and it stayed like that :) need to think a little more about my solution 

Adrian Kuegel:
20110711 08:26:33
@Filip: I think it is a bad idea to mix Scanner and BufferedReader. Replace numOfTests = sc.nextInt() by numOfTests = Integer.parseInt(rd.readLine()), then it should work. Note that you can test it the same way as the judge does if you use java Main < input.txt (where input.txt does contain the test case). In this case you will see that your current solution even fails for the sample input. 

Filip Zymek:
20110709 20:46:46
hi all


Problem Solver:
20110707 15:37:02
Thanks sir, i thought distance between E and B is 3 not 23 :) 
Added by:  Adrian Kuegel 
Date:  20110705 
Time limit:  0.407s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  German Collegiate Programming Contest 2011 (Author: Tobias Werth) 