Return to Problem Sets

Competition Programming: 
Problem Set 3

Problem A: Free Lunch

A (fixed) group of students usually had lunch in the same cafeteria near the campus. They always sat at the same table, which had exactly as many seats as there were students. According to their tradition, they never sat the same way as before; that is, they used different permutations. The owner of the cafeteria eventually learned of this tradition, and decided to use it in a tricky marketing scheme. Specifically, he told the students that, once they try all possible permutations, they would get an unlimited number of free lunches. The students had never taken combinatorics, and they did not realize that they needed to have n! lunches before getting their first free meal. Thus, they continued eating in the same cafeteria, hoping to earn their free lunches.

The tricky owner, however, did not account for the fact that some students were identical siblings. The owner could not distinguish identical siblings from each other, which reduced the number of distinct sitting arrangements. For example, if the group included four students, and two of them were identical twins, then the number of distinct arrangements was 12 rather than 4! = 24. This consideration made the combinatorial problem more complex, and the owner decided to hire a programmer, to help him figure out how soon he would need to serve free lunches. Your task is to help him, by identifying all seating arrangements and determining their total number.

Input

The input is a single string of lower-case letters, where each letter represents a student; its length is between one and thirty. We represent identical siblings by identical letters; for example, the string ccddda describes six students, including identical twins (cc), identical triplets (ddd), and a student with no siblings (a).

Output

The first line of the output is the number of distinct strings that can be formed by permuting the input string. The other lines are distinct permutations of the string, in the alphabetical order, one permutation per line. You may assume that the total number of these permutations is at most 100,000.

Sample Input 

fcac
Sample Output 
12
accf
acfc
afcc
cacf
cafc
ccaf
ccfa
cfac
cfca
facc
fcac
fcca

Problem B: Star Wars Sorting

Soon after defeating the evil Empire, Han Solo and Chewbacca visited one of unexplored planets, and discovered a tribe of primitive people. Han Solo befriended the chief of the tribe, and learned that the chief had a hobby of recording various numeric properties of tribespeople, and making sorted lists of these properties. For example, he had a sorted list of the ages of tribe members, and another sorted list that showed how many mammoths each hunter caught during the last season. Unfortunately, the chief did not have any measuring devices, which limited his ability to obtain numeric data. To help the chief, Han Solo gave him a weighing machine, which enabled him to weigh tribespeople. Han Solo also taught the chief basics of the alphabet, and showed how to write down the names of tribe members. The chief soon created a list of the names and weights of all tribespeople, and tried to sort it. Unfortunately, the task proved unexpectedly difficult, because the chief had no experience with real numbers or alphabetical strings. Your task it to write a program that would help the chief with his sorting hobby.

Input

The input is a list of names and weights of tribe members; each line includes one name and the respective weight, separated by a single space. The name is a string of lower-case letters, which may include from one to thirty letters. The weight is a strictly positive real value between 10-20 and 1020. The last line is the string "end 0", which does not represent a tribe member.

Output

The output consists of two lists of names, with a blank line between the lists; each name in the lists is on a separate line. The first list is in the aplhabetical order of names, whereas the second list is in the increasing order of weights, with ties broken by the alphabetical order of the names.

Sample Input 

apeman 1e+20
neanderthal 2.0
snowman 1.0
neanderthal 1.0
bigfoot 1e-20
end 0
Sample Output 
apeman
bigfoot
neanderthal
neanderthal
snowman

bigfoot
neanderthal
snowman
neanderthal
apeman

Problem C: Very Long Sequence

We consider four positive integer values, denoted b, c, p, and q, and define the following finite sequence a0, a1, a2, ..., an-1 based on these values:
a0 = b
a1 = c
ai = (ai-1 mod p) + (ai-2 mod q) + 1 (for all i from 2 to n-1) 

Your task is to find the specified order statistics of this sequence. Note that we enumerate the order statistics from 1 to n (rather than from 0 to n-1); that is, the minimum is the 1st order statistic, and the maximum is the nth order statistic.

Input

The input consists of two lines, each of which is at most eighty character long. The first line includes five positive integers, separated by single spaces, which represent the values of b, c, p, q, and n. The values of b, c, p, and q are between 1 and 104, whereas n is between 1 and 109. The second line includes a list of positive integers that represent the required order statistics; each order statistic is between 1 and n. The last value on the second line is 0, which does not represent an order statistic.

Output

The output is a single line of positive integers, separated by single spaces, which represent the values of the given order statistics.

Resource Limits

You program should take at most 0.5 GByte memory, and it should complete the computation in 30 seconds on a 3-GHz computer.

Sample Input 

1 1 3 2 6
1 3 6 0
Sample Output 
1 2 4