Saturday, June 27, 2009

71. Asked in Hello World(Algorythm '09)

Problem  - Sum of Consecutive Prime Numbers
--------------------------------------------

Some positive integers can be represented by a sum of one or more
consecutive prime numbers. How many such representations does a given
positive integer have? For example, the integer 53 has two
representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three
representations 2 + 3 + 5 + 7 + 11 + 13, 11 + 13 + 17, and 41. The
integer 3 has only one representation, which is 3. The integer 20 has no
such representations. Note that the summands must be consecutive prime
numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation
for the integer 20.

Your mission is to write a program that reports the number of
representations for the given positive integer.

Input
-----

The input is a sequence of positive integers each in a separate line.
The integers are between 2 and 10000, inclusive. The end of the input
is indicated by a zero.

Output
------

The output should be composed of lines each corresponding to an input
line except the last zero. An output line includes the number of
representations for the input integer as the sum of one or more
consecutive prime numbers. No other characters should be inserted in the
output.

Sample Input
------------

2
3
17
41
20
666
12
53
0

Output for Sample Input
-----------------------

1
1
2
3
0
0
1
2

70. Marks Distribution

Marks Distribution

In an examination one student appeared in N subjects and has got total T marks. He has passed in all the N subjects where minimum mark for passing in each subject is P. You have to calculate the number of ways the student can get the marks. For example, if N=3, T=34 and P=10 then the marks in the three subject could be as follows.

	Subject 1	Subject 2	Subject 3
1	14	10	10
2	13	11	10
3	13	10	11
4	12	11	11
5	12	10	12
6	11	11	12
7	11	10	13
8	10	11	13
9	10	10	14
10	11	12	11
11	10	12	12
12	12	12	10
13	10	13	11
14	11	13	10
15	10	14	10

So there are 15 solutions. So F (3, 34, 10) = 15.

Input

In the first line of the input there will be a single positive integer K followed by K lines each containing a single test case. Each test case contains three positive integers denoting N, T and P respectively. The values of N, T and P will be at most 70. You may assume that the final answer will fit in a standard 32-bit integer.

Output

For each input, print in a line the value of F (N, T, P).

Sample Input	Output for Sample Input
2 3 34 10 3 34 10	15 15

69.Tight words

                             Tight words

Given is an alphabet {0, 1, ... , k}, 0 <= k <= 9 . We say that a word of length n over this alphabet is tight if any two neighbour digits in the word do not differ by more than 1.

Input is a sequence of lines, each line contains two integer numbers k and n, 1 <= n <= 100. For each line of input, output the percentage of tight words of length n over the alphabet {0, 1, ... , k} with 5 fractional digits.

Sample input

4 1
2 5
3 5
8 7

Output for the sample input

100.00000
40.74074
17.38281
0.10130

68.Adding Reversed numbers.

Problem - Adding Reversed Numbers 
-----------------------------------

The Antique Comedians of Malidinesia prefer comedies to tragedies.
Unfortunately, most of the ancient plays are tragedies. Therefore the
dramatic advisor of ACM has decided to transfigure some tragedies into
comedies. Obviously, this work is very hard because the basic sense of
the play must be kept intact, although all the things change to their
opposites. For example the numbers: if any number appears in the
tragedy, it must be converted to its reversed form before being accepted
into the comedy play.

Reversed number is a number written in arabic numerals but the order of
digits is reversed. The first digit becomes last and vice versa. For
example, if the main hero had 1245 strawberries in the tragedy, he has
5421 of them now. Note that all the leading zeros are omitted. That
means if the number ends with a zero, the zero is lost by reversing
(e.g. 1200 gives 21). Also note that the reversed number never has any
trailing zeros.

ACM needs to calculate with reversed numbers. Your task is to add two
reversed numbers and output their reversed sum. Of course, the result is
not unique because any particular number is a reversed form of several
numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we
must assume that no zeros were lost by reversing (e.g. assume that the
original number was 12).

Input 
-----

The input consists of N cases. The first line of the input contains only
positive integer N. Then follow the cases. Each case consists of exactly
one line with two positive integers separated by space. These are the
reversed numbers you are to add. Numbers will be at most 200 characters
long.

Output 
------

For each case, print exactly one line containing only one integer - the
reversed sum of two reversed numbers. Omit any leading zeros in the
output.

Sample Input 
------------

3
24 1
4358 754
305 794

Output for Sample Input
-----------------------

34
1998
1

67.Bees

Problem  Bees
---------------

In Africa there is a very special species of bee. Every year, the female
bees of such species give birth to one male bee, while the male bees
give birth to one male bee and one female bee, and then they die!

Now scientists have accidentally found one "magical female bee" of such
special species to the effect that she is immortal, but still able to
give birth once a year as all the other female bees (her descendants are
not immortal however). The scientists would like to know how many bees
there will be after N years. Please write a program that helps them find
the number of male bees and the total number of all bees after N years.

Input
-----

Each line of input contains an integer N >= 0. Input ends with a
case where N = -1. (This case should NOT be processed.)

Output
------

Each line of output should have two numbers, the first one being the
number of male bees after N years, and the second one being the total
number of bees after N years. The two numbers will not exceed 2^30.

Sample Input
------------

1
3
-1

Sample Output
-------------

1 2
4 7

66. COMPLEX NUMBERS

Complex, difficult and complicated
Complex numbers are not only complex, but also complicated. So you would better try to solve another problem...

The Problem

We have a complex number, a + b*i, where i is the square root of -1. We want to make it simple (I mean, real), by raising it to a natural power. For example, complex number 2+2*i, can be made simple by raising it to 4:

(2+2*i)⁴ = -64

You have to compute the smallest natural number, N, (zero is not included) such that (a + b*i)^N is a real number. Besides, we require that the absolute value of (a + b*i)^N is not bigger than 2³⁰.

The Input

The first line of the input contains an integer M, indicating the number of test cases.

For each test case, there is a line with two integers a and b. a is the real part of the complex number, and b is the imaginary part.

The Output

For each test case, the output should consist of a single positive natural number N in one line, indicating the power such that (a + b*i)^N is real and its absolute value is not greater than 2³⁰. If there is no solution, you have to output "TOO COMPLICATED".

Sample Input

Sample Output

1
4
2
TOO COMPLICATED
4

65. Parenthesis Balance

Problem - Parentheses Balance
-------------------------------

You are given a string consisting of parentheses () and []. A string of
this type is said to be correct:

(a) if it is the empty string
(b) if A and B are correct, AB is correct,
(c) if A is correct, (A) and [A] is correct.

Write a program that takes a sequence of strings of this type and check
their correctness. Your program can assume that the maximum string
length is 128.

Input
-----

The first line contains a positive integer N. N lines will follow, each
containing a string of parentheses () and [].

Output
------

For each input string, output Yes or No followed by a newline.

Sample Input
------------

3
([])
(([()])))
([()[]()])()

Output for Sample Input
-----------------------

Yes
No
Yes

64. ANAGRAMS

Problem B - Anagrams
--------------------

An anagram is a word or phrase formed by rearranging the letters of
another word or phrase. For example, "carthorse" is an anagram of
"orchestra". Blanks within a phrase are ignored in forming anagrams.
Thus, "orchestra" and "horse cart" are also anagrams. Note that a phrase
is an anagram of itself.

Write a program that reads a list of phrases and prints all pairs of
anagrams occurring in the list.

Input
-----

The first line of the input will contain a single integer indicating the
number of test cases you need to test. The second line will be blank.
Each test case will consist of from 1 to 100 lines. A blank line signals
the end of a test case. Each line constitutes one phrase and will be at
most 255 characters long. All phrases will be in lower case.

Output
------

Some number of lines (including possibly 0 if there are no anagrams in
the list), each line containing two anagrammatic phrases separated by
'='.

Each anagram pair should be printed exactly once, and the order of the
output must be lexicographic, as shown in the sample output below.

After the output for each test case, output a blank line. If a test
case, contains no anagrams, only this blank line should be produced.

Sample Input
------------

3

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

fire
ice

power
woper


Output for Sample Input
-----------------------

carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut


power = woper

63. BEFORE "SUDOKU " NAME WAS discovered

Consider a 9 by 9 grid of squares.  It is partitioned into 9 blocks,
each of which is a 3 by 3 grid.  Some squares contain a number from
1 to 9, and the rest are blank.  Your task is to fill in each blank
with a number (also from 1 to 9) so that

1) no row contains the same number twice, and
2) no column contains the same number twice, and
3) no block contains the same number twice.

You may assume that the problem instances you are given either have
a unique solution or have no solution.  If a solution exists, you must
print it out. 

Input Format
------------

The file contains multiple problem instances.  The first line contains
the number of instances.  Each instance consists of 9 lines.  Each of
those lines consists of 9 numbers, separated by single spaces.

Output Format
-------------

For each instance, generate one line giving the instance number (see
sample output).
If no solution exists, you must print "No solution." on a separate
line.
If a solution exists, print it using the same format as the input.

Sample Input
------------

2
0 0 0 9 1 0 0 0 6
4 0 6 8 0 5 0 0 0
0 2 0 4 6 0 0 7 0
0 4 1 0 0 0 0 0 0
2 0 5 0 0 0 4 0 3
0 0 0 0 0 0 2 5 0
0 1 0 0 4 8 0 3 0
0 0 0 3 0 1 5 0 7
7 0 0 0 5 6 0 0 0
2 0 0 0 8 5 0 0 0
9 5 0 0 0 6 0 7 0
0 0 0 0 0 0 4 3 0
0 6 0 0 0 0 8 0 0
4 0 0 8 0 1 0 0 2
0 0 9 0 0 0 0 4 0
0 7 6 0 0 0 0 0 0
0 2 0 1 0 0 0 9 7
0 0 0 2 5 0 0 0 0

Sample Output
-------------

Instance 1:
8 5 7 9 1 2 3 4 6
4 3 6 8 7 5 9 1 2
1 2 9 4 6 3 8 7 5
3 4 1 5 2 9 7 6 8
2 6 5 1 8 7 4 9 3
9 7 8 6 3 4 2 5 1
5 1 2 7 4 8 6 3 9
6 8 4 3 9 1 5 2 7
7 9 3 2 5 6 1 8 4
Instance 2:
No solution.

62. Very simple One

Problem  Diagonals
---------------------

Given that an n-gon has at least N diagonals, what is the minimum
possible value of n?

Input
-----

Input consists of multiple lines, one line per case. Each line contains
a positive integer N ( N < 1015) that indicates the minimum possible
number of diagonals. Input is terminated by a line containing a zero.
This line should not be processed.

Output
------

For each line of input produce one line of output containing the minimum
possible value for n (Number of sides).

Sample Input
------------

10
100
1000
0

Output for Sample Input
-----------------------

7
16
47

61. 23 OUT of 5

23 Out of 5

Your task is to write a program that can decide whether you can find an arithmetic expression consisting of five given numbers

(1<=i<=5) that will yield the value 23.

For this problem we will only consider arithmetic expressions of the following from:

where : {1,2,3,4,5} -> {1,2,3,4,5} is a bijective function

and  {+,-,*} (1<=i<=4)

Input

The Input consists of 5-Tupels of positive Integers, each between 1 and 50.
Input is terminated by a line containing five zero's. This line should not be processed.

Output

For each 5-Tupel print "Possible" (without quotes) if their exists an arithmetic expression (as described above) that yields 23. Otherwise print "Impossible".

Sample Input

1 1 1 1 1

1 2 3 4 5

2 3 5 7 11

0 0 0 0 0

Sample Output

Impossible

Possible

Possible

60. Palindromes

Problem  - Palindromes!
------------------------

A palindrome is a string that reads the same forward and backward. An
L-palindrome is a string which is a palindrome if you ignore its first
character. An R-palindrome is a palindrome if its last character is
ignored. Given a string, decide whether it is a palindrome, an
L-palindrome, or an R-palindrome.

Input
-----

Each input line contains only a string of at least 1 and at most 25
uppercase letters. End of input is signaled by a line containing only
the word END, which should not be processed.

Output
------

For each input string, output one or more of the following messages:

string is not any type of palindrome.
string is a palindrome.
string is an L-palindrome.
string is an R-palindrome.

where string is the input string. If more than one message
applies, they should be output in the order given above.
Leave a blankline after the output for each input string.

Sample Input
------------

HELLOWORLD
OTTO
OTTOR
OROTOR
TOTO
END

Output for Sample Input
-----------------------

HELLOWORLD is not any type of palindrome.

OTTO is a palindrome.

OTTOR is an R-palindrome.

OROTOR is an L-palindrome.

TOTO is an L-palindrome.
TOTO is an R-palindrome.

59. John and Tiger

Problem - John and the tiger
------------------------------

N is a random number, which for some reason, is at least two digits.
John Doe, a nondescript man, performs an operation on N: he chops off
the last digit to form a new number M, and then finds N-M.  This excites
him in a hard-to-justify way.  He then tells you N-M.  Thrilled by the
fascinating back-story behind this number, you make it your life goal to
figure out what N was.

By the way, John was later eaten by a tiger.

Input
-----

Input consists of multiple lines, one line per case.  Each line contains
a single positive integer between 10 and 10^18 inclusive, giving the
value of N-M.  Input is terminated by a line containing 0.

Output
------

For each case, print one line containing the possible values of N in
sorted order.  Separate consecutive numbers with a single space.

Sample Input
------------

18
0

Output for Sample Input
-----------------------

19 20

58. SMS encoder

Problem : SMS Encoder
-----------------------

People who use SMS (Short Message Service) to send text messages on
their mobile telephones and other devices often abbreviate phrases to
squeeze more meaning into a message that is required to be short.

You must write a programme that takes an input string and creates an
SMS version of it by doing some simple substitutions.  First you
should replace some words by their abbreviations.  Below is a list of
the word substitutions you should make.

later -> l8r
at -> @
that -> th@
to -> 2
for -> 4
one -> 1
see -> c
you -> u
be -> b
not -> !
love -> luv

Note that you should *not* replace portions of words using the above rules.
For example, do not change "into" to "in2".

After making the word substitutions, you should replace double s by $,
double t by #.  Thus, "kiss" becomes "ki$", "pretty" becomes "pre#y".

Input Format
------------

The first line of the input file will contain the number of words in
the passage to be translated.  All input will be presented in
lower-case letters, and there will be no punctuation.  Words will be
separated by spaces or carriage returns.

Output Format
-------------

You should output the encoded message with the same spacing as the
original message.

Sample Input (for Valentine's Day)
------------

63
to be or not to be

see you later

sometimes with one i love i fill myself with rage
for fear i effuse unreturnd love
but now i think there is no unreturnd love
the pay is certain one way or another
i loved a certain person ardently
and my love was not returnd
yet out of that i have written these songs

Output for Sample Input
-----------------------

2 b or ! 2 b

c u l8r

sometimes with 1 i luv i fill myself with rage
4 fear i effuse unreturnd luv
but now i think there is no unreturnd luv
the pay is certain 1 way or another
i loved a certain person ardently
and my luv was ! returnd
yet out of th@ i have wri#en these songs

57.

{sum+=i++} to Reach N

All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. Given an integer less than (9*10^14+1) or (9E14 + 1) or (9*10¹⁴ +1) you will have to determine in how many ways that number can be expressed as summation of consecutive numbers.

Input

The input file contains less than 1100 lines of input. Each line contains a single integer N (0<=N<= 9E14). Input is terminated by end of file.

Output

For each line of input produce one line of output. This line contains an integer which tells in how many ways N can be expressed as summation of consecutive integers.

Sample Input

Sample Output

56.Mischellams

Michaelmas

Michaelmas is celebrated on September 29 each year.  Write a programme
that will figure out what day of the week Michaelmas falls on in any
given year.  Recall that years divisible by 100 are not leap years,
unless the year is also divisible by 400.  (So 2000 was a leap year,
but 2100, 2200 and 2300 will not be.)

Input

The first line will contain an integer n giving the number of problem
instances.  The following n lines will each contain a year in the
range 1900 to 50000000.

Output

On a separate line for each year, output the day of the week on which
Michaelmas falls.

Sample Input

3
2004
1936
1972

Sample Output

Wednesday
Tuesday
Friday

55. Plot Graph On a Dumb Terminal

Plotting graphs on a dumb (vt100) terminal

You have a client who is a mathematician and wants you to write a program to plot graphs. Unfortunately, all he has is a vt100 (i.e. ASCII, non-graphic) terminal that connects to the department server. This terminal can display 41 lines of text at a time, and each line has 61 characters. Your graph plotting program must work on this setup.

Your current task is to write a program that plots only linear functions -- you need to see how graphs look on such a terminal, before proceeding further, Remembering that the equation for a linear function is y=ax + b, you see that you need two inputs a,b. You can assume that the range of x and y for which the function needs to be plotted are 0 <= x <= 6.0, and 0 <= y <= 40. Each point on the graph is marked with a "*" and the axes are marked with the characters "|" and "-" (see the sample output). The graph has 60 points, one for each non-zero value of x. Each point is rounded to the nearest character; e.g. y=4.51 for some x implies that a star be drawn corresponding to y=5. If a point is out of range (i.e. if y>40), the point can be ignored. For simplicity, all non-graph points are blanks (" ") in the output file. Any point that lies on an axis is not plotted.

Input

The input has two floating point numbers a,b (a,b > 0).

Output

The output will be the plot of the line on the 60x40 terminal. Note that each line, including the last one (the x-axis), has a newline at the end of it.

Sample Input

10.0 1.0

Sample Output

|                                      *                   
|                                     *                    
|                                    *                     
|                                   *                      
|                                  *                       
|                                 *                        
|                                *                         
|                               *                          
|                              *                           
|                             *                            
|                            *                             
|                           *                              
|                          *                               
|                         *                                
|                        *                                 
|                       *                                  
|                      *                                   
|                     *                                    
|                    *                                     
|                   *                                      
|                  *                                       
|                 *                                        
|                *                                         
|               *                                          
|              *                                           
|             *                                            
|            *                                             
|           *                                              
|          *                                               
|         *                                                
|        *                                                 
|       *                                                  
|      *                                                   
|     *                                                    
|    *                                                     
|   *                                                      
|  *                                                       
| *                                                        
|*                                                         
|                                                          
-------------------------------------------------------------

54. In Danger

In Danger:

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 Specification

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 Specification

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

05e0
01e1
42e0
66e6
00e0

Sample Output

53. Sloppy Fractions

Problem : Sloppy Fractions
Fractions are real numbers that can be written as a/b, where a and b are both integers, and b 6!= 0. We
will restrict ourselves to fractions that lie between 0 and 1, both inclusive. This means that 0 GT aLT b when
both a and b are non-negative. There are two ways of writing fractions: In the Canonical form, we write a
fraction as a/b where a and b are positive integers having no factor in common (except 1, of course). In the
Decimal form, brackets are placed around the smallest-sized left-most group of digits that repeats. Here
are some examples:
Fraction Canonical Decimal Full expansion
5/12 5/12 0.41(6) 0.41666666...
3/21 1/7 0.(142857) 0.142857142857142857...
1/5 1/5 0.2(0) 0.2000000...
7/8 7/8 0.875(0) 0.875000000...
3/9 1/3 0.(3) 0.3333333...
By convention, the Canonical form for fraction 0.0000 . . . will be 0/1.
Our protagonist is mathematician Chen, who prefers writing fractions in the Decimal form. Chen is
quite old — he celebrated his 100th birthday a fortnight ago. He’s become sloppy over the years. Since
his 90th birthday, he hasn’t necessarily been placing the brackets around the smallest-sized left-most group
of digits that repeats. For example, he might write 0.52(01) as 0.5201(01) or even as 0.52010101(0101).
Further, since his 100th birthday, he’s been forgetting to place the brackets around the repeating-groups!
This means that 0.520101 might denote any of the following: 0.52010(1), 0.5201(01), 0.520(101), 0.52(0101),
0.5(20101), 0.(520101) and 0.520101. Your goal is to write a program which will take a string written down
by Chen as input, and produce all possible fractions in Canonical form that string could correspond to.
Input: One string per line, of the form 0.a1a2 . . . a`, where 1 ` 6 and each of a1, a2 . . . a` is a digit
between 0 and 9.
Output: See the format below. Each fraction should be printed in the Canonical form. There should
be no duplicates. Fractions should be sorted by magnitude, smallest to largest. There should be exactly one
blank separating the fractions, and one blank before and after the = symbol, as shown below.
Input Output
0.000
0.3
0.32
0.99
0.511
0.5151
0.000 = 0/1
0.3 = 3/10 1/3
0.32 = 8/25 29/90 32/99
0.99 = 99/100 1/1
0.511 = 511/1000 23/45 511/999
0.5151 = 5151/10000 1159/2250 2573/4995 17/33

52.PATRIK

PATRIK:
N people are waiting in line to enter a concert. People get bored waiting so they turn and look for
someone familiar in the line.
Two persons A and B standing in line can see each other if they're standing right next to each other or
if no person between them is strictly taller than person A or person B.

Write a program that determines the number of pairs of people that can see each other.

INPUT
The first line of input contains an integer N (1 ≤ N ≤ 500 000), the number of people standing in line.
Each of the following N lines contains a single integer, the height of one person in nanometres.
Everyone will be shorter than 231 nanometres.
The heights are given in the order in which people are standing in line.

OUTPUT
Output the number of pairs of people that can see each other on a single line.
SAMPLE TEST DATA
input
7
2
4
1
2
2
5
1
output
10

Thursday, June 25, 2009

51.MAKING MONEY

Problem :Making Money
A trick sometimes used by parents to teach their children the value of money is to give then a penny – just
a penny! – and the promise that for each day they don’t spend it, the parent will double it. All students of
computing know that long before a month has elapsed without spending a cent, the parents will not likely be
able to make good on their promise.
100-percent compound daily interest on an investment is, of course, unattainable in normal financial
dealings, but we are all continually reminded of the power of compound interest, even with the relatively
low interest rates available today.
But exactly how much money can be made with compound interest? Assume, for example, an initial
investment of $100.00 (US or Canadian ☺), an annual interest rate of 6.00 percent, and that interest is
compounded monthly. That is, the interest earned during the preceding month is added to the principal at
the end of the month. (For our purposes, we’ll assume a month is exactly 1/12th of a year.)
At the end of the first month, the money will have earned 0.5 percent interest (1/12th of 6.00 percent), or
$0.50. This is added to the $100.00 invested, so that during the next month, interest is paid on $100.50.
During the next month another 0.5 percent interest is earned, which is exactly $0.5025. We will assume
that the bank, being conservative, will not pay any interest less than $0.01, so our investment is credited
with an additional $0.50 at the end of the second month, for a whopping total of $101.00. Continuing in the
same manner, at the end of 12 months our investment will total $106.12, $0.12 more than simple 6.00
percent interest for a year with no compounding.
Given an amount P to be invested for a year with I percent interest, compounded C times during the year at
equal intervals, what is total return on the investment?
Input
There will be multiple cases to consider. The input for each case is a single line containing the initial
investment amount, P, given in dollars and cents (but no fractional cents, and no larger than $100,000.00),
the annual interest rate (I) given as a real number with two fractional digits representing a percentage,
greater than zero but less than 100, and the number of compounding intervals per year (C), an integer
between 1 and 365. The last case will be followed by a line containing “0.00 0.00 0”.
Output
For each input case, display the case number (1, 2, ...), the initial investment (P), the annual interest rate
(I), the number of compounding intervals per year(C), and the value of the investment at the end of a year.
Your output should follow the format shown in the examples below.
Expected Output
Sample Input
Case 1. $100.00 at 6.00% APR compounded 1 times yields $106.00
100.00 6.00 1
Case 2. $100.00 at 6.00% APR compounded 12 times yields $106.12
100.00 6.00 12
Case 3. $1000.00 at 6.00% APR compounded 12 times yields $1061.63
1000.00 6.00 12
0.00 0.00 0

50.Ambiguos Permutations

Ambiguous Permutations

Some programming contest problems are really tricky: not only do they require a different output format from what you might have expected, but also the sample output does not show the difference. For an example, let us look at permutations.
A permutation of the integers 1 to n is an ordering of these integers. So the natural way to represent a permutation is to list the integers in this order. With n = 5, a permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation: You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation. The permutation 1, 4, 3, 2 for example is ambiguous, because its inverse permutation is the same. To get rid of such annoying sample test cases, you have to write a program which detects if a given permutation is ambiguous or not.
Input Specification

The input contains several test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 100000). Then a permutation of the integers 1 to n follows in the next line. There is exactly one space character between consecutive integers. You can assume that every integer between 1 and n appears exactly once in the permutation.
The last test case is followed by a zero.
Output Specification

For each test case output whether the permutation is ambiguous or not. Adhere to the format shown in the sample output.
Sample Input

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

Sample Output

ambiguous
not ambiguous
ambiguous

49. Digits of PIE

DIGITS OF PIE
In this problem you have to find as many digits of PI as possible.

Output

Output must contain as many digits of PI as possible (not more than 1000000).
Score

The score awarded to your program will be the first position of the digit where the first difference occured.

Example

Output:
3.1415926535897932384626433832795

will be awarded with 33 points

Wednesday, June 24, 2009

48.Orders

Orders

The stores manager has sorted all kinds of goods in an alphabetical
order of their labels. All the kinds having labels starting with the
same letter are stored in the same warehouse (i.e. in the same
building) labelled with this letter. During the day the stores manager
receives and books the orders of goods which are to be delivered from
the store. Each order requires only one kind of goods. The stores
manager processes the requests in the order of their booking.

You know in advance all the orders which will have to be processed by
the stores manager today, but you do not know their booking
order. Compute all possible ways of the visits of warehouses for the
stores manager to settle all the demands piece after piece during the
day.

Input:

Input file ORDERS.IN contains a single line with all labels of the
requested goods (in random order). Each kind of goods is represented
by the starting letter of its label. Only small letters of the English
alphabet are used. The number of orders doesn't exceed 200.

Output:

Output file ORDERS.OUT will contain all possible orderings in which
the stores manager may visit his warehouses. Every warehouse is
represented by a single small letter of the English alphabet -- the
starting letter of the label of the goods. Each ordering of warehouses
is written in the output file only once on a separate line and all the
lines containing orderings have to be sorted in an alphabetical order
(see the example). No output will exceed 2 megabytes.

Example:

ORDERS.IN
bbjd

ORDERS.OUT
bbdj
bbjd
bdbj
bdjb
bjbd
bjdb
dbbj
dbjb
djbb
jbbd
jbdb
jdbb

47. Roads

Roads:

N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it: the road length and the toll that needs to be paid for the road (expressed in the number of coins). Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash. We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.
Input

The input begins with the number t of test cases. Then t test cases follow. The first line of the each test case contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way. The second line contains the integer N, 2 <= N <= 100, the total number of cities. The third line contains the integer R, 1 <= R <= 10000, the total number of roads. Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters : S is the source city, 1 <= S <= N D is the destination city, 1 <= D <= N L is the road length, 1 <= L <= 100. T is the toll (expressed in the number of coins), 0 <= T <= 100 Notice that different roads may have the same source and destination cities.
Output

For each test case, output a single line contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins. If such path does not exist, output -1.
Example

Input:
2
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0

Output:
11
-1

46. Prime Generator

Prime1
Shridhar wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers.
Input

The first line contains t, the number of test cases (less then or equal to 10). Followed by t lines which contain two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output

For every test case print all prime numbers p such that m <= p <= n, one number per line. Separate the answers for each test case by an empty line.
Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)

Monday, June 22, 2009

45.FIND THE DISTANCE

Problem : Find the Distance

Given two numbers written out in binary with the same number of binary digits, the Hamming distance between them is the number of positions where they differ. For example the Hamming distance between

and

is 2 since they differ in the leftmost two positions and nowhere else. Similarly the Hamming distance between

and

is 2.

Suppose we consider binary numbers of length K. Given a number N with N ≤ 2^K - 1, we want to find the sum of the Hamming distances between 0 and 1, 1 and 2 and so on till N-1 and N.

For example if K=3 and N=4 the answer is 7 since the Hamming distance between 000 and 001 (0 and 1 written using 3 bits) is 1, the distance between 001 and 010 is 2, between 010 and 011 is 1 and between 011 and 100 is 3.

Given K and N, your task is to find the sum of the Hamming distances between the K-digit binary representations of 0 and 1, 1 and 2, ..., N-1 and N.

Input format

A single line with two positive integers K and N.

Output format

A single line with a single integer giving the required sum of Hamming distances.

Test data

You may assume that K ≤ 32 and N ≤ 1000000.

Example

We now illustrate the input and output formats using the above example.

Sample input

3 4

Sample output

44. WHAT IS RANK?

Problem 44: What is the Rank?

This is one more story about our old friend, the Despotic King. Once every year, it was customary for the king to give audience to the rich merchants of his country in a large hall. On that day, the merchants were ushered in to meet the king one by one and after paying their respects to the king they were seated in the auditorium.

It was the job of the minister to introduce each merchant, as he arrived, to the others in the hall. He would announce his name and his wealth. However, our quirky king demanded that in addition, he should also announce the rank of the merchant among all those in the hall (at the time of his arrival) in terms of his wealth.

For example, let us suppose that the wealth of the 6 merchants who met the king (in the order in which they arrived) is given by the sequence

 78  24  68  40  39  89

Then, clearly the first merchant is the richest in the hall when he enters it (since there are no others in the hall) and so his rank is 1. Since 24 <>

 1  2  2  3  4  1

Your task is to write a program that takes as input a sequence of distinct positive integers indicating the wealth of the merchants in the order in which they visit the king and outputs the sequence of ranks announced by the minister.

Input format

The first line contains a single integer N indicating the number of merchants. The next N lines (line 2,...,N+1) describe the wealth of these N merchants. Line i+1 contains a single positive integer indicating the wealth of the i^th merchant to enter the hall.

Output format

Your output should consist of N lines. Line i should be the rank announced when the i^th minister enters the hall.

Test Data:

You may assume N ≤ 45000 and that no two merchants have the same wealth. Further you may also assume that in 30% of of the inputs N ≤ 8000.

Example:

Here are the inputs and outputs corresponding to the example discussed above.

Sample Input

Sample Output

43.REVERSE

Revese

In this problem the input will consist of a number of lines of English text consisting of the letters of the English alphabet, the punctuation marks ' (apostrophe), . (full stop), , (comma), ; (semicolon), :(colon) and white space characters (blank, newline). Your task is print the words in the text in reverse order without any punctuation marks.
For example consider the following candidate for the input text:

This is a sample piece of text to illustrate this 
problem.  If you are smart you will solve this right.

The corresponding output would read as:

right this solve will you smart are you If problem
this illustrate to text of piece sample a is This

That is, the lines are printed in reverse order and in each line the words are printed in reverse order.

Input format

The first line of input contains a single integer N, indicating the number of lines in the input. This is followed by N lines of input text.

Output format

N lines of output text containing the input lines in reverse order and where each line contains the words in reverse order as illustrated above.

Test data

You may assume that N ≤ 10000 and that there are at most 80 characters in each line.

Example

We now illustrate the input and output formats using the above example.

Sample input

2
This is a sample piece of text to illustrate this 
problem.  If you are smart you will solve this right.

Sample output

right this solve will you smart are you If problem
this illustrate to text of piece sample a is This

Sunday, June 21, 2009

42: Interpreter

Problem : Interpreter

A certain computer has 10 registers and 1000 words of RAM. Each register or RAM location holds a 3-digit integer between 0 and 999. Instructions are encoded as 3-digit integers and stored in RAM. The encodings are as follows:

100 means halt
2dn means set register d to n (between 0 and 9)
3dn means add n to register d
4dn means multiply register d by n
5ds means set register d to the value of register s
6ds means add the value of register s to register d
7ds means multiply register d by the value of register s
8da means set register d to the value in RAM whose address is in register a
9sa means set the value in RAM whose address is in register a to the value of register s
0ds means goto the location in register d unless register s contains 0

All registers initially contain 000. The initial content of the RAM is read from standard input. The first instruction to be executed is at RAM address 0. All results are reduced modulo 1000.

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 to your program consists of up to 1000 3-digit unsigned integers, representing the contents of consecutive RAM locations starting at 0. Unspecified RAM locations are initialized to 000.

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 output from your program is a single integer: the number of instructions executed up to and including the halt instruction. You may assume that the program does halt.

Sample Input

Sample Output

41. Graphical Editor

Problem : Graphical Editor

Problem

The simple graphical editor deals with a rectangular table M×N (1<=M,N<=250). Each pixel of the table has its colour. The picture is formed from this square pixels.

The problem is to write a program, which simulates an interactive work of the graphical editor.

Input

Input consists of the editor commands, one per line. Each command is represented by one Latin capital placed in the very beginning of the line. If the command supposes parameters, all the parameters will be given in the same line separated by space. As the parameters there may be: the coordinates of the pixel - two integers, the first one is the column number and belongs to 1..M, the second one is the row number and belongs to 1..N, the origin is in the upper left corner of the table; the colour - the Latin capital; file name - in MSDOS 8.3 format.

The editor deals with the following commands:

I M N	Creates a new table M×N. All the pixels are colored in white (O).
C	Clears the table. The size remains the same. All the pixels became white (O).
L X Y C	Colors the pixel with coordinates (X,Y) in colour C.
V X Y1 Y2 C	Draws the vertical segment in the column X between the rows Y1 and Y2 inclusive in colour C.
H X1 X2 Y C	Draws the horizontal segment in the row Y between the columns X1 and X2 inclusive in colour C.
K X1 Y1 X2 Y2 C	Draws the filled rectangle in colour C. (X1,Y1) is the upper left corner, (X2,Y2) is the lower right corner of the rectangle.
F X Y C	Fills the region with the colour C. The region R to be filled is defined as follows. The pixel (X,Y) belongs to this region. The other pixel belongs to the region R if and only if it has the same colour as pixel (X,Y) and a common side with any pixel which belongs to this region.
S Name	Writes the picture in the file Name.
X	Terminates the session.

Output

Every time the command S NAME meets, you should output the file name NAME and the current table, row by row. Each row is represented by a pixels' colours series, see the output sample.

Errors

If as a command there will be a character different from I, C, L, V, H, K, F, S, X, the editor should ignore the whole line and pass to the next command.

In case of other errors the program behaviour is unpredictable.

Sample Input

I 5 6
L 2 3 A
S one.bmp
G 2 3 J
F 3 3 J
V 2 3 4 W
H 3 4 2 Z
S two.bmp
X

Sample Output

one.bmp
OOOOO
OOOOO
OAOOO
OOOOO
OOOOO
OOOOO
two.bmp
JJJJJ
JJZZJ
JWJJJ
JWJJJ
JJJJJ
JJJJJ


 
Alexander Denisjuk, 2002

40. STACK'EM UP

Problem : 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

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

39 Hartals

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<=N<=3650) giving the number of days over which the simulation must be run. The next line contains another integer p( 1<=p<=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<=i<=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

38: You can say 11

Problem : You can say 11
Time Limite: 1 second

Introduction to the problem

Your job is, given a positive number N, determine if it is a multiple of eleven.

Description of the input

The input is a file such that each line contains a positive number. A line containing the number 0 is the end of the input. The given numbers can contain up to 1000 digits.

Description of the output

The output of the program shall indicate, for each input number, if it is a multiple of eleven or not.

Sample input:

112233
30800
2937
323455693
5038297
112234
0

Sample output

112233 is a multiple of 11.
30800 is a multiple of 11.
2937 is a multiple of 11.
323455693 is a multiple of 11.
5038297 is a multiple of 11.
112234 is not a multiple of 11.

37. Trip Problem

Problem : 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.

The Input

Standard input will contain the information for several trips. The information for each trip consists of a line containing a positive integer, n, the number of students on the trip, followed by n lines of input, each containing the amount, in dollars and cents, spent by a student. There are no more than 1000 students and no student spent more than $10,000.00. A single line containing 0 follows the information for the last trip.

The Output

For each trip, output a line stating the total amount of money, in dollars and cents, that must be exchanged to equalize the students' costs.

Sample Input

Output for Sample Input

$10.00
$11.99

36. Minesweeper 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.

The Input

The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n =" m">

The Output

For each field, you must print the following message in a line alone:

Field #x:

Where x stands for the number of the field (starting from 1). The next n lines should contain the field with the "." characters replaced by the number of adjacent mines to that square. There must be an empty line between field outputs.

Sample Input

4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

Sample Output

Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

35. 3n+ 1 problem

The 3n + 1 problem

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:

1. input n

2. print n

3. if n = 1 then STOP

4. if n is odd then

5. else

6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n <>

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

34.LCD Dispaly

LC-Display

A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.

Input

The input file contains several lines, one for each number to be displayed. Each line contains two integers s, n ( $1 \le s \le 10, 0 \le n \le 99\,999\,999$ ), where n is the number to be displayed and s is the size in which it shall be displayed.

The input file will be terminated by a line containing two zeros. This line should not be processed.

Output

Output the numbers given in the input file in an LC-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, also for the last digit.) There has to be exactly one column of blanks between two digits.

Output a blank line after each number. (You will find a sample of each digit in the sample output.)

Sample Input

2 12345
3 67890
0 0

Sample Output

      --   --        --
 |    |    | |  | | 
 |    |    | |  | | 
    --   --   --   --
 | |       |    |    |
 | |       |    |    |
    --   --        --

---   ---   ---   ---   ---
|         | |   | |   | |   |
|         | |   | |   | |   |
|         | |   | |   | |   |
---         ---   ---     
|   |     | |   |     | |   |
|   |     | |   |     | |   |
|   |     | |   |     | |   |
---         ---   ---   ---

33.Fibary

We are familiar with radix number representations where digits read from right-to-left (least
significant to most significant) signify increasing powers of some radix (i.e. base) number, e.g.
100, 101, 102, 103, . . . in decimal representation or 20, 21, 22, 23, . . . in binary representation. For
example, the binary number 101001 represents
1 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 0 · 21 + 1 · 20 = 41.

In this problem, we consider a number representation where digits read from right-to-left (least
significant to most significant) signify increasing Fibonacci numbers 1, 2, 3, 5, 8, 13, 21, . . . we’ll
call them fibary numbers. Each digit of a fibary number is either 0 or 1. For example, the fibary
number 101001 represents
1 · 13 + 0 · 8 + 1 · 5 + 0 · 3 + 0 · 2 + 1 · 1 = 19.
While each number has exactly one radix representation without leading zeroes, it can have more
than one fibary representation without leading zeroes. For example, the fibary number 11111 also
represents
1 · 8 + 1 · 5 + 1 · 3 + 1 · 2 + 1 · 1 = 19.
However, each number has exactly one fibary representation without leading zeroes or succes-
sive ones—its canonical fibary representation. Of all the fibary representations of a number, the
canonical one is the largest when viewed as a binary number.

Input Format
Each line contains the decimal representation of a nonnegative number less than 231.

Output Format
For each decimal number input, output a line containing its canonical fibary representation.

Input Sample Output Sample
0 0
19 101001
10 10010
100 1000010100
1000000000 1010000100100001010101000001000101000101001
123456 1000000001001001000000000
654321 1001000100000100000000000001
2009 1001000010000001
317810 10101010101010101010101010

32.Absent

Given a string of symbols, it’s natural to look it over and see what substrings are present. In
this problem, you are given a string and asked to consider what substrings are absent. Of course,
a given string has finite length and therefore only finitely many substrings, so there are always
infinitely many strings that don’t appear as substrings of a given string. We’ll seek to find the
lexicographically least string that is absent from the given string.

Input Format

Each line of input contains a string x over the alphabet {a, b, c}. x may be the empty string,
as shown in the second line of the input sample below, or a nonempty string.

Output Format
For each input string x, find and output the lexicographically least string s over the alphabet
{a, b, c} such that s is not a substring of x; i.e. s is absent from x. Since the empty string is a
substring of every string, your output s is necessarily nonempty. Recall that a string is lexico-
graphically less than another string if it is shorter or is the same length and alphabetically less;
e.g. b
below.

Input Sample Output Sample
bcabacbaa
bb is absent from bcabacbaa
a is absent from
aac is absent from aaabacbbcacc
aaabacbbcacc

31.Permute Up

Consider all strings that can be obtained by permuting the characters of a given string. For
example, the permutations of the string cab listed alphabetically are
abc, acb, bac, bca, cab, cba.
In general, there are n! permutations of a string of length n. In this problem, you are given a string
x over the 36-character alphabet {0, 1, 2, . . . , 9, a, b, c, . . . , z}, and must find the permutation of x
that immediately follows x in the alphabetical list of permutations of x. For example, the successor
permutation of cab is cba, and there is no successor permutation of cba.
Input Format
Each line of input contains a nonempty string x over the 36-character alphabet
{0, 1, 2, . . . , 9, a, b, c, . . . , z}.
Output Format
For each input string x, find the permutation of x that immediately follows x in the alphabeti-
cal list of permutations of x. Output x and its successor permutation separated by ’ -> ’, as shown
in the output sample. If there is no successor permutation of x, output ’no successor’ instead.
Input Sample
Output Sample
12
12 -> 21
03snd3fk5ee2
03snd3fk5ee2 -> 03snd3fke25e
gfedcba987
gfedcba987 -> no successor
036420 036420 -> 040236

30. Ratio

Scenario
If you ever see a televised report on stock market activity, you'll hear the anchorperson say something like ``Gainers outnumbered losers 14 to 9,'' which means that for every 14 stocks that increased in value that day, approximately 9 other stocks declined in value. Often, as you hear that, you'll see on the screen something like this:

Gainers 1498
Losers 902

As a person with a head for numbers, you'll notice that the anchorperson could have said ``Gainers outnumbered losers 5 to 3'', which is a more accurate approximation to what really happened. After all, the exact ratio of winners to losers is (to the nearest millionth) 1.660754, and he reported a ratio of 14 to 9, which is 1.555555, for an error of 0.105199; he could have said ``5 to 3'', and introduced an error of only 1.666667-1.660754=0.005913. The estimate ``5 to 3'' is not as accurate as ``1498 to 902'' of course; evidently, another goal is to use small integers to express the ratio. So, why did the anchorperson say ``14 to 9?'' Because his algorithm is to lop off the last two digits of each number and use those as the approximate ratio.

What the anchorman needs is a list of rational approximations of increasing accuracy, so that he can pick one to read on the air. Specifically, he needs a sequence {a_1, a_2, ..., a_n} where a_1 is a rational number with denominator 1 that most exactly matches the true ratio of winners to losers (rounding up in case of ties), a_{i+1} is the rational number with least denominator that provides a more accurate approximation than a_i, and a_n is the exact ratio, expressed with the least possible denominator. Given this sequence, the anchorperson can decide which ratio gives the best tradeoff between accuracy and simplicity.

For example, if 5 stocks rose in price and 4 fell, the best approximation with denominator 1 is 1/1; that is, for every stock that fell, about one rose. This answer differs from the exact answer by 0.25 (1.0 vs 1.25). The best approximations with two in the denominator are 2/2 and 3/2, but neither is an improvement on the ratio 1/1, so neither would be considered. The best approximation with three in the denominator 4/3, is more accurate than any seen so far, so it is one that should be reported. Finally, of course, 5/4 is exactly the ratio, and so it is the last number reported in the sequence.

Can you automate this process and help the anchorpeople?
Input
The file "ratio.inp" contains several pairs of positive integers. Each pair is on a line by itself, beginning in the first column and with a space between the two numbers. The first number of a pair is the number of gaining stocks for the day, and the second number is the number of losing stocks for the day. The total number of stocks never exceeds 5000.
Output
For each input pair, the standard output should contain a series of approximations to the ratio of gainers to losers. The first approximation has '1' as denominator, and the last is exactly the ratio of gainers to losers, expressed as a fraction with least possible denominator. The approximations in between are increasingly accurate and have increasing denominators, as described above.

The approximations for a pair are printed one to a line, beginning in column one, with the numerator and denominator of an approximation separated by a slash (``/''). A blank line separates one sequence of approximations from another.

Sample Input
5 4
1498 902
Sample Output
1/1
4/3
5/4

2/1
3/2
5/3
48/29
53/32
58/35
63/38
68/41
73/44
78/47
83/50
88/53
93/56
377/227
470/283
563/339
656/395
749/451

29.Fill Jugs

Problem : Jugs

In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle.

You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug, (2) you can empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.

A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. A solution is a sequence of steps that leaves exactly N gallons in jug B. The possible steps are

fill A
fill B
empty A
empty B
pour A B
pour B A
success

where "pour A B" means "pour the contents of jug A into jug B", and "success" means that the goal has been accomplished.

You may assume that the input you are given does have a solution.

Input Format

Input to your program consists of a series of input lines each defining one puzzle. Input for each puzzle is a single line of three positive integers: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goal. You can assume 0 < Ca <= Cb and N <= Cb <=1000 and that A and B are relatively prime to one another.

Required Output Format

Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing exactly N gallons of water. The last line of output for each puzzle should be the line "success". Output lines start in column 1 and there should be no empty lines nor any trailing spaces.

Sample Input

3 5 4
5 7 3

Sample Output

fill B
pour B A
empty A
pour B A
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
empty B
pour A B
success

28.Last nonzero Digit of a big factorial

Problem : Just the Facts

The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example,

N N!
0 1
1 1
2 2
3 6
4 24
5 120
10 3628800

For this problem, you are to write a program that can compute the last non-zero digit of any factorial for (0 <= N <= 10000). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce "2" because 5! = 120, and 2 is the last nonzero digit of 120.

Input Format

Input to the program is a series of nonnegative integers not exceeding 10000, each on its own line with no other letters, digits or spaces. For each integer N, you should read the value and compute the last nonzero digit of N!.

Required Output Format

For each integer input, the program should print exactly one line of output. Each line of output should contain the value N, right-justified in columns 1 through 5 with leading blanks, not leading zeroes. Columns 6 - 9 must contain " -> " (space hyphen greater space). Column 10 must contain the single last non-zero digit of N!.

Sample Input

1
2
26
125
3125
9999

Sample Output

1 -> 1
2 -> 2
26 -> 4
125 -> 8
3125 -> 2
9999 -> 8

27. Uniform Generator

Problem : Uniform Generator

Computer simulations often require random numbers. One way to generate pseudo-random numbers is via a function of the form

seed(x+1) = [ seed(x) + STEP ] % MOD

where "%" is the modulus operator.

Such a function will generate pseudo-random numbers (seed) between 0 and MOD-1. One problem with functions of this form is that they will always generate the same pattern over and over. In order to minimize this effect, selecting the STEP and MOD values carefully can result in a uniform distribution of all values between (and including) 0 and MOD-1.

For example, if STEP=3 and MOD=5, the function will generate the series of pseudo-random numbers 0, 3, 1, 4, 2 in a repeating cycle. In this example, all of the numbers between and including 0 and MOD-1 will be generated every MOD iterations of the function. Note that by the nature of the function to generate the same seed(x+1) every time seed(x) occurs means that if a function will generate all the numbers between 0 and MOD-1, it will generate pseudo-random numbers uniformly with every MOD iterations.

If STEP = 15 and MOD = 20, the function generates the series 0, 15, 10, 5 (or any other repeating series if the initial seed is other than 0). This is a poor selection of STEP and MOD because no initial seed will generate all of the numbers from 0 and MOD-1.

Your program will determine if choices of STEP and MOD will generate a uniform distribution of pseudo-random numbers.

Input
Each line of input will contain a pair of integers for STEP and MOD in that order (1<=STEP,MOD<=100000).

Output
For each line of input, your program should print the STEP value right-justified in columns 1 through 10, the MOD value right-justified in columns 11 through 20 and either "Good Choice" or "Bad Choice" left-justified starting in column 25. The "Good Choice" message should be printed when the selection of STEP and MOD will generate all the numbers between and including 0 and MOD-1 when MOD numbers are generated. Otherwise, your program should print the message "Bad Choice". After each output test set, your program should print exactly one blank line.

Sample Input
3 5
15 20
63923 99999

Sample Output
3 5 Good Choice
15 20 Bad Choice
63923 99999 Good Choice

26.palinndrome as well as mirror image

Problem Palindromes

A regular palindrome is a string of numbers or letters that is the same
forward as backward. For example, the string "ABCDEDCBA" is a
palindrome because it is the same when the string is read from left to
right as when the string is read from right to left.

A mirrored string is a string for which when each of the elements of
the string is changed to its reverse (if it has a reverse) and the
string is read backwards the result is the same as the original string.
For example, the string "3AIAE" is a mirrored string because "A" and
"I" are their own reverses, and "3" and "E" are each others' reverses.

A mirrored palindrome is a string that meets the criteria of a regular
palindrome and the criteria of a mirrored string. The string "ATOYOTA"
is a mirrored palindrome because if the string is read backwards, the
string is the same as the original and because if each of the
characters is replaced by its reverse and the result is read backwards,
the result is the same as the original string. Of course, "A", "T",
"O", and "Y" are all their own reverses.

A list of all valid characters and their reverses is as follows.

Character Reverse Character Reverse Character Reverse
A A M M Y y
B N Z 5
C O O 1 1
D P 2 S
E 3 Q 3 E
F R 4
G S 5 Z
H H T T 6
I I U U 7
J L V V 8 8
K W W 9
L J X X

* Note that 0 (zero) and O (the letter) are considered the same
character and therefore ONLY the letter "O" is a valid character.

Input
Input consists of strings (one per line) each of which will consist of
one to twenty valid characters. There will be no invalid characters in
any of the strings. Your program should read to the end of file.

Output
For each input string, you should print the string starting in column 1
immediately followed by exactly one of the following strings.

STRING
CRITERIA

" -- is not a palindrome."
if the string is not a palindrome
and is not a mirrored string

" -- is a regular palindrome."
if the string is a palindrome and
is not a mirrored string

" -- is a mirrored string."
if the string is not a palindrome
and is a mirrored string

" -- is a mirrored palindrome."
if the string is a palindrome and
is a mirrored string

Note that the output line is to include the -'s and spacing exactly as
shown in the table above and demonstrated in the Sample Output below.
In addition, after each output line, you must print an empty line.

Sample Input
NOTAPALINDROME
ISAPALINILAPASI
A3MEA
ATOYOTA

Sample Output
NOTAPALINDROME -- is not a palindrome

ISAPALINILAPASI -- is a regular palindrome

2A3MEAS -- is a mirrored string

ATOYOTA -- is a mirrored palindrome

p.no-25(Boggle Game)

PROBLEM
The Boggle Game

The language PigEwu has a very simple syntax. Each word in this language has exactly 4 letters, the first cannot be a vowel. Also each word contains one or two vowels (y is consider a vowel in PigEwu). For instance, maar and beer are legitimate words, arts is not a legal word.

In the game boggle, you are given a 4x4 array of letters and asked to find all words contained in it. A word in our case (PigEwu) will thus be a sequence of 4 distinct squares (letters) that form a legal word and such that each square touches (have a corner or edge in common) the next square.

For example:

A S S D
S B E Y
G F O I
H U U K

In this board a (partial) list of legal words include:

BASS SABS FOIK FOYD SYDE HUGS

BOBS is a legal word but it is not on this boggle board (there are no two B's here).

Write a program that reads a pair of Boggle boards and lists all PigEwu words that are common to both boards.

The input file will include a few data sets. Each data set will be a pair of boards
as shown in the sample input. All entries will be upper case letters. Two consecutive entries on same board will be separated by one blank. The first row in the first board will be on the same line as the first row of the second board. They will be separated by a few tabs, the same will hold for the remaining 3 rows. Board pairs will be separated by a blank line. The file will be terminated by “#”.

For each pair of boggle boards, output a sorted list of all common words, each word on a separate line; or the statement “There are no common words for this pair of boggle boards.” Separate the output for each pair of boggle boards with a blank line.

Sample Input:

D F F B W A S U
T U G I B R E T
O K J M Y A P Q
K M B E L O Y R

Sample Output:

There are no common words for this pair of boggle boards.

P.no-24 (calculate date and day )

PROBLEM : 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. 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 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. The input will end with three zeroes.

Sample Input:

11 15 1997
1 1 2000
7 4 1998
2 11 1732
9 2 1752
9 14 1752
4 33 1997
0 0 0

Sample Output:

November 15, 1997 is a Saturday
January 1, 2000 is a Saturday
July 4, 1998 is a Saturday
February 11, 1732 is a Friday
September 2, 1752 is a Wednesday
September 14, 1752 is a Thursday
4/33/1997 is an invalid date.

P.No-3 Look at the picture

0 0

Expected Output

4 knights may be placed on a 2 row 3 column board.

13 knights may be placed on a 5 row 5 column board.

14 knights may be placed on a 4 row 7 column booard

22. Pseudo random number generation

Problem : Psuedo-Random Numbers

Computers normally cannot generate really random numbers, but frequently are used to generate sequences of pseudo-random numbers. These are generated by some algorithm, but appear for all practical purposes to be really random. Random numbers are used in many applications, including simulation.

A common pseudo-random number generation technique is called the linear congruential method. If the last pseudo-random number generated was L, then the next number is generated by evaluating (Z x L + I) mod M, where Z is a constant multiplier, I is a constant increment, and M is a constant modulus. For example, suppose Z is 7, I is 5, and M is 12. If the first random number (usually called the seed) is 4, then we can determine the next few pseudo-random numbers are follows:

Last Random Number, L | (Z×L+I) | Next Random Number, (Z×L+I) mod M
----------------------|---------|----------------------------------
4 | 33 | 9
9 | 68 | 8
8 | 61 | 1
1 | 12 | 0
0 | 5 | 5
5 | 40 | 4

As you can see, the sequence of pseudo-random numbers generated by this technique repeats after six numbers. It should be clear that the longest sequence that can be generated using this technique is limited by the modulus, M.

In this problem you will be given sets of values for Z, I, M, and the seed, L. Each of these will have no more than four digits. For each such set of values you are to determine the length of the cycle of pseudo-random numbers that will be generated. But be careful -- the cycle might not begin with the seed!

Input
Each input line will contain four integer values, in order, for Z, I, M, and L. The last line will contain four zeroes, and marks the end of the input data. L will be less than M.

Output
For each input line, display the case number (they are sequentially numbered, starting with 1) and the length of the sequence of pseudo-random numbers before the sequence is repeated.

Sample Input

7 5 12 4
5173 3849 3279 1511
9111 5309 6000 1234
1079 2136 9999 1237
0 0 0 0

Sample Output

Case 1: 6
Case 2: 546
Case 3: 500
Case 4: 220

21: Array(matrices) multiplication sequence

Problem :Optimal Array Multiplication Sequence

Given two arrays A and B, we can determine the array C = A B using the standard definition of matrix multiplication:

C(i,j) = SUM(A(i,k) x B(k,j))

The number of columns in the A array must be the same as the number of rows in the B array. Notationally, let's say that rows(A) and columns(A) are the number of rows and columns, respectively, in the A array. The number of individual multiplications required to compute the entire C array (which will have the same number of rows as A and the same number of columns as B) is then rows(A) columns(B) columns(A). For example, if A is a 10 × 20 array, and B is a 20 × 15 array, it will take 10 × 15 × 20, or 3000 multiplications to compute the C array.
To perform multiplication of more than two arrays we have a choice of how to proceed. For example, if X, Y, and Z are arrays, then to compute X Y Z we could either compute (X Y) Z or X (Y Z). Suppose X is a 5 × 10 array, Y is a 10 × 20 array, and Z is a 20 × 35 array. Let's look at the number of multiplications required to compute the product using the two different sequences:

(X × Y) × Z

* 5 × 20 × 10 = 1000 multiplications to determine the product (X × Y), a 5 × 20 array.
* Then 5 × 35 × 20 = 3500 multiplications to determine the final result.
* Total multiplications: 4500.

X × (Y × Z)

* 10 × 35 × 20 = 7000 multiplications to determine the product (Y × Z), a 10 × 35 array.
* Then 5 × 35 × 10 = 1750 multiplications to determine the final result.
* Total multiplications: 8750.

Clearly we'll be able to compute (X × Y) × Z using fewer individual multiplications.

Given the size of each array in a sequence of arrays to be multiplied, you are to determine an optimal computational sequence. Optimality, for this problem, is relative to the number of individual multiplcations required.

Input
For each array in the multiple sequences of arrays to be multiplied you will be given only the dimensions of the array. Each sequence will consist of an integer N which indicates the number of arrays to be multiplied, and then N pairs of integers, each pair giving the number of rows and columns in an array; the order in which the dimensions are given is the same as the order in which the arrays are to be multiplied. A value of zero for N indicates the end of the input. N will be no larger than 10.

Output
Assume the arrays are named A1, A2, ... AN. Your output for each input case is to be a line containing a parenthesized expression clearly indicating the order in which the arrays are to be multiplied. Prefix the output for each case with the case number (they are sequentially numbered, starting with 1). Your output should strongly resemble that shown in the samples shown below. If, by chance, there are multiple correct sequences, any of these will be accepted as a valid answer.

Sample Input

3
1 5
5 20
20 1

3
5 10
10 20
20 35

6
30 35
35 15
15 5
5 10
10 20
20 25

0

Sample Output

Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))

20.Run , Run Around Numbers

Problem :Run, Run, Runaround Numbers

An N-digit runaround number is characterized as follows:

* It is an integer with exactly N digits, each of which is between 1 and 9, inclusively.
* The digits form a sequence with each digit telling where the next digit in the sequence occurs. This is done by giving the number of digits to the right of the digit where the next digit in the sequence occurs. If necessary, counting wraps around from the rightmost digit back to the leftmost.
* The leftmost digit in the number is the first digit in the sequence, and the sequence must return to this digit after all digits in the number have been used exactly once.
* No digit will appear more than once in the number. This rule was accidentally left out of the problem description at the competition.

For example, consider the number 81362. To verify that this is a runaround number, we use the steps shown below:

1. Start with the leftmost digit, 8

8 1 3 6 2
-

2. Count 8 digits to the right, ending on 6 (note the wraparound).

8 1 3 6 2
- -

3. Count 6 digits to the right, ending on 2.

8 1 3 6 2
- - -

4. Count 2 digits to the right, ending on 1.

8 1 3 6 2
- - - -

5. Count 1 digit to the right, ending on 3.

8 1 3 6 2
- - - - -

6. Count 3 digits to the right, ending on 8, where we began.

8 1 3 6 2
= - - - -

In this problem you will be provided with one or more input lines, each with a single integer R having between 2 and 7 digits followed immediately by the end of line. For each such number, determine the smallest runaround number that is equal to or greater than R. There will always be such a number for each of the input numbers. Display the resulting number in the format illustrated below. The last line of the input will contain only the digit 0 in column 1.

Sample Input

12
123
1234
81111
82222
83333
911111
7654321
0

Sample Output

Case 1: 13
Case 2: 147
Case 3: 1263
Case 4: 81236
Case 5: 83491
Case 6: 83491
Case 7: 913425
Case 8: 8124956

19: WHATBASE() :) this problem was also given in Algorythm'09(csijmi) in Hello World c Prpgming event

Problem What Base Is This?
In positional notation we know the position of a digit indicates the weight of that digit toward the value of a number. For example, in the base 10 number 362 we know that 2 has the weight 100, 6 has the weight 101, and 3 has the weight 102, yielding the value 3 × 100 + 6 × 10 + 2 × 1, or just 300 + 60 + 2. The same mechanism is used for numbers expressed in other bases. While most people assume the numbers they encounter everyday are expressed using base 10, we know that other bases are possible. In particular, the number 362 in base 9 or base 14 represents a totally different value than 362 in base 10.

For this problem your program will presented with a sequence of pairs of integers. Let’s call the members of a pair X and Y. What your program is to do is determine the smallest base for X and the smallest base for Y (likely different from that for X) so that X and Y represent the same value.

Consider, for example, the integers 12 and 5. Certainly these are not equal if base 10 is used for each. But suppose 12 was a base 3 number and 5 was a base 6 number? 12 base 3 = 1 × 3 + 2 × 1, or 5 base 10, and certainly 5 in any base is equal to 5 base 10. So 12 and 5 can be equal, if you select the right bases for each of them!
Input
On each line of the input data there will be a pair of integers, X and Y, separated by one or more blanks; leading and trailing blanks may also appear on each line, are are to be ignored. The bases associated with X and Y will be between 1 and 36 (inclusive), and as noted above, need not be the same for X and Y. In representing these numbers the digits 0 through 9 have their usual decimal interpretations. The uppercase alphabetic characters A through Z represent digits with values 10 through 35, respectively. The last line of the input will contain nothing but zero or more blanks (and an end of line, of course), and represents the end of the data. There will be no incorrectly formatted data in the input.
Output
For each pair of integers in the input display a message similar to those shown in the examples shown below. Of course if the two integers cannot be equal regardless of the assumed base for each, then print an appropriate message; a suitable illustration is given in the examples.
Example Input

12 5
10 A
12 34
123 456
1 2
10 2
(blank)

Expected Output

12 (base 3) = 5 (base 6)
10 (base 10) = A (base 11)
12 (base 17) = 34 (base 5)
123 is not equal to 456 in any base 2..36
1 is not equal to 2 in any base 2..36
10 (base 2) = 2 (base 3)

18.Master Mind Hints Game

Problem - Master-Mind Hints
MasterMind is a game for two players. One of them, Designer, selects a secret code. The other, Breaker, tries to break it. A code is no more than a row of colored dots. At the beginning of a game, the players agree upon the length N that a code must have and upon the colors that may occur in a code.

In order to break the code, Breaker makes a number of guesses, each guess itself being a code. After each guess Designer gives a hint, stating to what extent the guess matches his secret code.

In this problem you will be given a secret code s1...sn and a guess g1...gn, and are to determine the hint. A hint consists of a pair of numbers determined as follows.

A match is a pair (i,j), 1<=i<=n and 1<=j<=n, such that si = gj. Match (i,j) is called strong when i = j, and is called weak otherwise. Two matches (i,j) and (p,q) are called independent when i = p if and only if j = q. A set of matches is called independent when all of its members are pairwise independent.

Designer chooses an independent set M of matches for which the total number of matches and the number of strong matches are both maximal. The hint then consists of the number of strong followed by the number of weak matches in M. Note that these numbers are uniquely determined by the secret code and the guess. If the hint turns out to be (n,0), then the guess is identical to the secret code.
Input
The input will consist of data for a number of games. The input for each game begins with an integer specifying N (the length of the code). Following these will be the secret code, represented as N integers, which we will limit to the range 1 to 9. There will then follow an arbitrary number of guesses, each also represented as N integers, each in the range 1 to 9. Following the last guess in each game will be N zeroes; these zeroes are not to be considered as a guess.

Following the data for the first game will appear data for the second game (if any) beginning with a new value for N. The last game in the input will be followed by a single zero (when a value for N would normally be specified). The maximum value for N will be 1000.
Output
The output for each game should list the hints that would be generated for each guess, in order, one hint per line. Each hint should be represented as a pair of integers enclosed in parentheses and separated by a comma. The entire list of hints for each game should be prefixed by a heading indicating the game number; games are numbered sequentially starting with 1. Separate the output for successive games using a blank line.
Example Input

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

10
1 2 2 2 4 5 6 6 6 9
1 2 3 4 5 6 7 8 9 1
1 1 2 2 3 3 4 4 5 5
1 2 1 3 1 5 1 6 1 9
1 2 2 5 5 5 6 6 6 7
0 0 0 0 0 0 0 0 0 0

0

Expected Output

Game 1:
(1,1)
(2,0)
(1,2)
(1,2)
(4,0)

Game 2:
(2,4)
(3,2)
(5,0)
(7,0)

17: Long Multiplication

Problem : Long Multiplication

In traditional "long multiplication" we determine the product of two integers, x and y, by multiplying x and the individual digits of y, in turn, starting with the units digit. The results of these multiplications are arranged appropriately and added, yielding the completed product.

The representation of these operations is usually done in a particular manner. Consider the multiplication of 123 by 95:

123
95
---
615
1107
-----
11685

The numbers to be multiplied, x and y, are each displayed on a separate line, followed by a horizontal line. The results of multiplying each digit of y by x are then displayed on separate lines, followed by another horizontal line, and then the final product. In this problem you are to perform a sequence of such multiplications, displaying the results in this traditional representation.
Input
Each line of the input data, except the last, will contain two integers, x and y, separated by whitespace (one or more blanks and tab characters). Whitespace may also precede the first integer and follow the second integer. Each integer will have no more than 10 digits. The last line of the input data will contain only whitespace, and marks the end of the input.
Output
For each pair of integers (that is, each input line except the last), perform the multiplication of x by y, displaying the results in the form shown above and in the examples shown below. Follow the output for each multiplication by a blank line. If y contains only a single significant digit, omit the second horizontal line and the sum (since in that case it would be superfluous). Display 0 digits only when they are significant.

The number of hyphens in the first horizontal line should be the same as the number of digits in the larger of x and y. The number of hyphens in the second horizontal line, if it is produced, should be the same as the number of digits in the product of x and y.
Example Input

4 7
135 46
12345 862
this line is blank

Expected Output

4
7
-
28

135
46
---
810
540
----
6210

12345
862
-----
24690
74070
98760
--------
10641390

16.PASSWORD

Problem : Easier Done than Said?
Password security is a tricky thing. Users prefer simple passwords that are easy to
remember (like buddy), but such passwords are often insecure. Some sites use random
computer-generated passwords (like xvtpzyo), but users have a hard time remembering
them and sometimes leave them written on notes stuck to their computer. One
potential solution is to generate "pronounceable" passwords that are relatively secure
but still easy to remember.

FnordCom is developing such a password generator. You work in the quality control
department, and it's your job to test the generator and make sure that the passwords
are acceptable. To be acceptable, a password must satisfy these three rules:
1. It must contain at least one vowel.
2. It cannot contain three consecutive vowels or three consecutive consonants.
3. It cannot contain two consecutive occurrences of the same letter, except for 'ee'
or 'oo'.

(For the purposes of this problem, the vowels are 'a', 'e', 'i', 'o', and 'u'; all other
letters are consonants.) Note that these rules are not perfect; there are many
common/pronounceable words that are not acceptable.

The input consists of one or more potential passwords, one per line, followed by a line
containing only the word 'end' that signals the end of the file. Each password is at
least one and at most twenty letters long and consists only of lowercase letters. For
each password, output whether or not it is acceptable, using the precise format shown
in the example.

Example input:
a
tv
ptoui
bontres
zoggax
wiinq
eep
houctuh
end

Example output:
"a" is acceptable.
"tv" is not acceptable.
"ptoui" is not acceptable.
"bontres" is not acceptable.
"zoggax" is not acceptable.
'wiinq" is not acceptable.
"eep" is acceptable.
"houctuh" is acceptable.

Picture : robot

----this one

15 Robots

Robot Motion:
A robot has been programmed to follow the instructions in its path. Instructions for the next direction the
robot is to move are laid down in a grid. The possible instructions are
north (up the page)
N
south (down the page)
S
east (to the right on the page)
E
west (to the left on the page)
W
For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path
the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid.
Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop
through 8 instructions, and never exits.
You are to write a program that determines how long it takes a robot to get out of the grid or how the
robot loops around.
There will be one or more grids for robots to navigate. The data for each is in the following form. On the
first line are three integers separated by blanks: the number of rows in the grid, the number of columns in
the grid, and the number of the column in which the robot enters from the north. The possible entry
columns are numbered starting with one at the left. Then come the rows of the direction instructions.
Each grid will have at least one and at most 10 rows and columns of instructions. The lines of
instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a
row containing 0 0 0.
For each grid in the input there is one line of output. Either the robot follows a certain number of
instructions and exits the grid on any one the four sides or else the robot follows the instructions on a
certain number of locations once, and then the instructions on some number of locations repeatedly. The
sample input below corresponds to the two grids above and illustrates the two forms of output. The word "step" is always immediately followed by "(s)" whether or not the number before it is 1.
Example input:
3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0
Example output:
10 step(s) to exit
3 step(s) before a loop of 8 step(s)

14. Basically Speaking

The Really Neato Calculator Company, Inc. has recently hired your team to help design their Super Neato Model I calculator. As a computer scientist you suggested to the company that it would be neato if this new calculator could convert among number bases. The company thought this was a stupendous idea and has asked your team to come up with the prototype program for doing base conversion. The project manager of the Super Neato Model I calculator has informed you that the calculator will have the following neato features:

It will have a 7-digital display.
Its buttons will include the capital letters A through F in addition to the digits 0 through 9.
It will support bases 2 through 16.

The input for your prototype program will consist of one base conversion per line. There will be three numbers per line. The first number will be the number in the base you are converting from. The second number is the base you are converting from. The third number is the base you are converting to. There will be one or more blanks surrounding (on either side of) the numbers. There are several lines of input and your program should continue to read until the end of file is reached.

The output will only be the converted number as it would appear on the display of the calculator. The number should be right justified in the 7-digit display. If the number is to large to appear on the display, then print ``ERROR'' (without the quotes) right justified in the display.

A sample input file is shown here:

1111000  2 10
1111000  2 16
2102101  3 10
2102101  3 15
 12312  4  2
    1A 15  2
1234567 10 16
  ABCD 16 15

The following output file should be produced from the above sample input:

13 perfect cubes

PERFECT CUBES:

For hundreds of years Fermat's Last Theorem, which stated simply that for n > 2 there exist no integers a, b, c > 1 such that a^n = b^n + c^n, has remained elusively unproven. (A recent proof is believed to be correct, though it is still undergoing scrutiny.) It is possible, however, to find integers greater than 1 that satisfy the "perfect cube" equation a^3 = b^3 + c^3 + d^3 (e.g. a quick calculation will show that the equation 12^3 = 6^3 + 8^3 + 10^3 is indeed true). This problem requires that you write a program to find all sets of numbers {a,b,c,d} which satisfy this equation for a <= 100.

The output should be listed as shown below, one perfect cube per line, in non-decreasing order of a (i.e. the lines should be sorted by their a values). The values of b, c, and d should also be listed in non-decreasing order on the line itself. There do exist several values of a which can be produced from multiple distinct sets of b, c, and d triples. In these cases, the triples with the smaller b values should be listed first.

Note that the programmer will need to be concerned with an efficient implementation. The official time limit for this problem is 2 minutes, and it is indeed possible to write a solution to this problem which executes in under 2 minutes on a 33 MHz 80386 machine. Due to the distributed nature of the contest in this region, judges have been instructed to make the official time limit at their site the greater of 2 minutes or twice the time taken by the judge's solution on the machine being used to judge this problem.

The first part of the output is shown here:

Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)

12: perfection

Problem 6: Perfection

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, 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."

Problem Statement:  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 .

Example:   The following input data:

15 28 6 56 60000 22 496 0

should produce the following output:

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

Pno -11 Sum

look at the image for problem

sample output:

370370367037037036703703703670

Saturday, June 20, 2009

PNo-10 very good one..............

Palindroms ! smordnilaP

The following problem deals with Palindroms composed of digits. A number is a palin-
drom, if the sequence of signs (digits or characters) read from left to right and read from
right to left are identical. Now, given the number 65 with base 10, adding the number
read from right to left , that means 56, leads to 121. By denition 121 is a palindrom.
With another number you might have to repeat this step until the sum is of the required
palindrom form. eg. 87:
87 + 78 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884
The number of steps is 4.
This works in any base with any number. Naturally the number of steps increases incred-
ibly fast, so there exist numbers in base 10 that requires more than 10’000 steps. You
will have to nd the numbers of steps of a given number in all the bases 15 down to 2.
When a Number is in an illegal form in a base, the number of Steps will be represented
by a "?".
Example:

Base 15 87 + 78 = 110
110 + 011 = 121 2 steps
Base 14 87 + 78 = 111 1 step
Base 13 87 + 78 = 132
132 + 231 = 363 2 steps
Base 12 87 + 78 = 143

143 + 341 = 484 2 steps
Base 11 87 + 78 = 154
154 + 451 = 5A5 2 steps
Base 10 87 + 78 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884 4 steps
Base 9 87 + 78 = 176
176 + 671 = 857
857 + 758= 1726
1762+ 2671 = 7543
7543 + 3457 = 12111
12111 + 11121 = 23232 6 steps
Base 8 87 + 78 = 207
207 + 702 = 1111 2 steps
Base 7 illegal ? steps
Base 6 illegal ? steps
Base 5 illegal ? steps
Base 4 illegal ? steps
Base 3 illegal ? steps
Base 2 illegal ? steps
For the above example, the Files would look like this:
Inputle:
87
Outputle:
2 1 2 2 2 4 6 2 ? ? ? ? ? ?

PNo-9 Word Index

Word Index

Encoding schemes are often used in situations requiring encryption or information storage/transmission
economy. Here, we develop a simple encoding scheme that encodes particular types of words with five or
fewer (lower case) letters as integers.
Consider the English alphabet {a,b,c,...z}. Using this alphabet, a set of valid words are to be formed that
are in a strict lexicographic order. In this set of valid words, the successive letters of a word are in a strictly
ascending order; that is, later letters in a valid word are always after previous letters with respect to their
positions in the alphabet list {a,b,c...,z}. For example,

abc aep gwz
are all valid three-letter words, whereas

aab are cat
are not.

For each valid word associate an integer which gives the position of the word in the alphabetized list of
words. That is:
a → 1
b → 2
.
.
z → 26
ab → 27
ac → 28
.
.
az → 51
bc → 52
.
.
vwxyz → 83681
Your program is to read a series of input lines. Each input line will have a single word on it, that will be
from one to five letters long. For each word read, if the word is invalid give the number 0. If the word read

is valid, give the word’s position index in the above alphabetical list.

INPUT
The input consists of a series of single words, one per line. The words are at least one letter long and no
more that five letters. Only the lower case alphabetic {a,b,...,z} characters will be used as input. The first
letter of a word will appear as the first character on an input line.
The input will be terminated by end-of-file.

OUTPUT
The output is a single integer, greater than or equal to zero (0) and less than or equal 83681. The first digit
of an output value should be the first character on a line. Note: This may not be a default-format. There is
one line of output for each input line.

EXAMPLE
Input File
Output File
z
26
a
1
cat
0
vwxyz
83681

P. No-8 Hamming Distance....

Hamming Distance:
The Hamming distance between two strings of bits (binary integers) is the number of corresponding bit positions that differ. This can be found by using XOR on corresponding bits or equivalently, by adding corresponding bits (base 2) without a carry. For example, in the two bit strings that follow:

A 0 1 0 0 1 0 1 0 0 0
B 1 1 0 1 0 1 0 1 0 0
A XOR B = 1 0 0 1 1 1 1 1 0 0

The Hamming distance (H) between these 10-bit strings is 6, the number of 1's in the XOR string.
Input
N, the length of the bit strings and H, the Hamming distance.
Output
A list of all possible bit strings of length N that are Hamming distance H from the bit string containing all 0's (origin). That is, all bit strings of length N with exactly H 1's. The number of such bit strings is equal to the combinatorial symbol C(N, H). This is the number of possible combinations of N-H zeros and H ones. It is equal to
N! (N-H)! H!

This number can be very large. The program should work for 1<=N<=10 and 1<=H<=10.
Sample
For N=4 and H=2 the output should contain all of the following bit strings (order is unimportant):

0011
0101
0110
1001
1010
1100

C(4, 2) is 6.

P.No-7 reverse words

Word Reversal

Input:
happy coding
everest is masala,
i studied it to be mountain

output:
yppah ngidoc
tsereve si ,alasam
i deiduts ti ot eb niatnuom

P.No-6 Y2K accounting Bug

Y2K Accounting Bug

Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc.

All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.

Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.

Input is a sequence of lines, each containing two positive integers s and d. For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.
Sample input

59 237
375 743
200000 849694
2500000 8000000

Output for sample input

116
28
300612
Deficit

P.No-5 TUG OF WAR

Tug of War

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

The first line of input contains n the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 450. There are at most 100 people at the picnic.

Your output will be a single line containing 2 numbers: the total weight of the people on one team, and the total weight of the people on the other team. If these numbers differ, give the lesser first.
Sample Input

3
100
90
200

Output for Sample Input

190 200

Ye problem mere naam se match karta hai...

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.

Each line of input contains an integer n < 3000 followed by n integers representing the sequence. 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

Output for Sample Input

Jolly
Not jolly

Interesing problem..........

Problem : Alphabetization

Write a program that prints exactly the sample output shown below. There is no input.
Sample Input
none
Sample Output

The quick brown fox jumps over the laxy dog.

P.No-4"ARITHMATIC"

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.

Each line of input contains two unsigned integers less than 10 digits. The last line of input contains 0 0. 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

123 456
555 555
123 594
0 0

Output for Sample Input

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

P.No.3 Division

Division

Given t, a, b positive integers not bigger than 2147483647, establish whether (t^a - 1)/(t^b -1) is an integer with less than 100 digits. Each line of input contains t, a, b. For each line of input print the formula followed by its value, or followed by "is not an integer with less than 100 digits.", whichever is appropriate.
Sample Input

2 9 3
2 3 2
21 42 7
123 911 1

Output For Sample Input

(2^9-1)/(2^3-1) 73
(2^3-1)/(2^2-1) is not an integer with less than 100 digits.
(21^42-1)/(21^7-1) 18952884496956715554550978627384117011154680106
(123^911-1)/(123^1-1) is not an integer with less than 100 digits.

P. No 2

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

Challenging Work(){}

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 >= n. Each line of input contains one integer number n. For each line of input output one line either

Stan wins.

or

Ollie wins.

assuming that both of them play perfectly.
Sample input

162
17
34012226

Output for sample input

Stan wins.
Ollie wins.
Stan wins.

Saturday, June 27, 2009

Marks Distribution

The Problem

The Input

The Output

Sample Input

Sample Output

Input Specification

Output Specification

Sample Input

Sample Output

Thursday, June 25, 2009

Wednesday, June 24, 2009

Monday, June 22, 2009

Sunday, June 21, 2009

Problem : Interpreter

Input

Output

Sample Input

Sample Output

Problem : Graphical Editor

Input

Output

Errors

Sample Input

Sample Output

Alexander Denisjuk, 2002

Problem : Stack 'em Up

Input

Output

Sample Input

Output for Sample Input

Problem : The Trip

The Input

The Output

Sample Input

Output for Sample Input

Saturday, June 20, 2009

Vistors Counter

AddThis

programmer

GanuraG