1.

PC/UVa IDs: 110104/706, Popularity: A, Success rate: average Level: 1

A friend of yours has just bought a new computer. Before this, the most powerful machine he
ever used was a pocket calculator. He is a little disappointed because he liked the LCD display of
his calculator more than the screen on his new computer! To make him happy, write a program
that prints numbers in LCD display style.

Input The input file contains several lines, one for each number to be displayed. Each line
contains integers s and n, where n is the number to be displayed (0 ≤ n ≤ 99, 999, 999) and s is
the size in which it shall be displayed (1 ≤ s ≤ 10). The input will be terminated by a line containing
two zeros, which should not be processed.

Output Print the numbers specified in the input file in an LCD display-style using s “-” signs for
the horizontal segments and s “|” signs for the vertical ones. Each digit occupies exactly s + 2
columns and 2s + 3 rows. Be sure to fill all the white space occupied by the digits with blanks,
including the last digit. There must be exactly one column of blanks between two digits. Output
a blank line after each number. You will find an example of each digit in the sample output
below.

2. PC/UVa IDs: 110303/10252, Popularity: A, Success rate: average Level: 1

Given two strings a and b, print the longest string x of letters such that there is a permutation of
x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

Input The input file contains several cases, each case consisting of two consecutive lines. This
means that lines 1 and 2 are a test case, lines 3 and 4 are another test case, and so on. Each line
contains one string of lowercase characters, with first line of a pair denoting a and the second
denoting b. Each string consists of at most 1,000 characters.

Output For each set of input, output a line containing x. If several x satisfy the criteria above,
choose the first one in alphabetical order.
3. PC/UVa IDs: 110501/10035, Popularity: A, Success rate: average Level: 1

Children are taught to add multi-digit numbers from right to left, one digit at a time. Many find
the “carry” operation, where a 1 is carried from one-digit position to the next, to be a significant
challenge. Your job is to count the number of carry operations for each of a set of addition
problems so that educators may assess their difficulty.

Input

Each line of input contains two unsigned integers less than 10 digits. The last line of input
contains “0 0”.

Output

For each line of input except the last, compute the number of carry operations that result from
adding the two numbers and print them in the format shown below.

4. PC/UVa IDs: 110502/10018, Popularity: A, Success rate: low Level: 1

The reverse and add function starts with a number, reverses its digits, and adds the reverse to
the original. If the sum is not a palindrome (meaning it does not give the same number read
from left to right and right to left), we repeat this procedure until it does. For example, if we
start with 195 as the initial number, we get 9,339 as the resulting palindrome after the fourth
addition:
This method leads to palindromes in a few steps for almost all of the integers. But there are
interesting exceptions. 196 is the first number for which no palindrome has been found. It has
never been proven, however, that no such palindrome exists. You must write a program that
takes a given number and gives the resulting palindrome (if one exists) and the number of
iterations/additions it took to find it. You may assume that all the numbers used as test data will
terminate in an answer with less than 1,000 iterations (additions), and yield a palindrome that
is not greater than 4,294,967,295.

Input

The first line will contain an integer N (0 < N ≤ 100), giving the number of test cases, while the
next N lines each contain a single integer P whose palindrome you are to compute.

Output

For each of the N integers, print a line giving the minimum number of iterations to find the
palindrome, a single space, and then the resulting palindrome itself.

Example:

5. PC/UVa IDs: 110701/10110, Popularity: A, Success rate: average Level: 1

There is man named Edison who switches on-off the lights along a corridor at our university.
Every bulb has its own toggle switch that changes the state of the light. If the light is off, pressing
the switch turns it on. Pressing it again will turn it off. Initially each bulb is off. He does a peculiar
thing. If there are n bulbs in a corridor, he walks along the corridor back and forth n times. On
the ith walk, he toggles only the switches whose position is divisible by i. He does not press any
switch when coming back to his initial position. The ith walk is defined as going down the
corridor (doing his peculiar thing) and coming back again. Determine the final state of the last
bulb. Is it on or off?

Input

The input will be an integer indicating the nth bulb in a corridor, which is less than or equal to
232 − 1. A zero indicates the end of input and should not be processed.

Output

Output “yes” or “no” to indicate if the light is on, with each case appearing on its own line.
6. PC/UVa IDs: 110702/10006, Popularity: A, Success rate: average Level: 2

Certain cryptographic algorithms make use of big prime numbers. However, checking whether
a big number is prime is not so easy. Randomized primality tests exist that offer a high degree
of confidence of accurate determination at low cost, such as the Fermat test. Let a be a random
number between 2 and n − 1, where n is the number whose primality we are testing. Then, n is
probably prime if the following equation holds:

an mod n = a

If a number passes the Fermat test several times, then it is prime with a high probability.
Unfortunately, there is bad news. Certain composite numbers (non-primes) still pass the Fermat
test with every number smaller than themselves. These numbers are called Carmichael
numbers. Write a program to test whether a given integer is a Carmichael number.

Input

The input will consist of a series of lines, each containing a small positive number n (2 <n< 65,
000). A number n = 0 will mark the end of the input and must not be processed.

Output

For each number in the input, print whether it is a Carmichael number or not as shown in the
sample output.

7. PC/UVa IDs: 110704/10139, Popularity: A, Success rate: average Level: 2

The factorial function, n! is defined as follows for all non-negative integers n:

0! = 1

n! = n × (n − 1)! (n > 0)

We say that a divides b if there exists an integer k such that k × a = b

Input

The input to your program consists of several lines, each containing two non-negative integers,
n and m, both less than 231.

Output

For each input line, output a line stating whether or not m divides n!, in the format shown below.
8. Successor

It is 2084 and the year of Big Brother has finally arrived, albeit a century late. In order to exercise
greater control over its citizens and thereby to counter a chronic breakdown in law and order,
the Government decides on a radical measure — all citizens are to have a tiny microcomputer
surgically implanted in their left wrists. This computer will contains all sorts of personal
information as well as a transmitter which will allow people’s movements to be logged and
monitored by a central computer. (A desirable side effect of this process is that it will shorten
the dole queue for plastic surgeons.) An essential component of each computer will be a unique
identification code, consisting of up to 50 characters drawn from the 26 lower case letters. The
set of characters for any given code is chosen somewhat haphazardly. The complicated way in
which the code is imprinted into the chip makes it much easier for the manufacturer to produce
codes which are rearrangements of other codes than to produce new codes with a different
selection of letters. Thus, once a set of letters has been chosen all possible codes derivable from
it are used before changing the set. For example, suppose it is decided that a code will contain
exactly 3 occurrences of ‘a’, 2 of ‘b’ and 1 of ‘c’, then three of the allowable 60 codes under
these conditions are:

abaabc

abaacb

ababac

These three codes are listed from top to bottom in alphabetic order. Among all codes generated
with this set of characters, these codes appear consecutively in this order. Write a program to
assist in the issuing of these identification codes. Your program will accept a sequence of no
more than 50 lower case letters (which may contain repeated characters) and print the
successor code if one exists or the message ‘No Successor’ if the given code is the last in the
sequence for that set of characters.

Input

Input will consist of a series of lines each containing a string representing a code. The entire file
will be terminated by a line consisting of a single ‘#’.

Output
Output will consist of one line for each code read containing the successor code or the words
‘No Successor’. Sample Input abaacb cbbaa # Sample Output ababac No Successor

9. What Day Is It?

The calendar now in use evolved from the Romans. Julius Caesar codified a calendar system that
came to be known as the Julian calendar. In this system, all months have 31 days, except for
April, June, September, and November, which have 30 days, and February, which has 28 days in
non-leap years, and 29 days in leap years. Also, in this system, leap years happened every four
years. That is because the astronomers of ancient Rome computed the year to be 365.25 days
long, so that after every four years, one needed to add an extra day to keep the calendar on
track with the seasons. To do this, they added an extra day (February 29) to every year that was
a multiple of four. Julian Rule: Every year that is a multiple of 4 is a leap year, i.e. has an extra
day (February 29). In 1582, Pope Gregory’s astronomers noticed that the year was not 365.25
days long, but closer to 365.2425. Therefore, the leap year rule would be revised to the
following:

Gregorian Rule: Every year that is a multiple of 4 is a leap year, unless it is a multiple of 100 that
is not a multiple of 400. To compensate for how the seasons had shifted against the calendar up
until that time, the calendar was actually shifted 10 days: the day following October 4, 1582 was
declared to be October 15. England and its empire (including the United States) didn’t switch to
the Gregorian calendar system until 1752, when the day following September 2 was declared to
be September 14. (The delay was caused by the poor relationship between Henry VIII and the
Pope.)

Write a program that converts dates in the United States using a calendar of the time and
outputs weekdays.

Input

The input will be a series of positive integers greater than zero, three integers per line, which
represent dates, one date per line. The format for a date is “month day year” where month is a
number between 1 (which indicates January) and 12 (which indicates December), day is a
number between 1 and 31, and year is positive number. The input will end with three zeroes,
and this case won’t be processed.

Output

The output will be the input date and name of the weekday on which the given date falls in the
format shown in the sample. An invalid date or nonexistent date for the calendar used in the
United States at the time should generate an error message indicating a invalid date.

Sample Input
11 15 1997
1 1 2000
7 4 1998
2 11 1732
9 2 1752
9 14 1752
4 33 1997
000
Sample Output

November 15, 1997 is a Saturday

10. Roman Numerals

This year is the XXV Anniversary of the Faculty of Computer Science in Murcia. But, what XXV
means? Maybe you should ask an ancient Roman to get the answer. A Roman numeral consists
of a set of letters of the alphabet. Each letter has a particular value, as shown in the following
table:

Generally, Roman numerals are written in descending order from left to right, and are added
sequentially. However, certain combinations employ a subtractive principle. If a symbol of
smaller value precedes a symbol of larger value, the smaller value is subtracted from the larger
value, and the result is added to the total. This subtractive principle follows the next rules:

• “I” may only precede “V” and “X” (e.g., IV = 4).

Symbols “I”, “X”, “C” and “M” cannot appear more than three consecutive times. Symbols “V”,
“L” and “D” cannot appear more than once consecutively.

Roman numerals do not include the number zero, and for values greater or equal than 4000
they used bars placed above the letters to indicate multiplication by 1000.

You have write a program that converts from Roman to Arabic numerals and vice versa.
Although lower case letters were used in the Middle Ages, the Romans only used upper case
letters. Therefore, for the Roman numerals we only consider upper case letters.

Input

The input consists of several lines, each one containing either an Arabic or a Roman number n,
where 0 < n < 4000.

Output

For each input line, you must print a line with the converted number. If the number is Arabic,
you must give it in Roman format. If the number is Roman, you must give it in Arabic format.
Sample Input

XXV
4
942
MCMLXXXIII

Sample Output

25
IV
CMXLII
1983