Uva 514: Rails (solution)

Rails


There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.



The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N ≤ 1000 coaches numbered in increasing order 1, 2, . . . , N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, . . . , aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

Input


The input file consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, . . . , N The last line of the block contains just 0. The last block consists of just one line containing 0.

The input must be read from standard input.

Output


The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input file. There is no empty line in the output file corresponding to the last “null” block of the input file.

The output must be written to standard output.

Sample Input



5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0

Sample Output


Yes
No

Yes

SOLUTION: Python


SOLUTION: C++

UVA 540: Team Queue (solution)

Team Queue

Queues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa is a team queue, for example. In a team queue each element belongs to a team. If an element enters the queue, it first searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue. Your task is to write a program that simulates such a team queue.

Input


The input file will contain one or more test cases. Each test case begins with the number of teams t ( 1 ≤ t ≤ 1000). Then t team descriptions follow, each one consisting of the number of elements belonging to the team and the elements themselves. Elements are integers in the range 0-999999. A team may consist of up to 1000 elements. Finally, a list of commands follows. There are three different kinds of commands: ENQUEUE x: enter element x into the team queue. DEQUEUE: process the first element and remove it from the queue. STOP: end of test case. The input will be terminated by a value of 0 for t. The input must be read from standard input.

Output


For each test case, first print a line saying “Scenario #k”, where k is the number of the test case. Then, for each DEQUEUE command, print the element which is dequeued on a single line. Print a blank line after each test case, even after the last one. The output must be written to standard output.

Sample Input



2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP

2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0


Sample Output



Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001

SOLUTION: Python


SOLUTION: C++

UVA 305: Joseph (solution)

Joseph

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, ..., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.


Input


The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.


Output


The output file will consist of separate lines containing m corresponding to k in the input file.


Sample Input



3
4
0


Sample Output



5
30

SOLUTION: C++

UVA 458: The Decoder (solution)

The Decoder

Write a complete program that will correctly decode a set of characters into a valid message. Your program should read a given file of a simple coded set of characters and print the exact message that the characters contain. The code key for this simple coding is a one for one character substitution based upon a single arithmetic manipulation of the printable portion of the ASCII character set.

Input / Output


For example: with the input file that contains:

1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5
your program should print the message:
*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.
Your program should accept all sets of characters that use the same encoding scheme and should print the actual message of each set of characters.

Sample Input



1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5





Sample Output






*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.






SOLUTION: C++
















UVA 108: Maximum Sum (solution)






Maximum Sum









Background





A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem.









The Problem





Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. As an example, the maximal sub-rectangle of the array:




0  -2  -7  0

9  2  -6  2

-4  1  -4  1

-1  8  0  -2





is in the lower-left-hand corner:




9  2

-4  1

-1  8





and has the sum of 15.





Input / Output

The input consists of an NxN array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by N^2 integers separated by white-space (newlines and spaces). These N^2 integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100. The numbers in the array will be in the range [-127, 127].



The output is the sum of the maximal sub-rectangle.







Sample Input








4
0 -2 -7  0 9  2 -6  2
-4  1 -4  1 -1
8  0 -2





Sample Output








15 




SOLUTION: C++

















Uva 113: Power of Cryptography (solution)


Power of Cryptography 



Background

Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers modulo functions of these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be of only theoretical interest.

This problem involves the efficient computation of integer roots of numbers.





The Problem

Given an integer n>= 1 and an integer p>=1 you are to write a program that determines a(sqrt(p))

 , the positive n^th root of p. In this problem, given such integers n and p, p will always be of the form k^n for an integer k (this integer is what your program must find).





Input

The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs 1<= n <= 200, 1<= p <= 10^101 and there exists an integer k, 1 <=k <=10^9 such that k^n = p .





Output

For each integer pair n and p the value a(sqrt(p)) should be printed, i.e., the number k such that k^n = p .





Sample Input




2
16
3
27
7
4357186184021382204544





Sample Output




4
3
1234




SOLUTION: C++

















Uva 120: Stacks of Flapjacks (solution)


Stacks of Flapjacks





Background



Stacks and Queues are often considered the bread and butter of data structures and find use in architecture, parsing, operating systems, and discrete event simulation. Stacks are also important in the theory of formal languages.

This problem involves both butter and sustenance in the form of pancakes rather than bread in addition to a finicky server who flips pancakes according to a unique, but complete set of rules.



The Problem



Given a stack of pancakes, you are to write a program that indicates how the stack can be sorted so that the largest pancake is on the bottom and the smallest pancake is on the top. The size of a pancake is given by the pancake's diameter. All pancakes in a stack have different diameters.

Sorting a stack is done by a sequence of pancake ``flips''. A flip consists of inserting a spatula between two pancakes in a stack and flipping (reversing) the pancakes on the spatula (reversing the sub-stack). A flip is specified by giving the position of the pancake on the bottom of the sub-stack to be flipped (relative to the whole stack). The pancake on the bottom of the whole stack has position 1 and the pancake on the top of a stack of n pancakes has position n.

A stack is specified by giving the diameter of each pancake in the stack in the order in which the pancakes appear.

For example, consider the three stacks of pancakes below (in which pancake 8 is the top-most pancake of the left stack):


         8           7           2
         4           6           5
         6           4           8
         7           8           4
         5           5           6
         2           2           7

The stack on the left can be transformed to the stack in the middle via flip(3). The middle stack can be transformed into the right stack via the command flip(1).



Input





The input consists of a sequence of stacks of pancakes. Each stack will consist of between 1 and 30 pancakes and each pancake will have an integer diameter between 1 and 100. The input is terminated by end-of-file. Each stack is given as a single line of input with the top pancake on a stack appearing first on a line, the bottom pancake appearing last, and all pancakes separated by a space.



Output



For each stack of pancakes, the output should echo the original stack on one line, followed by some sequence of flips that results in the stack of pancakes being sorted so that the largest diameter pancake is on the bottom and the smallest on top. For each stack the sequence of flips should be terminated by a 0 (indicating no more flips necessary). Once a stack is sorted, no more flips should be made.



Sample Input






1 2 3 4 5
5 4 3 2 1
5 1 2 3 4







Sample Output




1 2 3 4 5
0
5 4 3 2 1
1 0
5 1 2 3 4
1 2 0



SOLUTION: C++




















Suscribirse a:
Entradas (Atom)