SPOJ: 400. To and Fro

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down

Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as


Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.

Problem: Sphere Online Judge (SPOJ) – Problem TOANDFRO

Solution: Let’s do this on a small example. The message should be ABCDEFGHIJKL with three columns. Therefore we get:

If we merge these lines together, we get:

You can see that you need the first character from the first element, the third from the second, the first from the third, etc. To make this a bit easier I decided to reverse every second element.

Now we can just take all the firsts characters from every element, then the second characters and finally the thirds and we’re done.

Write a Comment