Thursday, March 31, 2011

UVa_00846_Steps.cpp

Problem Links:

Problem:

Steps

One steps through integer points of the straight line. The length of a step must be nonnegative and can be by one bigger than, equal to, or by one smaller than the length of the previous step.
What is the minimum number of steps in order to get from x to y? The length of the first and the last step must be 1.

Input and Output

Input consists of a line containing n, the number of test cases. For each test case, a line follows with two integers: 0 $\le$ x $\le$ y < 2³¹. For each test case, print a line giving the minimum number of steps to get from x to y.

Sample Input

Sample Output

3
3
4

Miguel Revilla 2002-06-15

Problem Links:

uva10077,

Problem:

The Stern-Brocot Number System

Input: standard input

Output: standard output

The Stern-Brocot tree is a beautiful way for constructing the set of all nonnegative fractions m / n where m and n are relatively prime. The idea is to start with two fractions

and then repeat the following operations as many times as desired:

Insert

between two adjacent fractions

and

For example, the first step gives us one new entry between

and

and the next gives two more:

The next gives four more,

and then we will get 8, 16, and so on. The entire array can be regarded as an infinite binary tree structure whose top levels look like this:

The construction preserves order, and we couldn't possibly get the same fraction in two different places.

We can, in fact, regard the Stern-Brocot tree as a number system for representing rational numbers, because each positive, reduced fraction occurs exactly once. Let's use the letters L and R to stand for going down to the left or right branch as we proceed from the root of the tree to a particular fraction; then a string of L's and R's uniquely identifies a place in the tree. For example, LRRL means that we go left from

down to

, then right to

, then left to

. We can consider LRRL to be a representation of

. Every positive fraction gets represented in this way as a unique string of L's and R's.

Well, actually there's a slight problem: The fraction

corresponds to the empty string, and we need a notation for that. Let's agree to call it I, because that looks something like 1 and it stands for "identity".

In this problem, given a positive rational fraction, you are expected to represent it in Stern-Brocot number system.

Input

The input file contains multiple test cases. Each test case consists of a line contains two positive integers m and n where m and n are relatively prime. The input terminates with a test case containing two 1's for m and n, and this case must not be processed.

Output

For each test case in the input file output a line containing the representation of the given fraction in the Stern-Brocot number system.

Sample Input

5 7
878 323
1 1

Sample Output

LRRL
RRLRRLRLLLLRLRRR
______________________________________________________________________________________
Rezaul Alam Chowdhury

UVa_10049_Self-describing_Sequence.cpp

Problem Links:

uva10049,

Problem:

Problem C: Selfdescribing Sequence

Solomon Golomb's selfdescribing sequence $\langle f(1), f(2), f(3), \dots \rangle$ is the only nondecreasing sequence of positive integers with the property that it contains exactly f(k) occurrences of k for each k. A few moments thought reveals that the sequence must begin as follows:

$\begin{displaymath}\begin{array}{c\vert cccccccccccc} \mbox{\boldmath $n$} & 1 &... ...)$} & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 4 & 5 & 5 & 5 & 6 \end{array}\end{displaymath}$

In this problem you are expected to write a program that calculates the value of f(n) given the value of n.

Input

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n ( $1 \le n \le 2,000,000,000$ ). The input terminates with a test case containing a value 0 for n and this case must not be processed.

Output

For each test case in the input output the value of f(n) on a separate line.

Sample Input

Sample Output

Miguel Revilla
2000-12-26

Problem Links:

uva10198,

Problem:

Problem E: Counting

The Problem

Gustavo knows how to count, but he is now learning how write numbers. As he is a very good student, he already learned 1, 2, 3 and 4. But he didn't realize yet that 4 is different than 1, so he thinks that 4 is another way to write 1. Besides that, he is having fun with a little game he created himself: he make numbers (with those four digits) and sum their values. For instance:

132 = 1 + 3 + 2 = 6
112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4 = 1)

After making a lot of numbers in this way, Gustavo now wants to know how much numbers he can create such that their sum is a number n. For instance, for n = 2 he noticed that he can make 5 numbers: 11, 14, 41, 44 and 2 (he knows how to count them up, but he doesn't know how to write five). However, he can't figure it out for n greater than 2. So, he asked you to help him.

The Input

Input will consist on an arbitrary number of sets. Each set will consist on an integer n such that 1 <= n <= 1000. You must read until you reach the end of file.

The Output

For each number read, you must output another number (on a line alone) stating how much numbers Gustavo can make such that the sum of their digits is equal to the given number.

Sample Input

2
3

Sample Output

5
13

UVa_00847_A_Multiplication_Game.cpp

Problem Links:

poj2505, uva00847,

Problem:

A multiplication game

Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches p $\ge$ n.

Input and Output

Each line of input contains one integer number n. For each line of input output one line either

Stan wins.

Ollie wins.

assuming that both of them play perfectly.

Sample input

162
17
34012226

Sample Output

Stan wins.
Ollie wins.
Stan wins.

Miguel Revilla 2002-06-15

Problem Links:

poj2551, uva10127,

Problem:

Problem E - Ones

Given any integer 0 <= n <= 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1's. How many digits are in the smallest such a multiple of n?

Sample input

3 
7 
9901

Output for sample input

3
6
12

UVa_00701_The_Archeologists'_Dilemma.cpp

Problem Links:

uva00701,

Problem:

The Archeologists' Dilemma

An archeologist seeking proof of the presence of extraterrestrials in the Earth's past, stumbles upon a partially destroyed wall containing strange chains of numbers. The left-hand part of these lines of digits is always intact, but unfortunately the right-hand one is often lost by erosion of the stone. However, she notices that all the numbers with all its digits intact are powers of 2, so that the hypothesis that all of them are powers of 2 is obvious. To reinforce her belief, she selects a list of numbers on which it is apparent that the number of legible digits is strictly smaller than the number of lost ones, and asks you to find the smallest power of 2 (if any) whose first digits coincide with those of the list.
Thus you must write a program such that given an integer, it determines (if it exists) the smallest exponent E such that the first digits of 2^E coincide with the integer (remember that more than half of the digits are missing).

Input

It is a set of lines with a positive integer N not bigger than 2147483648 in each of them.

Output

For every one of these integers a line containing the smallest positive integer E such that the first digits of 2^E are precisely the digits of N, or, if there is no one, the sentence ``no power of 2".

Sample Input

1
2
10

UVa_10018_Reverse_and_Add.cpp

Problem Links:

spoj4770, uva10018,

Problem:

Reverse and Add

The Problem

The "reverse and add" method is simple: choose a number, reverse its digits and add it to the original. If the sum is not a palindrome (which means, it is not the same number from left to right and right to left), repeat this procedure. For example:
195 Initial number
591
-----
786
687
-----
1473
3741
-----
5214
4125
-----
9339 Resulting palindrome
In this particular case the palindrome 9339 appeared after the 4th addition. This method leads to palindromes in a few step for almost all of the integers. But there are interesting exceptions. 196 is the first number for which no palindrome has been found. It is not proven though, that there is no such a palindrome.
Task :
You must write a program that give the resulting palindrome and the number of iterations (additions) to compute the palindrome.
You might assume that all tests data on this problem:
- will have an answer ,
- will be computable with less than 1000 iterations (additions),
- will yield a palindrome that is not greater than 4,294,967,295.

The Input

The first line will have a number N with the number of test cases, the next N lines will have a number P to compute its palindrome.

The Output

For each of the N tests you will have to write a line with the following data : minimum number of iterations (additions) to get to the palindrome and the resulting palindrome itself separated by one space.

Sample Input

Sample Output

4 9339
5 45254
3 6666

Problem Links:

poj2562, uva10035,

Problem:

Problem B: Primary Arithmetic

Children are taught to add multi-digit numbers from right-to-left one digit at a time. Many find the "carry" operation - in which a 1 is carried from one digit position to be added 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 you should compute and print the number of carry operations that would result from adding the two numbers, in the format shown below.

Sample Input

Sample Output

No carry operation.
3 carry operations.
1 carry operation.

Problem Links:

uva10152,

Problem:

Problem D: ShellSort

He made each turtle stand on another one's back
And he piled them all up in a nine-turtle stack.
And then Yertle climbed up. He sat down on the pile.
What a wonderful view! He could see 'most a mile!

The Problem

King Yertle wishes to rearrange his turtle throne to place his highest-ranking nobles and closest advisors nearer to the top. A single operation is available to change the order of the turtles in the stack: a turtle can crawl out of its position in the stack and climb up over the other turtles to sit on the top.
Given an original ordering of a turtle stack and a required ordering for the same turtle stack, your job is to determine a minimal sequence of operations that rearranges the original stack into the required stack.
The first line of the input consists of a single integer K giving the number of test cases. Each test case consist on an integer n giving the number of turtles in the stack. The next n lines specify the original ordering of the turtle stack. Each of the lines contains the name of a turtle, starting with the turtle on the top of the stack and working down to the turtle at the bottom of the stack. Turtles have unique names, each of which is a string of no more than eighty characters drawn from a character set consisting of the alphanumeric characters, the space character and the period (`.'). The next n lines in the input gives the desired ordering of the stack, once again by naming turtles from top to bottom. Each test case consists of exactly 2n+1 lines in total. The number of turtles (n) will be less than or equal to two hundred.
For each test case, the output consists of a sequence of turtle names, one per line, indicating the order in which turtles are to leave their positions in the stack and crawl to the top. This sequence of operations should transform the original stack into the required stack and should be as short as possible. If more than one solution of shortest length is possible, any of the solutions may be reported. Print a blank line after each test case.

Sample Input

2
3
Yertle
Duke of Earl
Sir Lancelot
Duke of Earl
Yertle
Sir Lancelot
9
Yertle
Duke of Earl
Sir Lancelot
Elizabeth Windsor
Michael Eisner
Richard M. Nixon
Mr. Rogers
Ford Perfect
Mack
Yertle
Richard M. Nixon
Sir Lancelot
Duke of Earl
Elizabeth Windsor
Michael Eisner
Mr. Rogers
Ford Perfect
Mack

Sample Output

Duke of Earl

Sir Lancelot
Richard M. Nixon
Yertle

Problem Links:

poj, uva10026,

Problem:

Shoemaker's Problem

Shoemaker has N jobs (orders from customers) which he must make. Shoemaker can work on only one job in each day. For each i_th job, it is known the integer T_i (1<=T_i<=1000), the time in days it takes the shoemaker to finish the job. For each day of delay before starting to work for the i_th job, shoemaker must pay a fine of S_i (1<=S_i<=10000) cents. Your task is to help the shoemaker, writing a programm to find the sequence of jobs with minimal total fine.

The Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

First line of input contains an integer N (1<=N<=1000). The next N lines each contain two numbers: the time and fine of each task in order.

The Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

You programm should print the sequence of jobs with minimal fine. Each job should be represented by its number in input. All integers should be placed on only one output line and separated by one space. If multiple solutions are possible, print the first lexicographically.

Sample Input

Sample Output

2 1 3 4

Alex Gevak
September 16, 2000(Revised 4-10-00, Antonio Sanchez)

Codeforces Beta Round #62

Mar 18, 2011.
Accepted: 0. WA: 2. NotTried: 3.

Tutorial

Problem 1:

Solution:

Naive method: Go through all of the permutations and then check the condition. O(24 * n), n is the number of elements.

Advanced method: After checking on the condition, if i-th element is smaller than those four integer, then this number will satisfy any permutation.

The reason I got WA is: I didn't sort the p before I start using the next_permuation function.

Source Code:

//Friday, March  18, 2011 10:41 CDT
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char* argv[])
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    vector<int> p(4, 0);
    int a, b;
    cin >> p[0] >> p[1] >> p[2] >> p[3] >> a >> b;
    vector<int> pickup(b - a + 1, 0);
    sort(p.begin(), p.end());
    do
    {
        for (int i = a; i <= b; i++)
        {
            if (i == i % p[0] % p[1] % p[2] % p[3])
            {
                pickup[i - a]++;
            }
        }
    }
    while (next_permutation(p.begin(), p.end()));
    int count = 0;
    for (int i = 0; i < pickup.size(); i++)
        if (pickup[i] >= 7)
            count++;
    cout << count << endl;
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Problem Links:

uva10191,

Problem:

Problem D: Longest Nap

The Problem

As you may already know, there are professors very busy with a filled schedule of work during the day. Your professor, let's call him Professor P, is a bit lazy and wants to take a nap during the day, but as his schedule is very busy, he doesn't have a lot of chances of doing this. He would REALLY like, however, to take one nap every day. Because he'll take just one nap, he wants to take the longest nap that it's possible given his schedule. He decided to write a program to help him in this task but, as we said, Professor P is very lazy. So, he finally decided that YOU must write the program!

The Input

The input will consist on an arbitrary number of test cases, each test case represents one day. The first line of each set contains a positive integer s (not greater than 100) representing the number of scheduled appointments during that day. In the next s lines there are the appointments in the following format:

time1 time2 appointment

Where time1 represents the time which the appointment starts and time2 the time it ends. All times will be in the hh:mm format, time1 will always be strictly less than time2, they will be separated by a single space and all times will be greater than or equal to 10:00 and less than or equal to 18:00. So, your response must be in this interval as well (i.e. no nap can start before 10:00 and last after 18:00). The appointment can be any sequence of characters, but will always be in the same line. You can assume that no line will be longer than 255 characters, that 10 <= hh <= 18 and that 0 <= mm < 60. You CAN'T assume, however, that the input will be in any specific order. You must read the input until you reach the end of file.

The Output

For each test case, you must print the following line:

Day #d: the longest nap starts at hh:mm and will last for [H hours and] M minutes.

Where d stands for the number of the test case (starting from 1) and hh:mm is the time when the nap can start. To display the duration of the nap, follow these simple rules:

if the total duration X in minutes is less than 60, just print "M minutes", where M = X.
if the total duration X in minutes is greater or equal to 60, print "H hours and M minutes", where H = X div 60 (integer division, of course) and M = X mod 60.

Notice that you don't have to worry with concordance (i.e. you must print "1 minutes" or "1 hours" if it's the case). The duration of the nap is calculated by the difference between the ending time free and the begining time free. That is, if an appointment ends at 14:00 and the next one starts at 14:47, then you have (14:47)-(14:00) = 47 minutes of possible nap. If there is more than one longest nap with the same duration, print the earliest one. You can assume that there won't be a day all busy (i.e. you may assume that there will be at least one possible nap).

Sample Input

4
10:00 12:00 Lectures
12:00 13:00 Lunch, like always.
13:00 15:00 Boring lectures...
15:30 17:45 Reading
4
10:00 12:00 Lectures
12:00 13:00 Lunch, just lunch.
13:00 15:00 Lectures, lectures... oh, no!
16:45 17:45 Reading (to be or not to be?)
4
10:00 12:00 Lectures, as everyday.
12:00 13:00 Lunch, again!!!
13:00 15:00 Lectures, more lectures!
15:30 17:15 Reading (I love reading, but should I schedule it?)
1
12:00 13:00 I love lunch! Have you ever noticed it? :)

Sample Output

Day #1: the longest nap starts at 15:00 and will last for 30 minutes.
Day #2: the longest nap starts at 15:00 and will last for 1 hours and 45 minutes.
Day #3: the longest nap starts at 17:15 and will last for 45 minutes.
Day #4: the longest nap starts at 13:00 and will last for 5 hours and 0 minutes.

UVa_10037_Bridge.cpp

Problem Links:

poj2573, uva10037, spoj06734(not passed),

Problem:

Problem D: Bridge

n people wish to cross a bridge at night. A group of at most two people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people, so some sort of shuttle arrangement must be arranged in order to return the flashlight so that more people may cross. Each person has a different crossing speed; the speed of a group is determined by the speed of the slower member. Your job is to determine a strategy that gets all n people across the bridge in the minimum time.

Input

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The first line of output must contain the total number of seconds required for all n people to cross the bridge. The following lines give a strategy for achieving this time. Each line contains either one or two integers, indicating which person or people form the next group to cross. (Each person is indicated by the crossing time specified in the input. Although many people may have the same crossing time the ambiguity is of no consequence.) Note that the crossings alternate directions, as it is necessary to return the flashlight so that more may cross. If more than one strategy yields the minimal time, any one will do.

Sample Input

Sample Output

Problem Links:

uva00120,

Problem:

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).

The 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.

The 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

Problem Links:

uva10041,

Problem:

Problem C: Vito's family

Background

The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them.

Problem

Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.

Input

The input consists of several test cases. The first line contains the number of test cases. For each test case you will be given the integer number of relatives r ( 0 < r < 500) and the street numbers (also integers) $s_1, s_2, \ldots, s_i, \ldots, s_r$ where they live ( 0 < s_i < 30000 ). Note that several relatives could live in the same street number.

Output

For each test case your program must write the minimal sum of distances from the optimal Vito's house to each one of his relatives. The distance between two street numbers s_i and s_j is d_ij= |s_i-s_j|.

Sample Input

2
2 2 4 
3 2 4 6

Sample Output

2
4

Miguel Revilla
2000-11-19

Problem Links:

uva10132,

Problem:

Question 2: File Fragmentation

The Problem

Your friend, a biochemistry major, tripped while carrying a tray of computer files through the lab. All of the files fell to the ground and broke. Your friend picked up all the file fragments and called you to ask for help putting them back together again.
Fortunately, all of the files on the tray were identical, all of them broke into exactly two fragments, and all of the file fragments were found. Unfortunately, the files didn't all break in the same place, and the fragments were completely mixed up by their fall to the floor.
You've translated the original binary fragments into strings of ASCII 1's and 0's, and you're planning to write a program to determine the bit pattern the files contained.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Input will consist of a sequence of ``file fragments'', one per line, terminated by the end-of-file marker. Each fragment consists of a string of ASCII 1's and 0's.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Output is a single line of ASCII 1's and 0's giving the bit pattern of the original files. If there are 2N fragments in the input, it should be possible to concatenate these fragments together in pairs to make N copies of the output string. If there is no unique solution, any of the possible solutions may be output.
Your friend is certain that there were no more than 144 files on the tray, and that the files were all less than 256 bytes in size.

Sample Input

Sample Output

01110111

UVa_10252_Common_Permutation.cpp

Problem Links:

poj2629, uva10252,

Problem:

Problem G

Common Permutation

Input: standard input

Output: standard output

Time Limit: 4 seconds

Memory Limit: 32 MB

Given two strings of lowercase letters, a and b, print the longest string x of lowercase 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

Input file contains several lines of input. Consecutive two lines make a set of input. That means in the input file line 1 and 2 is a set of input, line 3 and 4 is a set of input and so on. The first line of a pair contains a and the second contains b. Each string is on a separate line and consists of at most 1000 lowercase letters.

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.

Sample Input:

pretty

women

walking

down

the

street

Sample Output:

(World Finals Warm-up Contest, Problem Source: University of Alberta Local Contest)

Problem Links:

uva10010,

Problem:

Where's Waldorf?

Given a m by n grid of letters, ( $1 \leq m,n \leq 20$ ), and a list of words, find the location in the grid at which the word can be found. A word matches a straight, uninterrupted line of letters in the grid. A word can match the letters in the grid regardless of case (i.e. upper and lower case letters are to be treated as the same). The matching can be done in any of the eight directions either horizontally, vertically or diagonally through the grid.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input begins with a pair of integers, m followed by n, $1 \leq m,n \leq 50$ in decimal notation on a single line. The next m lines contain n letters each; this is the grid of letters in which the words of the list must be found. The letters in the grid may be in upper or lower case. Following the grid of letters, another integer k appears on a line by itself ( $1 \leq k \leq 20$ ). The next k lines of input contain the list of words to search for, one word per line. These words may contain upper and lower case letters only (no spaces, hyphens or other non-alphabetic characters).

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
For each word in the word list, a pair of integers representing the location of the corresponding word in the grid must be output. The integers must be separated by a single space. The first integer is the line in the grid where the first letter of the given word can be found (1 represents the topmost line in the grid, and m represents the bottommost line). The second integer is the column in the grid where the first letter of the given word can be found (1 represents the leftmost column in the grid, and n represents the rightmost column in the grid). If a word can be found more than once in the grid, then the location which is output should correspond to the uppermost occurence of the word (i.e. the occurence which places the first letter of the word closest to the top of the grid). If two or more words are uppermost, the output should correspond to the leftmost of these occurences. All words can be found at least once in the grid.

Sample Input

1

8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
4
Waldorf
Bambi
Betty
Dagbert

Problem Links:

poj2538, uva10082,

Problem:

Problem C: WERTYU

A common typing error is to place the hands on the keyboard one row to the right of the correct position. So "Q" is typed as "W" and "J" is typed as "K" and so on. You are to decode a message typed in this manner.
Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above [except back-quote (`)]. Keys labelled with words [Tab, BackSp, Control, etc.] are not represented in the input. You are to replace each letter or punction symbol by the one immediately to its left on the QWERTY keyboard shown above. Spaces in the input should be echoed in the output.

Sample Input

O S, GOMR YPFSU/

Output for Sample Input

I AM FINE TODAY.

UVa_10258_Contest_Scoreboard.cpp

Problem Links:

uva10258,

Problem:

Question B - Contest Scoreboard

Think the contest score boards are wrong? Here's your chance to come up with the right rankings.
Contestants are ranked first by the number of problems solved (the more the better), then by decreasing amounts of penalty time. If two or more contestants are tied in both problems solved and penalty time, they are displayed in order of increasing team numbers. A problem is considered solved by a contestant if any of the submissions for that problem was judged correct. Penalty time is computed as the number of minutes it took for the first correct submission for a problem to be received plus 20 minutes for each incorrect submission received prior to the correct solution. Unsolved problems incur no time penalties.

Input:

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Input consists of a snapshot of the judging queue, containing entries from some or all of contestants 1 through 100 solving problems 1 through 9. Each line of input will consist of three numbers and a letter in the format
contestant problem time L
where L can be C, I, R, U or E. These stand for Correct, Incorrect, clarification Request, Unjudged and Erroneous submission. The last three cases do not affect scoring.
Lines of input are in the order in which submissions were received.

Output:

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Output will consist of a scoreboard sorted as previously described. Each line of output will contain a contestant number, the number of problems solved by the contestant and the time penalty accumulated by the contestant. Since not all of contestants 1-100 are actually participating, display only the contestants that have made a submission.

Sample Input:

Sample Output:

1 2 66
3 1 11

UVa_10205_Stack_\'em_Up.cpp

Problem Links:

poj2469, uva10205,

Problem:

Problem E: Stack 'em Up

A standard playing card deck contains 52 cards, 13 values in each of four suits. The values are named 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace. The suits are named Clubs, Diamonds, Hearts, Spades. A particular card in the deck can be uniquely identified by its value and suit, typically denoted of . For example, "9 of Hearts" or "King of Spades". Traditionally a new deck is ordered first alphabetically by suit, then by value in the order given above. The Big City has many Casinos. In one such casino the dealer is a bit crooked. She has perfected several shuffles; each shuffle rearranges the cards in exactly the same way whenever it is used. A very simple example is the "bottom card" shuffle which removes the bottom card and places it at the top. By using various combinations of these known shuffles, the crooked dealer can arrange to stack the cards in just about any particular order.
You have been retained by the security manager to track this dealer. You are given a list of all the shuffles performed by the dealer, along with visual cues that allow you to determine which shuffle she uses at any particular time. Your job is to predict the order of the cards after a sequence of shuffles.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
Input consists of an integer n <= 100, the number of shuffles that the dealer knows. 52n integers follow. Each consecutive 52 integers will comprise all the integers from 1 to 52 in some order. Within each set of 52 integers, i in position j means that the shuffle moves the i^th card in the deck to position j.
Several lines follow; each containing an integer k between 1 and n indicating that you have observed the dealer applying the k^th shuffle given in the input.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Assume the dealer starts with a new deck ordered as described above. After all the shuffles had been performed, give the names of the cards in the deck, in the new order.

Sample Input

1

2
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 52 51
52 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 1
1
2

Output for Sample Input

King of Spades
2 of Clubs
4 of Clubs
5 of Clubs
6 of Clubs
7 of Clubs
8 of Clubs
9 of Clubs
10 of Clubs
Jack of Clubs
Queen of Clubs
King of Clubs
Ace of Clubs
2 of Diamonds
3 of Diamonds
4 of Diamonds
5 of Diamonds
6 of Diamonds
7 of Diamonds
8 of Diamonds
9 of Diamonds
10 of Diamonds
Jack of Diamonds
Queen of Diamonds
King of Diamonds
Ace of Diamonds
2 of Hearts
3 of Hearts
4 of Hearts
5 of Hearts
6 of Hearts
7 of Hearts
8 of Hearts
9 of Hearts
10 of Hearts
Jack of Hearts
Queen of Hearts
King of Hearts
Ace of Hearts
2 of Spades
3 of Spades
4 of Spades
5 of Spades
6 of Spades
7 of Spades
8 of Spades
9 of Spades
10 of Spades
Jack of Spades
Queen of Spades
Ace of Spades
3 of Clubs

Problem Links:

uva10050,

Problem:

Problem D: Hartals

A social research organization has determined a simple set of parameters to simulate the behavior of the political parties of our country. One of the parameters is a positive integer h (called the hartal parameter) that denotes the average number of days between two successive hartals (strikes) called by the corresponding party. Though the parameter is far too simple to be flawless, it can still be used to forecast the damages caused by hartals. The following example will give you a clear idea:

Consider three political parties. Assume h₁ = 3, h₂ = 4 and h₃ = 8 where h_i is the hartal parameter for party i ( i = 1, 2, 3). Now, we will simulate the behavior of these three parties for N = 14 days. One must always start the simulation on a Sunday and assume that there will be no hartals on weekly holidays (on Fridays and Saturdays).

	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Days
	Su	Mo	Tu	We	Th	Fr	Sa	Su	Mo	Tu	We	Th	Fr	Sa
Party 1			x			x			x			x
Party 2				x				x				x
Party 3								x
Hartals			1	2				3	4			5

The simulation above shows that there will be exactly 5 hartals (on days 3, 4, 8, 9 and 12) in 14 days. There will be no hartal on day 6 since it is a Friday. Hence we lose 5 working days in 2 weeks.
In this problem, given the hartal parameters for several political parties and the value of N, your job is to determine the number of working days we lose in those N days.

Input

The first line of the input consists of a single integer T giving the number of test cases to follow.
The first line of each test case contains an integer N ( $7 \le N \le 3650$ ) giving the number of days over which the simulation must be run. The next line contains another integer P ( $1 \le P \le 100$ ) representing the number of political parties in this case. The ith of the next P lines contains a positive integer h_i (which will never be a multiple of 7) giving the hartal parameter for party i ( $1 \le i \le P$ ).

Output

For each test case in the input output the number of working days we lose. Each output must be on a separate line.

Sample Input

Sample Output

5
15

Miguel Revilla
2000-12-26

Problem Links:

uva10315,

Problem:

Problem D

Poker Hands

Input: standard input

Output: standard output

Time Limit: 2 seconds

Memory Limit: 32 MB

A poker deck contains 52 cards - each card has a suit which is one of clubs, diamonds, hearts, or spades (denoted C, D, H, and S in the input data). Each card also has a value which is one of 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, king, ace (denoted 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, A). For scoring purposes, the suits are unordered while the values are ordered as given above, with 2 being the lowest and ace the highest value.

A poker hand consists of 5 cards dealt from the deck. Poker hands are ranked by the following partial order from lowest to highest

High Card: Hands which do not fit any higher category are ranked by the value of their highest card. If the highest cards have the same value, the hands are ranked by the next highest, and so on.
Pair: 2 of the 5 cards in the hand have the same value. Hands which both contain a pair are ranked by the value of the cards forming the pair. If these values are the same, the hands are ranked by the values of the cards not forming the pair, in decreasing order.
Two Pairs: The hand contains 2 different pairs. Hands which both contain 2 pairs are ranked by the value of their highest pair. Hands with the same highest pair are ranked by the value of their other pair. If these values are the same the hands are ranked by the value of the remaining card.
Three of a Kind: Three of the cards in the hand have the same value. Hands which both contain three of a kind are ranked by the value of the 3 cards.
Straight: Hand contains 5 cards with consecutive values. Hands which both contain a straight are ranked by their highest card.
Flush: Hand contains 5 cards of the same suit. Hands which are both flushes are ranked using the rules for High Card.
Full House: 3 cards of the same value, with the remaining 2 cards forming a pair. Ranked by the value of the 3 cards.
Four of a kind: 4 cards with the same value. Ranked by the value of the 4 cards.
Straight flush: 5 cards of the same suit with consecutive values. Ranked by the highest card in the hand.

Your job is to compare several pairs of poker hands and to indicate which, if either, has a higher rank.

Input

The input file contains several lines, each containing the designation of 10 cards: the first 5 cards are the hand for the player named "Black" and the next 5 cards are the hand for the player named "White".

Output

For each line of input, print a line containing one of the following three lines:

   Black wins.

   White wins.

   Tie.

Sample Input

2H 3D 5S 9C KD 2C 3H 4S 8C AH

2H 4S 4C 2D 4H 2S 8S AS QS 3S

2H 3D 5S 9C KD 2C 3H 4S 8C KH

2H 3D 5S 9C KD 2D 3H 5C 9S KH

Sample Output

White wins.

Black wins.

Black wins.

Tie.

(The Decider Contest, Source: Waterloo ACM Programming Contest)

UVa_10038_Jolly_Jumpers.cpp

Problem Links:

poj2575, uva10038,

Problem:

Problem E: Jolly Jumpers

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,

1 4 2 3

is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.

Input

Each line of input contains an integer n <= 3000 followed by n integers representing the sequence.

Output

For each line of input, generate a line of output saying "Jolly" or "Not jolly".

Sample Input

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly
Not jolly

poj_1269_Intersecting_Lines.cpp

Problem Links:

poj1269, uva00378,

Problem:

Intersecting Lines

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 4630		Accepted: 2223

Description

We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect.

Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000.

Input

The first line contains an integer N between 1 and 10 describing how many pairs of lines are represented. The next N lines will each contain eight integers. These integers represent the coordinates of four points on the plane in the order x1y1x2y2x3y3x4y4. Thus each of these input lines represents two lines on the plane: the line through (x1,y1) and (x2,y2) and the line through (x3,y3) and (x4,y4). The point (x1,y1) is always distinct from (x2,y2). Likewise with (x3,y3) and (x4,y4).

Output

There should be N+2 lines of output. The first line of output should read INTERSECTING LINES OUTPUT. There will then be one line of output for each pair of planar lines represented by a line of input, describing how the lines intersect: none, line, or point. If the intersection is a point then your program should output the x and y coordinates of the point, correct to two decimal places. The final line of output should read "END OF OUTPUT".

poj_1528_Perfection.cpp

Problem Links:

poj1528, uva00382,

Problem:

Perfection

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 7728		Accepted: 3713

Description

From the article Number Theory in the 1994 Microsoft Encarta: ``If a, b, c are integers such that a = bc, a is called a multiple of b or of c, and b or c is called a divisor or factor of a. If c is not 1/-1, b is called a proper divisor of a. Even integers, which include 0, are multiples of 2, for example, -4, 0, 2, 10; an odd integer is an integer that is not even, for example, -5, 1, 3, 9. A perfect number is a positive integer that is equal to the sum of all its positive, proper divisors; for example, 6, which equals 1 + 2 + 3, and 28, which equals 1 + 2 + 4 + 7 + 14, are perfect numbers. A positive number that is not perfect is imperfect and is deficient or abundant according to whether the sum of its positive, proper divisors is smaller or larger than the number itself. Thus, 9, with proper divisors 1, 3, is deficient; 12, with proper divisors 1, 2, 3, 4, 6, is abundant."
Given a number, determine if it is perfect, abundant, or deficient.

Input

A list of N positive integers (none greater than 60,000), with 1 <= N < 100. A 0 will mark the end of the list.

Output

The first line of output should read PERFECTION OUTPUT. The next N lines of output should list for each input integer whether it is perfect, deficient, or abundant, as shown in the example below. Format counts: the echoed integers should be right justified within the first 5 spaces of the output line, followed by two blank spaces, followed by the description of the integer. The final line of output should read END OF OUTPUT.

Sample Input

15 28 6 56 60000 22 496 0

Sample Output

PERFECTION OUTPUT
   15  DEFICIENT
   28  PERFECT
    6  PERFECT
   56  ABUNDANT
60000  ABUNDANT
   22  DEFICIENT
  496  PERFECT
END OF OUTPUT

Source

Mid-Atlantic 1996

Problem Links:

poj1552,

Problem:

Doubles

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 13940		Accepted: 7824

Description

As part of an arithmetic competency program, your students will be given randomly generated lists of from 2 to 15 unique positive integers and asked to determine how many items in each list are twice some other item in the same list. You will need a program to help you with the grading. This program should be able to scan the lists and output the correct answer for each one. For example, given the list

1 4 3 2 9 7 18 22

Codeforces Beta Round #61 (Div 2)

Mar 7, 2011.
Accepted: 3.        WA: 1.        NotTried: 1.

Tutorial

Problem 1: Petya and Java.
AC: This problem is mainly to determine which data type should be used based on the given integer. The redirect of operation is very useful here.
Time: O(1).
Source Code:
//Monday, March  07, 2011 09:15 CST
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

bool operator < (const string &a, const string &b)
{
    if (a.size() < b.size()) return true;
    if (b.size() < a.size()) return false;

    //They have the same number of digits.
    for (int i = 0;i < a.size();i++)
    {
        if (a[i] < b[i]) return true;
        if (b[i] < a[i]) return false;
    }
    return true; //a could be less or equal to b.
}

string solve(string n)
{
    string b = "127";
    string s = "32767";
    string i = "2147483647";
    string l = "9223372036854775807";

    if(n < b) return "byte";
    if(n < s) return "short";
    if(n < i) return "int";
    if(n < l) return "long";
    return "BigInteger";
}

int main(int argc, char* argv[])
{
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}

Codeforces Beta Round #59 (Div 2)

Mar 1, 2011.
Accepted: 3.        WA: 0.        NotTried: 2.

Tutorial

Problem 1: Sinking Ship.
AC: This problem is mainly about the sort algorithm, but the comparative function is determined by its character on the ship. Use the trick of data structure in STL. The pair structure will be sorted by the first index, then the second index.
Time: O(n^2), which depends on the sort function.
Source Code:
//Mon Feb 28 21:59:55 CST 2011
int main(int argc, char* argv[]) {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int number;
    while (cin >> number) {
        string a, b;
        vector<pair<int, pair<int, string> > > mp;
        for (int i = 0; i < number; i++) {
            cin >> a >> b;
            if (b == "rat") {
                mp.push_back(make_pair(0, make_pair(i, a)));
            } else if (b == "child" || b == "woman") {
                mp.push_back(make_pair(1, make_pair(i, a)));
            } else if (b == "captain") {
                mp.push_back(make_pair(4, make_pair(i, a)));
            } else {
                mp.push_back(make_pair(3, make_pair(i, a)));
            }
        }
        sort(mp.begin(), mp.end());
        for (int i = 0; i < number; i++) {
            cout << mp[i].second.second << endl;
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
******************************************************************************************

UVa_10137_The_Trip.cpp

Problem Links:

poj2646, uva10137,

Problem:

Problem A: The Trip

A number of students are members of a club that travels annually to exotic locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven.The group agrees in advance to share expenses equally, but it is not practical to have them share every expense as it occurs. So individuals in the group pay for particular things, like meals, hotels, taxi rides, plane tickets, etc. After the trip, each student's expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within a cent) all the students' costs.

Problem Links:

poj2663, uva10918, spoj3883, hit2124,

Problem:

Tri Tiling

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5244		Accepted: 2794

Description

In how many ways can you tile a 3xn rectangle with 2x1 dominoes?

Here is a sample tiling of a 3x12 rectangle.

Problem Links:

poj2612,

Problem:

Mine Sweeper

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5122		Accepted: 2008

Description

The game Minesweeper is played on an n by n grid. In this grid are hidden mines, each at a distinct grid location. The player repeatedly touches grid positions. If a position with a mine is touched, the mine explodes and the player loses. If a positon not containing a mine is touched, an integer between 0 and 8 appears denoting the number of adjacent or diagonally adjacent grid positions that contain a mine. A sequence of moves in a partially played game is illustrated below.

Here, n is 8, m is 10, blank squares represent the integer 0, raised squares represent unplayed positions, and the figures resembling asterisks represent mines. The leftmost image represents the partially played game. From the first image to the second, the player has played two moves, each time choosing a safe grid position. From the second image to the third, the player is not so lucky; he chooses a position with a mine and therefore loses. The player wins if he continues to make safe moves until only m unplayed positions remain; these must necessarily contain the mines. Your job is to read the information for a partially played game and to print the corresponding board.

UVa_10189_Minesweeper.cpp

Problem Links:

uva10189,

Problem:

Problem B: Minesweeper

The Problem

Have you ever played Minesweeper? It's a cute little game which comes within a certain Operating System which name we can't really remember. Well, the goal of the game is to find where are all the mines within a MxN field. To help you, the game shows a number in a square which tells you how many mines there are adjacent to that square. For instance, supose the following 4x4 field with 2 mines (which are represented by an * character):

*...
....
.*..
....

If we would represent the same field placing the hint numbers described above, we would end up with:

As you may have already noticed, each square may have at most 8 adjacent squares.

Subscribe to: Posts ( Atom )

Pages

Thursday, March 31, 2011

Problem Links:

Problem:

Steps

Input and Output

Sample Input

Sample Output

Problem Links:

Problem:

Wednesday, March 30, 2011

Problem Links:

Problem:

Problem C: Self­describing Sequence

Input

Output

Sample Input

Sample Output

Problem Links:

Problem:

Problem E: Counting

The Problem

The Input

The Output

Sample Input

Sample Output

Friday, March 25, 2011

Problem Links:

Problem:

A multiplication game

Input and Output

Sample input

Sample Output

Problem Links:

Problem:

Problem E - Ones

Sample input

Output for sample input

Thursday, March 24, 2011

Problem Links:

Problem:

The Archeologists' Dilemma

Input

Output

Sample Input

Friday, March 18, 2011

Problem Links:

Problem:

The Problem

The Input

The Output

Sample Input

Sample Output

Problem Links:

Problem:

Problem B: Primary Arithmetic

Input

Output

Sample Input

Sample Output

Problem Links:

Problem:

Problem D: ShellSort

The Problem

Sample Input

Sample Output

Problem Links:

Problem:

Tutorial

Problem 1:

Solution:

Source Code:

Problem Links:

Problem:

Problem D: Longest Nap

The Problem

The Input

The Output

Sample Input

Sample Output

Problem C: Selfdescribing Sequence