Maths

113 - Power of Cryptography

Background

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

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

The Problem

Given an integer and an integer you are to write a program that determines , the positive root of p. In this problem, given such integers n and p, p will always be of the form for an integer k (this integer is what your program must find).

The Input

The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs , and there exists an integer k, such that .

The Output

For each integer pair n and p the value should be printed, i.e., the number k such that .

Sample Input

2

16

3

27

7

4357186184021382204544

Sample Output

4

3

1234

10161 - Ant on a Chessboard

Background

One day, an ant called Alice came to an M*M chessboard. She wanted to go around all the grids. So she began to walk along the chessboard according to this way: (you can assume that her speed is one grid per second)

At the first second, Alice was standing at (1,1). Firstly she went up for a grid, then a grid to the right, a grid downward. After that, she went a grid to the right, then two grids upward, and then two grids to the left…in a word, the path was like a snake.

For example, her first 25 seconds went like this:

( the numbers in the grids stands for the time when she went into the grids)

25

24

23

22

21

10

11

12

13

20

9

8

7

14

19

2

3

6

15

18

1

4

5

16

17

5

4

3

2

1

1 2 3 4 5

At the 8th second , she was at (2,3), and at 20th second, she was at (5,4).

Your task is to decide where she was at a given time.

(you can assume that M is large enough)

Input

Input file will contain several lines, and each line contains a number N(1<=N<=2*10^9), which stands for the time. The file will be ended with a line that contains a number 0.

Output

For each input situation you should print a line with two numbers (x, y), the column and the row number, there must be only a space between them.

Sample Input

8

20

25

0

Sample Output

2 3

5 4

1 5

253 - Cube painting

We have a machine for painting cubes. It is supplied with three different colors: blue, red and green. Each face of the cube gets one of these colors. The cube's faces are numbered as in Figure 1.

Figure 1.

Since a cube has 6 faces, our machine can paint a face-numbered cube in different ways. When ignoring the face-numbers, the number of different paintings is much less, because a cube can be rotated. See example below. We denote a painted cube by a string of 6 characters, where each character is a b, r, or g. The character ( ) from the left gives the color of face i. For example, Figure 2 is a picture of rbgggr and Figure 3 corresponds to rggbgr. Notice that both cubes are painted in the same way: by rotating it around the vertical axis by 90 , the one changes into the other.

Input

The input of your program is a textfile that ends with the standard end-of-file marker. Each line is a string of 12 characters. The first 6 characters of this string are the representation of a painted cube, the remaining 6 characters give you the representation of another cube. Your program determines whether these two cubes are painted in the same way, that is, whether by any combination of rotations one can be turned into the other. (Reflections are not allowed.)

Output

The output is a file of boolean. For each line of input, output contains TRUE if the second half can be obtained from the first half by rotation as describes above, FALSE otherwise.

Sample Input

rbgggrrggbgr

rrrbbbrrbbbr

rbgrbgrrrrrg

Sample Output

TRUE

FALSE

FALSE

621 - Secret Research

At a certain laboratory results of secret research are thoroughly encrypted. A result of a single experiment is stored as an information of its completion:

`positive result', `negative result', `experiment failed' or `experiment not completed'

The encrypted result constitutes a string of digits S, which may take one of the following forms:

positive result S = 1 or S = 4 or S = 78

negative result S = S35

experiment failed S = 9S4

experiment not completed S = 190S

(A sample result S35 means that if we add digits 35 from the right hand side to a digit sequence then we shall get the digit sequence corresponding to a failed experiment)

You are to write a program which decrypts given sequences of digits.

Input

A integer n stating the number of encrypted results and then consecutive n lines, each containing a sequence of digits given as ASCII strings.

Output

For each analysed sequence of digits the following lines should be sent to output (in separate lines):

+ for a positive result

- for a negative result

* for a failed experiment

? for a not completed experiment

In case the analysed string does not determine the experiment result, a first match from the above list should be outputted.

Sample Input

4

78

7835

19078

944

Sample Output

+

-

?

*

10025 - The ? 1 ? 2 ? ... ? n = k

The problem

Given the following formula, one can set operators '+' or '-' instead of each '?', in order to obtain a given k

? 1 ? 2 ? ... ? n = k

For example: to obtain k = 12 , the expression to be used will be:

- 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12

with n = 7

The Input

The first line is the number of test cases, followed by a blank line.

Each test case of the input contains integer k (0<=|k|<=1000000000).

Each test case will be separated by a single line.

The Output

For each test case, your program should print the minimal possible n (1<=n) to obtain k with the above formula.

Print a blank line between the outputs for two consecutive test cases.

Sample Input

2

12

-3646397

Sample Output

7

2701

591 - Box of Bricks

Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. ``Look, I've built a wall!'', he tells his older sister Alice. ``Nah, you should make all stacks the same height. Then you would have a real wall.'', she retorts. After a little con- sideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?

Input

The input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights hi of the n stacks. You may assume and .

The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height.

The input is terminated by a set starting with n = 0. This set should not be processed.

Output

For each set, first print the number of the set, as shown in the sample output. Then print the line ``The minimum number of moves is k.'', where k is the minimum number of bricks that have to be moved in order to make all the stacks the same height.

Output a blank line after each set.

Sample Input

6

5 2 4 1 7 5

0

Sample Output

Set #1

The minimum number of moves is 5.

107 - The Cat in the Hat

Background

(An homage to Theodore Seuss Geisel)

The Cat in the Hat is a nasty creature,

But the striped hat he is wearing has a rather nifty feature.

With one flick of his wrist he pops his top off.

Do you know what's inside that Cat's hat?

A bunch of small cats, each with its own striped hat.

Each little cat does the same as line three,

All except the littlest ones, who just say ``Why me?''

Because the littlest cats have to clean all the grime,

And they're tired of doing it time after time!

The Problem

A clever cat walks into a messy room which he needs to clean. Instead of doing the work alone, it decides to have its helper cats do the work. It keeps its (smaller) helper cats inside its hat. Each helper cat also has helper cats in its own hat, and so on. Eventually, the cats reach a smallest size. These smallest cats have no additional cats in their hats. These unfortunate smallest cats have to do the cleaning.

The number of cats inside each (non-smallest) cat's hat is a constant, N. The height of these cats-in-a-hat is times the height of the cat whose hat they are in.

The smallest cats are of height one;

these are the cats that get the work done.

All heights are positive integers.

Given the height of the initial cat and the number of worker cats (of height one), find the number of cats that are not doing any work (cats of height greater than one) and also determine the sum of all the cats' heights (the height of a stack of all cats standing one on top of another).

The Input

The input consists of a sequence of cat-in-hat specifications. Each specification is a single line consisting of two positive integers, separated by white space. The first integer is the height of the initial cat, and the second integer is the number of worker cats.

A pair of 0's on a line indicates the end of input.

The Output

For each input line (cat-in-hat specification), print the number of cats that are not working, followed by a space, followed by the height of the stack of cats. There should be one output line for each input line other than the ``0 0'' that terminates input.

Sample Input

216 125

5764801 1679616

0 0

Sample Output

31 671

335923 30275911

573 - The Snail

A snail is at the bottom of a 6-foot well and wants to climb to the top. The snail can climb 3 feet while the sun is up, but slides down 1 foot at night while sleeping. The snail has a fatigue factor of 10%, which means that on each successive day the snail climbs 10% 3 = 0.3 feet less than it did the previous day. (The distance lost to fatigue is always 10% of the first day's climbing distance.) On what day does the snail leave the well, i.e., what is the first day during which the snail's height exceeds 6 feet? (A day consists of a period of sunlight followed by a period of darkness.) As you can see from the following table, the snail leaves the well during the third day.

Day Initial Height Distance Climbed Height After Climbing Height After Sliding

1 0' 3' 3' 2'

2 2' 2.7' 4.7' 3.7'

3 3.7' 2.4' 6.1' -

Your job is to solve this problem in general. Depending on the parameters of the problem, the snail will eventually either leave the well or slide back to the bottom of the well. (In other words, the snail's height will exceed the height of the well or become negative.) You must find out which happens first and on what day.

Input

The input file contains one or more test cases, each on a line by itself. Each line contains four integers H, U, D, and F, separated by a single space. If H = 0 it signals the end of the input; otherwise, all four numbers will be between 1 and 100, inclusive. H is the height of the well in feet, U is the distance in feet that the snail can climb during the day, D is the distance in feet that the snail slides down during the night, and F is the fatigue factor expressed as a percentage. The snail never climbs a negative distance. If the fatigue factor drops the snail's climbing distance below zero, the snail does not climb at all that day. Regardless of how far the snail climbed, it always slides D feet at night.

Output

For each test case, output a line indicating whether the snail succeeded (left the well) or failed (slid back to the bottom) and on what day. Format the output exactly as shown in the example.

Sample Input

6 3 1 10

10 2 1 50

50 5 3 14

50 6 4 1

50 6 3 1

1 1 1 1

0 0 0 0

Sample Output

success on day 3

failure on day 4

failure on day 7

failure on day 68

success on day 20

failure on day 2

846 – Steps

One steps through integer points of the straight line. The length of a step must be nonnegative and can be by one bigger than, equal to, or by one smaller than the length of the previous step.

What is the minimum number of steps in order to get from x to y? The length of the first and the last step must be 1.

Input and Output

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

Sample Input

3

45 48

45 49

45 50

Sample Output

3

3

4

10499 - The Land of Justice

Input: standard input

Output: standard output

Time Limit: 4 seconds

In the Land of Justice the selling price of everything is fixed all over the country. Nobody can buy a thing and sell it in double price. But, that created problems for the businessmen. They left their business and went to the production. So, after some days everybody was in production and nobody in business. And the people didn’t get their necessary things though the country was self-sufficient in every sector.

The government became very much anxious. But, they were intelligent enough to call the mathematicians.

The mathematicians gave a solution.  They suggested setting the surface area of an object as its selling-unit instead of its volume. Actually the clever mathematicians were very much interested to establish their own business.

Now, the government asks the programmers to build the software that would calculate the profit things.

Here your job is to calculate the business profit for a solid sphere. A businessman buys a complete sphere and to maximize his profit he divides it in n equal parts. All cut should go through the axis of the sphere. And every part should look like the picture below:

Input

You are given a sequence of integers N (0 < N < 231), indicating the numbers of parts of the sphere. The input file is terminated with a negative number. This number should not be processed.

Output

Calculate the profit over the sold pieces. The result should be in percentage and rounded to the nearest integer.

Sample input

2

2

-1

Sample output

50%

50%

10790 - How Many Points of Intersection?

We have two rows. There are a dots on the top row and b dots on the bottom row. We draw line segments connecting every dot on the top row with every dot on the bottom row. The dots are arranged in such a way that the number of internal intersections among the line segments is maximized. To achieve this goal we must not allow more than two line segments to intersect in a point. The intersection points on the top row and the bottom are not included in our count; we can allow more than two line segments to intersect on those two rows. Given the value of a and b, your task is to compute P(a, b), the number of intersections in between the two rows. For example, in the following figure a = 2 and b = 3. This figure illustrates that P(2, 3) = 3.

Input

Each line in the input will contain two positive integers a ( 0 < a20000) and b ( 0 < b20000). Input is terminated by a line where both a and b are zero. This case should not be processed. You will need to process at most 1200 sets of inputs.

Output

For each line of input, print in a line the serial of output followed by the value of P(a, b). Look at the output for sample input for details. You can assume that the output for the test cases will fit in 64-bit signed integers.

Sample Input

2 2

2 3

3 3

0 0

Sample Output

Case 1: 1

Case 2: 3

Case 3: 9

11044 - Searching for Nessy

The Loch Ness Monsteris a mysterious and unidentified animal said to inhabit Loch Ness,

a large deep freshwater loch near the city of Inverness in northern Scotland. Nessie is usually categorized as a type of lake monster.

http://en.wikipedia.org/wiki/Loch_Ness_Monster

In July 2003, the BBC reported an extensive investigation of Loch Ness by a BBC team, using 600 separate sonar beams, found no trace of any ¨sea monster¨ (i.e., any large animal, known or unknown) in the loch. The BBC team concluded that Nessie does not exist. Now we want to repeat the experiment.

Given a grid of n rows and m columns representing the loch, 6n, m10000, find the minimum number s of sonar beams you must put in the square such that we can control every position in the grid, with the following conditions:

one sonar occupies one position in the grid; the sonar beam controls its own cell and the contiguous cells;

the border cells do not need to be controlled, because Nessy cannot hide there (she is too big).

For example,

where X represents a sonar, and the shaded cells are controlled by their sonar beams; the last figure gives us a solution.

Input

The first line of the input contains an integer, t, indicating the number of test cases. For each test case, there is a line with two numbers separated by blanks, 6n, m10000, that is, the size of the grid (n rows and m columns).

Output

For each test case, the output should consist of one line showing the minimum number of sonars that verifies the conditions above.

Sample Input

3

6 6

7 7

9 13

Sample Output

4

4

12

10719 - Quotient Polynomial

A polynomial of degree n can be expressed as

If k is any integer then we can write:

Here q(x) is called the quotient polynomial of p(x) of degree(n-1) and r is any integer which is called the remainder.

For example, if p(x) = x3 - 7x2+ 15x - 8 and k = 3 then q(x) = x2- 4x + 3 and r = 1. Again if p(x) = x3 - 7x2+ 15x - 9 and k = 3then q(x) = x2 - 4x + 3 and r = 0.

In this problem you have to find the quotient polynomial q(x) and the remainder r. All the input and output data will fit in 32-bit signed integer.

Input

Your program should accept an even number of lines of text. Each pair of line will represent one test case. The first line will contain an integer value for k. The second line will contain a list of integers (an, an-1, … a0), which represent the set of co-efficient of a polynomial p(x). Here 1 ≤ n ≤ 10000. Input is terminated by .

Output

For each pair of lines, your program should print exactly two lines. The first line should contain the coefficients of the quotient polynomial. Print the reminder in second line. There is a blank space before and after the ‘=’ sign. Print a blank line after the output of each test case. For exact format, follow the given sample.

10177 - (2/3/4)-D Sqr/Rects/Cubes/Boxes?

You can see a (4x4) grid below. Can you tell me how many squares and rectangles are hidden there? You can assume that squares are not rectangles. Perhaps one can count it by hand but can you count it for a (100x100) grid or a (10000x10000) grid. Can you do it for higher dimensions? That is can you count how many cubes or boxes of different size are there in a (10x10x10) sized cube or how many hyper-cubes or hyper-boxes of different size are there in a four-dimensional (5x5x5x5) sized hypercube. Remember that your program needs to be very efficient. You can assume that squares are not rectangles, cubes are not boxes and hyper-cubes are not hyper-boxes. 

Input

The input contains one integer N (0<=N<=100) in each line, which is the length of one side of the grid or cube or hypercube. As for the example above the value of N is 4. There may be as many as 100 lines of input.

Output

For each line of input, output six integers S2, R2, S3, R3, S4, R4 in a single line where S2 means no of squares of different size in ( NxN) two-dimensional grid, R2 means no of rectangles of different size in(NxN) two-dimensional grid. S3, R3, S4, R4 means similar cases in higher dimensions as described before.  

Sample Input:

1

2

3

Sample Output:

1 0 1 0 1 0

5 4 9 18 17 64

14 22 36 180 98 1198

10916 - Factstone Benchmark

Amtel has announced that it will release a 128-bit computer chip by 2010, a 256-bit computer by 2020, and so on, continuing its strategy of doubling the word-size every ten years. (Amtel released a 64-bit computer in 2000, a 32-bit computer in 1990, a 16-bit computer in 1980, an 8-bit computer in 1970, and a 4-bit computer, its first, in 1960.)

Amtel will use a new benchmark - the Factstone - to advertise the vastly improved capacity of its new chips. The Factstone rating is defined to be the largest integer n such that n! can be represented as an unsigned integer in a computer word.

Given a year 1960 ≤ y ≤ 2160, what will be the Factstone rating of Amtel's most recently released chip?

There are several test cases. For each test case, there is one line of input containing y. A line containing 0 follows the last test case. For each test case, output a line giving the Factstone rating.

Sample Input

1960

1981

0

Output for Sample Input

3

8

10970 - Big Chocolate

Mohammad has recently visited Switzerland. As he loves his friends very much, he decided to buy some chocolate for them, but as this fine chocolate is very expensive(You know Mohammad is a little BIT stingy!), he could only afford buying one chocolate, albeit a very big one (part of it can be seen in figure 1) for all of them as a souvenir. Now, he wants to give each of his friends exactly one part of this chocolate and as he believes all human beings are equal (!), he wants to split it into equal parts.

The chocolate is an rectangle constructed from unit-sized squares. You can assume that Mohammad has also friends waiting to receive their piece of chocolate.

To split the chocolate, Mohammad can cut it in vertical or horizontal direction (through the lines that separate the squares). Then, he should do the same with each part separately until he reaches unit size pieces of chocolate. Unfortunately, because he is a little lazy, he wants to use the minimum number of cuts required to accomplish this task.

Your goal is to tell him the minimum number of cuts needed to split all of the chocolate squares apart.

Figure 1. Mohammad’s chocolate

The Input

The input consists of several test cases. In each line of input, there are two integers , the number of rows in the chocolate and , the number of columns in the chocolate. The input should be processed until end of file is encountered.

The Output

For each line of input, your program should produce one line of output containing an integer indicating the minimum number of cuts needed to split the entire chocolate into unit size pieces.

Sample Input

2 2

1 1

1 5

Sample Output

3

0

4

10014 - Simple calculations

There is a sequence of n+2 elements a0, a1,…, an+1 (n <= 3000; -1000 <= ai 1000). It is known that ai = (ai–1 + ai+1)/2 – ci for each i=1, 2, ..., n. You are given a0, an+1, c1, ... , cn. Write a program which calculates a1.

The Input

The first line is the number of test cases, followed by a blank line.

For each test case, the first line of an input file contains an integer n. The next two lines consist of numbers a0 and an+1 each having two digits after decimal point, and the next n lines contain numbers ci (also with two digits after decimal point), one number per line.

Each test case will be separated by a single line.

The Output

For each test case, the output file should contain a1 in the same format as a0 and an+1.

Print a blank line between the outputs for two consecutive test cases.

Sample Input

1

1

50.50

25.50

10.15

Sample Output

27.85

maths 算法竞赛入门经典 刘汝佳