COCI '07 Contest 3 #3 Tajna

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 32M

Problem type

Every evening, little Ivica sends secret messages to little Marica through e-mail. Knowing Ivica's e-letter travels unguarded through the network on its way to Marica's e-mailbox, they have decided to encrypt every message using the following algorithm:

  • Suppose Ivica's message consists of N characters.
  • Ivica must first find a matrix consisting of R rows and C columns such that R \le C and R \times C = N. If there is more than one such matrix, Ivica chooses the one with the most rows.
  • Ivica writes his message into the matrix in row-major order. In other words, he writes the first segment of the message into the first row, the second segment into the second row and so on.
  • The message he sends to Marica is the matrix read in column-major order.

Marica has grown tired of spending her precious time deciphering Ivica's messages, so you must write a program to do it for her.

Input Specification

The input contains the received message, a string of lowercase letters of the English alphabet (with no spaces).

The number of letters will be between 1 and 100.

Output Specification

Output the original (decrypted) message.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2


Sample Input 3


Sample Output 3


Ivica wants to send the message bombonisuuladici containing 16 letters. He can use a 1 \times 16, 2 \times 8 or 4 \times 4 matrix. Of these, the 4 \times 4 has the most rows. When the message is written into it, the matrix looks like this:

b o m b
o n i s
u u l a
d i c i


There are no comments at the moment.