Competition Programming:
Problem Set 11
Problem A: Palindromes
A string of letters is a palindrome if it reads the same forward
and backward; for example, abba and noon are palindromes.
When determining whether a string is a palindrome, we do not distinguish
between lower and upper cases; for example, Abba and NoOn
are also palindromes. A sentence is a palindrome if its letters form a
palindrome after the removal of all nonalphabetic characters; for instance,
"Madam, I'm Adam" and "A man, a plan, a canal--Panama" are
palindromes. Your task is to write a program that checks whether a given
sentence is a palindrome.
Input
The input consists of multiple sentences, which may include letters, spaces,
line breaks, and any punctuation marks except periods; note that a sentence
may comprise multiple lines. Each sentence includes between 2 and 100,000
characters, and the total number of sentences is at most 20. The separator
between consecutive sentences is a single period on a line by itself; the
last two lines of the input, after the last sentence, are also single-period
lines.
Output
For each sentence, the output includes the word yes or no
on a separate line. If the sentence is a palindrome, the respective output
is yes; else, it is no.
Sample input
A man, a plan, a cat, a ham, a yak,
a yam, a hat, a canal--Panama!
.
Oo (Oo) ((Oo))
.
This sentence is not a palindrome
.
Abcddcba
.
.
Sample output
yes
yes
no
yes
Problem B: Stubborn numbers
The game of stubborn numbers is a one-player game, invented for
the purpose of teaching addition in the primary school. A player takes
a given positive integer and checks whether it is a palindrome; if not,
she writes its digits in the backward order, removes any leading zeros,
and adds the resulting number to the original integer. For example, if
the given integer is 261, the player calculates 261 + 162 = 423. If the
sum is not a palindrome, the player repeats the same steps; that is, she
reverses its digits and adds the resulting number to the sum; for example,
since 423 is not a palindrome, she next calculates 423 + 324 = 747. The
player repeats these steps until she obtains a palindrome. When a teacher
give an initial integer to a pupil, she has to check the number of steps
required for obtaining a palindrome, and ensure that it is not too large.
Your task is to write a program that helps the teacher to determine the
number of steps for each given integer.
Input
The input includes a list of positive integers, each on a separate line;
every integer includes between 2 and 60 digits, and the total number of
integers is at most 1000. The last line is "0", which does not represent
an integer.
Output
For each integer, the output is the number of steps required for obtaining
a palindrome. If the integer does not become a palindrome after 1000 steps,
the respective output is "too many".
Sample input
11
123
239
261
0
Sample output
0
1
2
2
Problem C: Cryptic matrices
The Cryptic Matrix Union (CMU) is a secret society
of computer nerds, who use the cryptic-matrix code for their secret messages.
When a CMU member needs to encrypt a message, she
cuts a 2n x 2n matrix out of graph
paper and writes her message on this matrix in the row-major order. For
example, if the message is "Nerds-are-cool!!", then the matrix is
as shown in Figure 1. She then pins the top left corner of the matrix to
the desk, folds the matrix along the horizontal axis as shown in Figure
2, and then folds it along the vertical axis as shown in Figure 3. Then,
she folds the resulting 2n-1 x 2n-1
matrix again along the horizontal axis, and then again along the vertical
axis, and so on, until the matrix "collapses" into a single cell. Finally,
she writes the characters of the message in the order as they appear in
the resulting stack of cells, from the top to the bottom, thus obtaining
an encrypted message. Your task is to write a program that helps CMU
members to encrypt and decrypt their messages.
Input
The input consists of two lists of messages; your program should encrypt
the messages in the first list, and decrypt the messages in the second
list. A message may include letters and punctuation marks except periods;
note that it does not include spaces. A message may also include line breaks
inserted for readability, but they are not part of the message, and your
program should skip them. Each message includes exactly 22n
characters, for some n between 2 and 10; the total number
of messages is at most 10. The separator between consecutive messages is
a single period on a line by itself; the first list of messages ends with
two single-period lines, and the second list also ends with two such lines.
Output
For each message in the first list, the output is the respective encrypted
message; for each message in the second list, the output is the respective
decrypted message. If a message is longer than 60 characters, your program
should output a line break after each 60 characters. The output should
include a single-period line between consecutive messages, two single-period
lines after the list of encrypted messages, and two such lines after the
list of decrypted messages.
Sample input
abcd
.
Nerds-are-
cool!!
.
.
bdca
.
el!rac--seord!oN
.
.
Sample output
bdca
.
el!rac--seord!oN
.
.
abcd
Nerds are cool!!
.
.
