| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 3396 | Finding Nemo |
|
| 3397 | Searching the Web |
|
| 3398 | Argus |
|
| 3399 | Fun Game |
|
| 3400 | Square |
|
| 3401 | Color a Tree |
|
| 3402 | Kid's Problem |
|
| 3403 | The Separator in Grid |
|
| 3404 | The Lost House |
|
| 7475 | (*) All Discs Considered |
|
| 7476 | (*) Boolean Logic |
|
| 7477 | (*) Code |
|
| 7478 | (*) In Danger |
|
| 7479 | (*) Run Length Encoding |
|
| 7480 | (*) Fractran |
|
| 7481 | (*) Huffman's Greed |
|
| 7482 | (*) Binary Search Heap Construction |
|
Description
Operating systems are large software artefacts composed of many packages, usually distributed on several media, e.g., discs. You probably remember the time when your favourite operating system was delivered on 21 floppy discs, or, a few years later, on 6 CDs. Nowadays, it will be shipped on several DVDs, each containing tens of thousands of packages.
The installation of certain packages may require that other packages have been installed previously. Therefore, if the packages are distributed on the media in an unsuitable way, the installation of the complete system requires you to perform many media changes, provided that there is only one reading device available, e.g., one DVD-ROM drive. Since you have to start the installation somehow, there will of course be one or more packages that can be installed independently of all other packages.
Given a distribution of packages on media and a list of dependences between packages, you have to calculate the minimal number of media changes required to install all packages. For your convenience, you may assume that the operating system comes on exactly 2 DVDs.
Input
The input contains several test cases. Every test case starts with three integers N1, N2, D. You may assume that 1<=N1,N2<=50000 and 0<=D<=100000. The first DVD contains N1 packages, identified by the numbers 1, 2, ..., N1. The second DVD contains N2 packages, identified by the numbers N1+1, N1+2, ..., N1+N2. Then follow D dependence specifications, each consisting of two integers xi, yi. You may assume that 1<=xi,yi<=N1+N2 for 1<=i<=D. The dependence specification means that the installation of package xi requires the previous installation of package yi. You may assume that there are no circular dependences. The last test case is followed by three zeros.
Output
For each test case output on a line the minimal number of DVD changes required to install all packages. By convention, the DVD drive is empty before the installation and the initial insertion of a disc counts as one change. Likewise, the final removal of a disc counts as one change, leaving the DVD drive empty after the installation.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Propositions are logical formulas consisting of proposition symbols and connecting operators. They are recursively defined by the following rules:
1. All proposition symbols (in this problem, lower-case alphabetic characters, e.g., a and z) are propositions.
2. If P is a proposition, (!P) is a proposition, and P is a direct subformula of it.
3. If P and Q are propositions, (P&Q), (P|Q), (P-->Q), and (P<->Q) are propositions, and P and Q are direct subformulas of them.
4. Nothing else is a proposition.
The operations !, &, |, -->, and <-> denote logical negation, conjunction, disjunction, implication, and equivalence, respectively. A proposition P is a subformula of a proposition R if P=R or P is a direct subformula of a proposition Q and Q is a subformula of R.
Let P be a proposition and assign boolean values (i.e., 0 or 1) to all proposition symbols that occur in P. This induces a boolean value to all subformulas of P according to the standard semantics of the logical operators:
negation conjunction disjunction implication equivalence
!0=1 0&0=0 0|0=0 0-->0=1 0<->0=1
!1=0 0&1=0 0|1=1 0-->1=1 0<->1=0
1&0=0 1|0=1 1-->0=0 1<->0=0
1&1=1 1|1=1 1-->1=1 1<->1=1
This way, a value for P can be calculated. This value depends on the choice of the assignment of boolean values to the proposition symbols. If P contains n different proposition symbols, there are 2n different assignments. To evaluate all possible assignments we may use truth tables.
A truth table contains one line per assignment (i.e., 2n lines in total). Every line contains the values of all subformulas under the chosen assignment. The value of a subformula is aligned with the proposition symbol, if the subformula is a proposition symbol, and with the center of the operator otherwise.
Input
The input contains several test cases, each on a separate line. Every test case denotes a proposition and may contain arbitrary amounts of spaces in between. The input file terminates immediately after the newline symbol following the last test case.
Output
For each test case generate a truth table for the denoted proposition. Start the truth table by repeating the input line. Evaluate the proposition (and its subformulas) for all assignments to its variables, and output one line for each assignment. The line must have the same length as the corresponding input line and must consist only of spaces and the characters 0 and 1. Output an empty line after each test case.
Let s1,...,sn be the proposition symbols in the denoted proposition sorted in alphabetic order. Then, all assignments of 0 to s1 must precede the assignments of 1 to s1. Within each of these blocks of assignments, all assignments of 0 to s2 must precede the assignments of 1 to s2, and so on.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
KEY Inc., the leading company in security hardware, has developed a new kind of safe. To unlock it, you don't need a key but you are required to enter the correct n-digit code on a keypad (as if this were something new!). There are several models available, from toy safes for children (with a 2-digit code) to the military version (with a 6-digit code).
The safe will open as soon as the last digit of the correct code is entered. There is no "enter" key. When you enter more than n digits, only the last n digits are significant. For example (in the 4-digit version), if the correct code is 4567, and you plan to enter the digit sequence 1234567890, the door will open as soon as you press the 7 key.
The software to create this effect is rather simple. In the n-digit version the safe is always in one of 10n-1 internal states. The current state of the safe simply represents the last n-1 digits that have been entered. One of these states (in the example above, state 456) is marked as the unlocked state. If the safe is in the unlocked state and then the right key (in the example above, 7) is pressed, the door opens. Otherwise the safe shifts to the corresponding new state. For example, if the safe is in state 456 and then you press 8, the safe goes into state 568.
A trivial strategy to open the safe is to enter all possible codes one after the other. In the worst case, however, this will require n * 10n keystrokes. By choosing a good digit sequence it is possible to open the safe in at most 10n + n - 1 keystrokes. All you have to do is to find a digit sequence that contains all n-digit sequences exactly once. KEY Inc. claims that for the military version (n=6) the fastest computers available today would need billions of years to find such a sequence - but apparently they don't know what some programmers are capable of...
Input
The input contains several test cases. Every test case is specified by an integer n. You may assume that 1<=n<=6. The last test case is followed by a zero.
Output
For each test case specified by n output a line containing a sequence of 10n + n - 1 digits that contains each n-digit sequence exactly once.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Flavius Josephus and 40 fellow rebels were trapped by the Romans. His companions preferred suicide to surrender, so they decided to form a circle and to kill every third person and to proceed around the circle until no one was left. Josephus was not excited by the idea of killing himself, so he calculated the position to be the last man standing (and then he did not commit suicide since nobody could watch).
We will consider a variant of this "game" where every second person leaves. And of course there will be more than 41 persons, for we now have computers. You have to calculate the safe position. Be careful because we might apply your program to calculate the winner of this contest!
Input
The input contains several test cases. Each specifies a number n, denoting the number of persons participating in the game. To make things more difficult, it always has the format "xyez" with the following semantics: when n is written down in decimal notation, its first digit is x, its second digit is y, and then follow z zeros. Whereas 0<=x,y<=9, the number of zeros is 0<=z<=6. You may assume that n>0. The last test case is followed by the string 00e0.
Output
For each test case generate a line containing the position of the person who survives. Assume that the participants have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2. For example, if there are 5 persons in the circle, counting proceeds as 2, 4, 1, 5 and person 3 is staying alive.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Your task is to write a program that performs a simple form of run-length encoding, as described by the rules below.
Any sequence of between 2 to 9 identical characters is encoded by two characters. The first character is the length of the sequence, represented by one of the characters 2 through 9. The second character is the value of the repeated character. A sequence of more than 9 identical characters is dealt with by first encoding 9 characters, then the remaining ones.
Any sequence of characters that does not contain consecutive repetitions of any characters is represented by a 1 character followed by the sequence of characters, terminated with another 1. If a 1 appears as part of the sequence, it is escaped with a 1, thus two 1 characters are output.
Input
The input consists of letters (both upper- and lower-case), digits, spaces, and punctuation. Every line is terminated with a newline character and no other characters appear in the input.
Output
Each line in the input is encoded separately as described above. The newline at the end of each line is not encoded, but is passed directly to the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
To play the "fraction game" corresponding to a given list f1, f2, ..., fk of fractions and starting integer N, you repeatedly multiply the integer you have at any stage (initially N) by the earliest fi in the list for which the answer is integral. Whenever there is no such fi, the game stops.
Formally, we define a sequence by S0=N, and Sj+1=fiSj, if for 1<=i<=k, the number fiSj is an integer but the numbers f1Sj, ..., fi-1Sj are not.
For example, if we have the list of eight fractions f1=170/39, f2=19/13, f3=13/17, f4=69/95, f5=19/23, f6=1/19, f7=13/7, f8=1/3, and start with N=21, we produce the (finite) sequence (21,39,170,130,190,138,114,6,2). In general, the sequence may be infinite.
Given a fraction list and a starting integer calculate a part of the defined sequence. Actually, we are interested only in the powers of 2 that appear in the sequence.
Input
The input contains several test cases. Every test case starts with three integers m, N, k. You may assume that 1<=m<=40, 1<=N<=1000, and 1<=k<=100. Then follow k fractions f1, ..., fk. For each fraction, first its numerator is given, followed by its denominator. You may assume that both are positive integers less than 1000 and their greatest common divisor is 1. The last test case is followed by a zero.
Output
For each test case output on a line m numbers e1, ..., em, separated by one space character, such that 2e1, ..., 2ek are the first m numbers in the defined sequence that are powers of 2. You may assume that there are at least m powers of 2 among the first 7654321 elements of the sequence.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the following we define the basic terminology of trees. A tree is defined inductively: It has a root which is either an external node (a leaf), or an internal node having a sequence of trees as its children. An internal node is also called the parent of the roots of its child trees. The level of a node in a tree is defined inductively: The root has level 0, and the level of a node is 1 more than the level of its parent node.
Every internal node of a binary tree has precisely two children, its left sub-tree and its right sub-tree. Every internal node of a labelled binary tree is additionally marked with a string, its label. A binary search tree is a labelled binary tree where every internal node t satisfies the following condition: All labels of nodes in the left sub-tree of t are less than the label of t which is, in turn, less than all labels of nodes in the right sub-tree of t. For this condition, we assume lexicographic, i.e., alphabetic order on the strings.
An inorder traversal of a tree is defined recursively: A leaf is just visited, and for an internal node first its left sub-tree is traversed inorder, then the node itself is visited, finally its right sub-tree is traversed inorder. It follows that an inorder traversal of a binary search tree yields the labels in lexicographic order. Note that binary search trees whose shapes differ may nevertheless yield the same sequence of strings while being traversed inorder.
When a given string s is looked for in a binary search tree, we compare s to the label l of the root. We are done if s=l, otherwise if s
The number of comparisons performed in such a search procedure depends on s and the actual shape of the search tree. Therefore, there is an interest in constructing binary search trees that store a given sequence of strings but provide as efficient access as possible. Of course, we don't know in advance which strings will be looked up in the tree, so we need to make some assumptions.
Let n be the number of strings that are to be stored in the binary search tree. Let K1,...,Kn be these strings in lexicographic order. Let p1,...,pn and q0,...,qn be 2n+1 non-negative real numbers such that ∑i=1..n pi + ∑i=0..n qi = 1. The interpretation of these numbers is:
• pi = probability that the search argument s is Ki.
• qi = probability that s lies (lexicographically) strictly between Ki and Ki+1.
By convention, q0 is the probability that s is less than K1, and qn is the probability that s is greater than Kn. We want to find a binary search tree containing nodes with labels K1,...,Kn that minimises the expected number of comparisons in the search, namely
cost = ∑i=1..n pi*(1 + level of internal node Ki) + ∑i=0..n qi*(level of leaf between Ki and Ki+1).
The leaf between Ki and Ki+1 is that leaf reached in the search for a string s that lies (lexicographically) strictly between Ki and Ki+1. Adhere to the convention stated above for the border cases.
The following figure illustrates the first test case of the sample input. It shows the two possible binary search trees, the probabilities and the associated costs. 
.bmp)
Input
The input contains several test cases. Every test case starts with an integer n. You may assume that 1<=n<=200. Then follow 2n+1 non-negative integers denoting frequencies. Let s be the sum of all frequencies. You may assume that 1<=s<=1000000. The probabilities p1,...,pn and q0,...,qn are calculated in this order by dividing the frequencies by s. The last test case is followed by a zero.
Output
For each test case devise a binary search tree whose cost is minimal for the specified probabilities. Output the integer cost*s for such a tree.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Read the statement of problem G for the definitions concerning trees. In the following we define the basic terminology of heaps. A heap is a tree whose internal nodes have each assigned a priority (a number) such that the priority of each internal node is less than the priority of its parent. As a consequence, the root has the greatest priority in the tree, which is one of the reasons why heaps can be used for the implementation of priority queues and for sorting.
A binary tree in which each internal node has both a label and a priority, and which is both a binary search tree with respect to the labels and a heap with respect to the priorities, is called a treap. Your task is, given a set of label-priority-pairs, with unique labels and unique priorities, to construct a treap containing this data.
Input
The input contains several test cases. Every test case starts with an integer n. You may assume that 1<=n<=50000. Then follow n pairs of strings and numbers l1/p1,...,ln/pn denoting the label and priority of each node. The strings are non-empty and composed of lower-case letters, and the numbers are non-negative integers. The last test case is followed by a zero.
Output
For each test case output on a single line a treap that contains the specified nodes. A treap is printed as (