Description

Bessie has returned to 8th grade in order to finish her diploma.
Her cruel math teacher wants the students to calculate "powers of integers". An integer power is the resultant integer when some number N (1 <= N <= 2,000,000,000) is multiplied by itself over and over P times (1 <= P <= 100,000).

By way of example, 2 to the power 3 = 2 * 2 * 2 (three times) = 8. Similarly, 123456 to the power 88 = 123456 * 123456 * ... * 123456 (88 times) =

1129987770413559019467963153621658978635389622595924947762339599136126
3387265547320084192414348663697499847610072677686227073640285420809119
1376617325522768826696494392126983220396307144829544079751988205731569
1498433718478969549886325738202371569900214092289842856905719188890170
0772424218248094640290736200969188059104939824466416330655204270246371
3699112106518584413775333247720509274637795508338904731884172716714194
40898407102819460020873199616

when printed 70 digits per line.

Write a program to calculate the Pth power of an integer N. The answer is guaranteed to be no longer than 15,000 digits. Print your answer 70 digits per line (except the last line which might be shorter). Do not print leading zeroes, of course.

Input

* Line 1: Two space-separated integers: N and P

Output

* Lines 1..?: A single integer that is the result of the calculation.
Print 70 digits per line except potentially for the last line, which might be shorter.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

As if powers of numbers were not cruel enough, Bessie's cruel math teacher has created yet another cruel assignment: Find the 'root' or 'zero' of a polynomial. All of these polynomials have a highest degree D (1 <= D <= 11) that is odd and have but a single solution in the range -1,000,000 <= X <= 1,000,000; for that solution, the polynomial's value when evaluated for X is very close or equal to to 0 in computer math.

Given a polynomial with real number coefficients (-500 <= coef_i <= 500), find a value of X that is within 0.0005 of the value of X that will yield 0 when the polynomial is evaluated. Multiply that value of X by 1,000 and print it as an (unrounded) integer.

By way of example, consider the cubic polynomial problem 1.5*x*x*x - 10 = 0. Astute algebra students will quickly recognize a solution for this as x*x*x = 100/15 = 20/3 = 6.66666. To five decimal places, the exactly solution is 1.88207. For this task, the proper output would be 1882.

The polynomial is expressed as the sum from i=0..D of coef_i*x^i (where x^i means x to the i-th power).
No answer will require more than six significant digits and each answer will be small enough that it is able to be incremented by 0.0001 in the 'double' precision floating point datatype  without losing lots of precision.

HINT: Find a strategy to narrow the search space each time you choose a new X value as a guess.

NOTE: Your first 50 submissions will report results of more test cases than just the first one.

Input

* Line 1: A single integer: D
* Lines 2..D+2: Line i+2 contains a single real number: coef_i

Output

* Line 1: A single integer that is the truncated product of 1,000 and the X value that is closest to the X value that causes the polynomial to evaluate to 0

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Like everyone else on their vacation, the cows play the cow version of the word game called Boggle: Coggle. It's a similar game where 25 letter dice are rolled into a matrix like this one:

Z C C D X
K Q M N B
U O W Z Y
F C O I J
P A Q Z T

Words are made (and thus points scored) by starting at some letter and proceeding to one of its (as many as) eight neighbors, etc.
until the successive letters spell out a word from a dictionary In the matrix above, the lower 'C' can be used to form the words "CAP", "COW", and "COOK" (but not "COD" or "PACK"). The complete list of dictionary words for the above square is: "CAP", "COOK", "COW", "OWN", "WIT", "WOO", "ZOO", and "ZOOM".

Your program should read the dictionary from file dict.txt (which is alphabetized and has fewer than 25,000 words; each word is no longer than 20 characters). The actual dictionary contents can be inspected at http://ace.delos.com/usaco/dict.txt.

Help Bessie see how good she can do. Read in five rows of five letters that represent the dice and see how many words from the dictionary can be formed. Don't use any given die's letter twice in the same word.

Count the number of words that can be formed (a number that might well be smaller than the number of ways a word a can be formed since words might be formed in more than one way).

Input

* Lines 1..5: Line i contains five space-separated upper-case letters that are row i

Output

* Line 1: A single integer that is the number of words in the dictionary that can be formed using the described rules

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Imagine Bessie's surprise as she spied a leprechaun prancing through the north pasture. Being no one's fool, she charged at the leprechaun at captured him with her prehensile hooves.

"One wish, bovine one. That's all I have for cows," he said.

"Riches," Bessie said dreamily. "The opportunity for riches."

Leprechauns never grant precisely the easiest form of their captor's wishes. As the smoke cleared from the location of a loud explosion, a shimmering donut spun slowly over the verdant green fields.

"I have made you a torus," the leprechaun cooed. "And on that torus is an N x N matrix (1 <= N <= 200) of integers in the range -1,000,000..1,000,000 that will determine the magnitude of your riches. You must find the sequence of contiguous integers all in one row, one column, or on one diagonal that yields the largest sum from among all the possible sequences on the torus."

Bessie pondered for a moment and realized that the torus was a device for "wrapping" the columns, rows, and diagonals of a matrix so that one could choose contiguous elements that "wrapped around" the side or top edge.

Bessie will share the matrix with you. Determine the value of the largest possible sum (which requires choosing at least one matrix element).

By way of example, consider the 4 x 4 matrix on the left below that has all the elements from one exemplary "wrapped" diagonal marked:

           8  6  6* 1           8  6* 6  1
          -3  4  0  5*         -3  4  0  5
           4* 2  1  9           4  2  1  9*
           1 -9* 9 -2           1 -9  9*-2

The marked diagonal of the right-hand matrix includes two nines (the highest available number) and a six for a total of 24. This is the best possible sum for this matrix and includes only three of the four possible elements on its diagonal.

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains N space-separated integers that compose row i of the matrix

Output

* Line 1: A single integer that is the largest possible sum computable using the rules above

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Farmer John has bought property in the Caribbean and is going to try to raise dairy cows on a big farm composed of islands. Set in his ways, he wants to surround all the islands with fence.

Each island in the farm has the shape of a polygon. He fences the islands one side at a time (between a consecutive pair of vertices) and proceeds clockwise around a given island with his fencing operations. Since he wants to fence all the islands, he must at some point travel to any other islands using a boat.

He can start fencing at any vertex and, at any vertex he encounters, travel to some vertex on another island, fence all the way around it, and then IMMEDIATELY return back to the same vertex on the original island using the same path he traveled before. Each boat trip has a cost defined by a supplied matrix.

The islands are described by a set of N (3 <= N <= 500) pairs of vertices V1,V2 (1 <= V1 <= N; 1 <= V2 <= N) although you must figure out how to assemble them into islands. The vertices are conveniently  numbered 1..N.

The cost of traveling by boat between each pair of vertices is given by a symmetric cost matrix whose elements fall in the range 0..1000.
What is the minimum cost of surrounding the islands with the fence?

Input

* Line 1: A single integer: N

* Lines 2..N+1: Each line describes an island's border with two space-separated integers: V1 and V2

* Lines N+2..2*N+1: Line i-N-1 contains N integers that describe row i of the cost matrix: Row_i

Output

* Line 1: A single integer that specifies the minimum cost of building

30

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Farmer John wants to position N (1 <= N <= 100,000) cows and bulls in a single row to present at the annual fair.

FJ has observed that the bulls have been quite pugnacious lately; if two bulls too close together in the line, they will argue and begin to fight, ruining the presentation. Ever resourceful, FJ calculated that any two bulls must have at least K (0 <= K < N) cows between them in order to avoid a fight.

FJ would like you to help him by counting the number of possible sequences of N bulls and cows that avoid any fighting. FJ considers all bulls the to be the same and all cows to be the same; thus, two sequences are only different if they have different kinds of cattle in some position.

Input

* Line 1: Two space-separated integers: N and K

Output

* Line 1: A single integer representing the number of ways FJ could create such a sequence of cattle. Since this number can be quite large, output the result modulo 5,000,011.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Although Farmer John has no problems walking around the fair to collect prizes or see the shows, his cows are not in such good shape; a full day of walking around the fair leaves them exhausted. To help them enjoy the fair, FJ has arranged for a shuttle truck to take the cows from place to place in the fairgrounds.

FJ couldn't afford a really great shuttle, so the shuttle he rented traverses its route only once (!) and makes N (1 <= N <= 20,000) stops (conveniently numbered 1..N) along its path. A total of K (1 <= K <= 50,000) groups of cows conveniently numbered 1..K wish to use the shuttle, each of the M_i (1 <= M_i <= N) cows in group i
wanting to ride from one stop S_i (1 <= S_i < E_i) to another stop E_i (S_i < E_i <= N) farther along the route.

The shuttle might not be able to pick up an entire group of cows (since it has limited capacity) but can pick up partial groups as appropriate.

Given the capacity C (1 <= C <= 100) of the shuttle truck and the descriptions of the groups of cows that want to visit various sites at the fair, determine the maximum number of cows that can ride the shuttle during the fair.

Input

* Line 1: Three space-separated integers: K, N, and C
* Lines 2..K+1: Line i+1 describes group i of the cows with three space-separated integers: S_i, E_i, and M_i

Output

* Line 1: The maximum number of cows that can ride the shuttle at the fair.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Despite their innate prudence, the cows took a beating in the home mortgage market and now are trying their hand at stocks. Happily, Bessie is prescient and knows not only today's S (2 <= S <= 50) stock prices but also the future stock prices for a total of D days (2 <= D <= 10).

Given the matrix of current and future stock prices on various days (1 <= PR_sd <= 1,000) and an initial M (1 <= M <= 200,000) units of money, determine an optimal buying and selling strategy in order to maximize the gain realized by selling stock on the final day. Shares must be purchased in integer multiples, and you need not
spend all the money (or any money). It is guaranteed that you will not be able to earn a profit of more than 500,000 units of money.

Consider the example below of a bull (i.e., improving) market, the kind Bessie likes most. In this case, S=2 stocks and D=3 days. The cows have 10 units of money to invest.

                   Today's price
                   |   Tomorrow's price
                   |   |  Two days hence
             Stock |   |  |
              1    10 15 15
              2    13 11 20

If money is to be made, the cows must purchase stock 1 on day 1. Selling stock 1 on day 2 and quickly buying stock 2 yields 4 money in the bank and one share of 2. Selling stock 2 on the final day brings in 20 money for a total of 24 money when the 20 is added to the bank.

Input

* Line 1: Three space-separated integers: S, D, and M
* Lines 2..S+1: Line s+1 contains the D prices for stock s on days 1..D: PR_sd

Output

* Line 1: The maximum amount of money possible to have after selling on day D.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Farmer John dutifully checks on the cows every day. He traverses some of the M (1 <= M <= 50,000) trails conveniently numbered 1..M from pasture 1 all the way out to pasture N (a journey which is always possible for trail maps given in the test data). The N (1 <= N <= 10,000) pastures conveniently numbered 1..N on Farmer John's
farm are currently connected by bidirectional dirt trails. Each trail i connects pastures P1_i and P2_i (1 <= P1_i <= N; 1 <= P2_i <= N) and requires T_i (1 <= T_i <= 1,000,000) units of time to traverse.

He wants to revamp some of the trails on his farm to save time on his long journey. Specifically, he will choose K (1 <= K <= 20) trails to turn into highways, which will effectively reduce the trail's traversal time to 0. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture 1 to N.

Input

* Line 1: Three space-separated integers: N, M, and K
* Lines 2..M+1: Line i+1 describes trail i with three space-separated integers: P1_i, P2_i, and T_i

Output

* Line 1: The length of the shortest path after revamping no more than K edges

Sample Input  Download

Sample Output  Download

Tags

Discuss