Problem Link
http://www.codechef.com/CDCK2015/problems/CENCODE
Author:
Pravakar Wang
Tester:
Ankur Goel
Editorialist:
Shuchita Garg
Difficulty:
Easy
Prerequisite
LCM ( Least comman multiple)
Problem :
A forward shifted alphabet code is a form of coding in which each letter has been shifted for a particular number. For example, if a message has been encrypted by shifting 2, then ‘C’ will be written in place of ‘A’ , ‘B’ in place of ‘Z’, ‘A’ in place of ‘Y’ and so on. Such integers are the keys to decode shifted alphabet codes.
Thaton likes sending encoded messages to Pravakar. So to decode those messages she gave him N alarm clocks, all set at 12 O’ clock with batteries removed, placed sequentially in a box. The alarm clocks rings every { x1,x2,x3,x4,…,xn } hours respectively. While sending the message, she tells Pravakar not to consider a continuous sequence of alarm clocks in the set from positions L to R i.e from XL to XR is not under consideration and ask him to insert the batteries in the rest of the alarm clocks (except alarm clocks from L to R) and informs him that the minimum number of hours after which all the clocks under consideration ring simultaneously is the key to her message. Help Pravakar!!
Note : Shifting of character occurs in a circular manner, i.e. if ‘y’ need to be shifted forward by 2,
Then y+2=‘a’ i.e in forward shifting, after z we starts with ‘a’ again, and in backward shifting , after ‘a’ we again starts with ‘z’ e.g back shift ‘c’ by 5 will be : ‘x’.
Explanation :
Let all the alphabets in the encoded message are shifted forward by integer Z.
So, To decode them we again need to shift them backward by Z.
Z=After the clocks in the range 1 to L and R+1 to N will Ring Together.
Z=LCM(x1… xL, xR+1…xN. )
Now shift all the characters backward by Z.