Cryptcowgraphy
Time limit1sMemory limit1024 MB
Given a message encrypted by inserting C, O, and W markers and swapping the segments between them, decide whether it decodes to the target sentence and count the encryptions.
- Level
Medium7 of 10
- Topics
- Simulation, String, Recursion
- Solved
- No attempts yet
Problem
The cows of Farmer Brown and Farmer John are planning a coordinated escape from their respective farms. They devised an encryption method to protect their written messages.
Suppose a cow has a message, such as "International Olympiad in Informatics". The cow inserts the letters C, O, and W at random positions in the message, so that C comes before O, and O comes before W. Then the cow swaps the part between C and O with the part between O and W. Examples:
"International Olympiad in Informatics"
->
"CnOIWternational Olympiad in Informatics"
"International Olympiad in Informatics"
->
"International Cin InformaticsOOlympiad W"
The cows can apply the encryption several times. Each time, they encrypt the string produced by the previous encryption.
One night, the cows of Farmer John receive a message that has been encrypted several times. Compute whether the original, unencrypted message could have been this string:
"Begin the Escape execution at the Break of Dawn".
Input
A single line containing both uppercase and lowercase letters, with fewer than 100 characters, representing the encrypted message.
Output
Print two integers on a single line. The first integer is 1 if the message decodes to an escape message, and 0 otherwise. The second integer is the number of encryptions that were applied.