ECOO Practice 2014

Problem 2: Word Wrap Cypher

In text display, word wrap is the feature of moving text to a new line when the current line is full, so that all text is visible without having to scroll horizontally. This makes it so that newlines do not have to be hardcoded in a piece of text, and that the text can be dynamically reflowed when the text editor is resized. When a word (more specifically, a consecutive series of characters that does not contain a space) is too long to fit on the current line, the entire word is displayed on the next line, where the rest text continues. The space that comes before the wrapped word is always on the line above it, meaning that no wrapped line can have a space as the first character. The following diagram illustrates word wrap on a piece of text.

Word Wrap Cypher is a way of encoding a message based on word wrapping a text and right-aligning it. We are given a width W (1 ≤ W ≤ 100), along with a single-line message of no more than 1000 ASCII characters. To encode the message using Word Wrap Cypher, we follow these instructions:

  1. Word wrap the line of text to a width of W characters.
  2. Fill the end of each line with spaces until it is W characters wide (not including the newline character).
  3. Right align the piece of text, trimming off all trailing spaces and padding each line with leading spaces so that their widths remain W characters long.
  4. Interpret the resulting right-aligned text column by column into a single-lined string. That is, first take the character at row 1 column 1, then at row 2 column 1, etc. After reaching the end of column 1, we take the character at row 1 column 2, then at row 2 column 2, and so on.

It is guaranteed that you will not be dealing with original messages that contain words longer than W characters (and thus cannot be wrapped). Nor will you have to deal with messages that contain 2 or more consecutive spaces. Let's say we want to encode the following message for W = 15.

Every man must die, Jon Snow. But first he must live.

For the purposes of this explanation only, we will use underscores to represent spaces. The text wraps like this:


Right aligning the above, we get:


Interpreting the text column by column yields the following encoded string:


Given an encoded string, your task is to determine the original message.


The input will contain 5 test cases with 2 lines per test case. The first of these lines contains a single integer W, and the second of these lines contains the resulting encoded string. In the sample input below, spaces are replaced by underscore '_' characters for readability. The actual test input will use spaces, not underscores!


For each test case, output a line containing the original, decoded message.

Sample Input


Sample Output

Every man must die, Jon Snow. But first he must live.
Syrio: Do you pray to the gods?
Arya: The old and the new.
Syrio: There is only one god, and his name is death.
Syrio: And there is only one thing we say to death... Not today.

All Submissions
Best Solutions

Point Value: 7
Time Limit: 5.00s
Memory Limit: 16M
Added: Jun 29, 2014
Author: Alex

Languages Allowed:

Comments (Search)

It's quiet in here...