| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 7301 | PA - Payback |
|
| 7302 | PB - Plumbing the Pond |
|
| 7303 | PC - The Perfect Cow |
|
| 7304 | PD - Dairy Queen |
|
| 7305 | PE - Sand Castle |
|
| 7306 | PF - Cow Frisbee Team |
|
| 7307 | PG - Look Up |
|
| 7308 | PH - Moon Mooing |
|
| 7309 | PI - Cleaning Up |
|
| 7310 | PJ - Earthquake Damage 2 |
|
Description
"Never a borrower nor a lender be." O how Bessie wishes she had taken that advice! She has borrowed from or lent money to each of N (1 <= N <= 100,000) friends, conveniently labeled 1..N.
Payback day has finally come. She knows she is owed more money than she owes to the other cows. They have all lined up in a straight line, cow i standing i meters from the barn. Bessie is going to traverse the line collecting money from those who owe her and reimbursing money to those she owes.
As she moves down the line, she can request any cow who owes her money to give her the money. When she has enough money to pay off any or all of her debts, she can pay the (recently collected) money to those she owes. Cow i owes Bessie D_i money (-1,000 <= D_i <= 1,000; D_i != 0). A negative debt means that Bessie owes money to the cow instead of vice-versa.
Bessie starts at the barn, location 0. What is the minimum distance she must travel to collect her money and pay all those she owes? She must end her travels at the end of the line.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: D_i
Output
* Line 1: A single integer that is the total metric distance Bessie must travel in order to collect or pay each cow.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Bessie's drinks water from a pond in the northwest part of the farm.
It has an interesting bottom in that it is full of little hills and valleys. She wonders how deep it is.
She trolls across the pond in her little boat with a very old radar set that tends to have spurious readings. She knows the deepest part is relatively flat and has decided that she'll believe the
largest depth number only if it is verified by the fact that the same depth appears in an adjacent reading.
The pond is modeled as an R x C (1 <= R <= 50; 1 <= C <= 50) grid of (positive integer) depth readings D_rc (0 <= D_rc <= 1,000,000); some readings might be 0 -- those are not part of the pond. A depth reading of 10 means "depth of 10".
Find the greatest depth that appears in at least two 'adjacent' readings (where 'adjacent' means in any of the potentially eight squares that border a square on each of its sides and its diagonals).
She knows the pond has at least one pair of positive, adjacent readings.
Input
* Line 1: Two space-separated integers: R and C
* Lines 2..R+1: Line i+1 contains C space-separated integers that represent the depth of the pond across row i: D_rc
Output
* Line 1: A single integer that is the depth of the pond determined by following Bessie's rules.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
For the 39th year in a row, Farmer John was named "Dairy Farmer of the Year". The Dairy Association wants him to exhibit his most perfect cow at the upcoming Cow Convention in Herbster, Wisconsin on the frigid shores of Lake Superior.
FJ keeps up with scientific literature and knows that beauty is actually a trend toward the average rather than the existence of some superior trait. Thus, he wants to find his most average cow and share her beauty with the other Dairy Farmers during the weekend of revelry and partying at the convention.
Happily, each of the N*N cows (2 <= N <= 99; N odd) has her beauty rating (1 <= R_ij <= 1,000) inscribed on a tag in her ear, just like in this picture.
Cows aren't so good at math, so FJ lines them up into an N x N square. He asks them to find the median cow in each row (the median cow is the one whose beauty number is bigger than or equal to half the cows in her group and also smaller than or equal to half the cows in her group -- the middle number of the group). From those N medians, FJ then finds the median of those numbers and brings that cow to the convention.
Given a set of N x N cows, find the beauty index of the most perfect (average) cow.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains N space-separated integers that are the N beauty indices for row i of the cow square
Output
* Line 1: A single integer that is the index of the most perfect cow as described in the task.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Bessie, always in need of an income, has decided to leverage her dairy skills by taking a part-time job at the local Dairy Queen restaurant. She is running a special cash register (since she has hooves instead of fingers and thus requires special accommodation). Her job is making change for customers as they make a purchase.
As she was counting out 83 cents in change, she wondered: "How many ways can I count out 83 cents? I can use three quarters and eight pennies, seven dimes and three pennies, 83 pennies... there must be a zillion ways!"
How many different ways can one make change for N (1 <= N <= 300) cents using coins from a set of C (1 <= C <= 8) coins of supplied values C_i (1 <= C_i <= 200)? "Different" means differing counts of coins.
Thus, 8 cents can be made, in American currency, with 1 five-cent piece + 3 one-cent pieces and also with 8 one-cent pieces. Using 3 one-cent pieces + 1 five-cent piece is the same as 1 five-cent piece + 3 one-cent pieces, so one can create eight cents in just two different ways. Note that some coin systems are poor at making change and result in an answer of '0'.
Coin values in the input file are listed in descending order from largest to smallest. All coin values will be distinct.
HINT: Consider recursion as a solution technique.
Input
* Line 1: Two space-separated integers: N and C
* Lines 2..C+1: Line i+1 contains a single integer: C_i
Output
* Line 1: A single line with a single integer that is the number of ways to create N cents of change using the supplied coins. The answer is guaranteed to fit into a signed 32-bit integer.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John has built a sand castle! Like all good castles, the walls have crennelations, that nifty pattern of embrasures (gaps) and merlons (filled spaces); see the diagram below. The N (1 <= N <= 25,000) merlons of his castle wall are conveniently numbered 1..N; merlon i has height M_i (1 <= M_i <= 100,000); his merlons often have varying heights, unlike so many.
He wishes to modify the castle design in the following fashion: he has a list of numbers B_1 through B_N (1 <= B_i <= 100,000), and wants to change the merlon heights to those heights B_1, ..., B_N in some order (not necessarily the order given or any other order derived from the data).
To do this, he has hired some bovine craftsmen to raise and lower the merlons' heights. Craftsmen, of course, cost a lot of money. In particular, they charge FJ a total X (1 <= X <= 100) money per unit height added and Y (1 <= Y <= 100) money per unit height reduced.
FJ would like to know the cheapest possible cost of modifying his sand castle if he picks the best permutation of heights. The answer is guaranteed to fit within a 32-bit signed integer.
Note: about 40% of the test data will have N <= 9, and about 60% will have N <= 18.
Input
* Line 1: Three space-separated integers: N, X, and Y
* Lines 2..N+1: Line i+1 contains the two space-separated integers: M_i and B_i
Output
* Line 1: A single integer, the minimum cost needed to rebuild the castle
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After Farmer Don took up Frisbee, Farmer John wanted to join in the fun. He wants to form a Frisbee team from his N cows (1 <= N <= 2,000) conveniently numbered 1..N. The cows have been practicing flipping the discs around, and each cow i has a rating R_i (1 <= R_i <= 100,000) denoting her skill playing Frisbee. FJ can form a team by choosing one or more of his cows.
However, because FJ needs to be very selective when forming Frisbee teams, he has added an additional constraint. Since his favorite number is F (1 <= F <= 1,000), he will only accept a team if the sum of the ratings of each cow in the team is exactly divisible by F.
Help FJ find out how many different teams he can choose. Since this number can be very large, output the answer modulo 100,000,000.
Input
* Line 1: Two space-separated integers: N and F
* Lines 2..N+1: Line i+1 contains a single integer: R_i
Output
* Line 1: A single integer representing the number of teams FJ can choose, modulo 100,000,000.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once again standing in a row. Cow i has height H_i (1 <= H_i <= 1,000,000).
Each cow is looking to her left toward those with higher index numbers. We say that cow i 'looks up' to cow j if i < j and H_i < H_j. For each cow i, FJ would like to know the index of the first cow in line looked up to by cow i.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains the single integer: H_i
Output
* Lines 1..N: Line i contains a single integer representing the smallest index of a cow up to which cow i looks. If no such cow exists, print 0.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A full moon casts some sort of spell on the cows and, like their cousins the wolves and coyotes, they bay at the moon -- mooing instead of howling, of course.
Each 'moo' lasts a certain amount of time. A short 'moo' might last time 1; a longer one might last time 24 or even 1,000,000,000 or longer (cows can really moo when they want to). No 'moo' will last more than or equal to 2^63.
It should come as no surprise that the cows have a pattern to their moos. Bessie will choose an integer c (1 <= c <= 100) that is the initial length of a moo.
After Bessie moos for length c, the cows calculate times for subsequent moos. They apply two formulae to each moo time to yield even more moo times. The two formulae are:
f1(c)=a1*c/d1+b1 (integer divide, of course) and
f2(c)=a2*c/d2+b2.
They then successively use the two new times created by evaluating f1(c) and f2(c) to create even more mooing times. They keep a sorted list of all the possible mooing times (discarding duplicates).
They are allowed to moo a total of N times (1 <= N <= 4,000,000). Please determine the length of the longest moo before they must quit.
The constants in the formulae have these constraints: 1 <= d1 < a1; d1 < a1 <= 20; 0 <= b1 <= 20; 1 <= d2 < a2; d2 < a2 <= 20; 0 <= b2 <= 20.
Consider an example where c=3 and N=10. The constants are:
a1=4 b1=3 d1=3
a2=17 b2=8 d2=2
The first mooing time is 3, given by the value of c. The total list of mooing times is:
1. c=3 -> 3 6. f2(3)=17*3/2+8 -> 33
2. f1(3)=4*3/3+3 -> 7 7. f1(28)=4*28/3+3 -> 40
3. f1(7)=4*7/3+3 -> 12 8. f1(33)=4*33/3+3 -> 47
4. f1(12)=4*12/3+3 -> 19 9. f1(40)=4*40/3+3 -> 56
5. f1(19)=4*19/3+3 -> 28 10. f1(47)=4*47/3+3 -> 65
The tenth time is 65, which would be the proper answer for this set of inputs.
Partial feedback will be provided on the first 50 submissions.
Input
* Line 1: Two space-separated integers: c and N
* Line 2: Three space-separated integers: a1, b1, and d1
* Line 3: Three space-separated integers: a2, b2, and d2
Output
* Line 1: A single line which contains a single integer which is the length of the Nth moo
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the good old days, Farmer John served a boring cuisine comprising but a single type of cow food to his N (1 <= N <= 40000) prize dairy cows. Times change. Today he serves the herd a total of M (1 <= M <= N) different types of food (conveniently numbered 1..M).
The cows are picky. Cow i has a single food preference P_i (1 <= P_i <= M) and will eat only that favorite food.
Each day at feeding time FJ converts the barn into a tastefully lit cafeteria. The cows line up outside to enter the cafeteria in order of their previously-mentioned convenient index number.
Unfortunately, with so many types of food, cleaning up afterwards is very time-consuming. If Farmer John is serving K different types of food, it takes him K*K units of time to clean the barn.
To save time, FJ serves the cows in contiguous groups from the line. After each group, he cleans up the barn and sets out the food for the next group (of course, he only sets out food that cows in the any given group will eat). Determine the minimum amount of total time FJ must spend cleaning the barn. Each group consists of the next contiguous group of cows from the line; each cow belongs to exactly one group; and the barn must be cleaned up after every group, including the last one.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 contains a single integer: P_i
Output
* Line 1: A single integer: the minimum amount of time FJ must spend cleaning the barn.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Wisconsin has had an earthquake that has struck Farmer John's farm! The earthquake has damaged some of the pastures so that they are unpassable. Remarkably, none of the cowpaths was damaged.
As usual, the farm is modeled as a set of P (1 <= P <= 3,000) pastures conveniently numbered 1..P which are connected by a set of C (1 <= C <= 20,000) non-directional cowpaths conveniently numbered 1..C. Cowpath i connects pastures a_i and b_i (1 <= a_i <= P; 1 <= b_i <= P). Cowpaths might connect a_i to itself or perhaps might connect two pastures more than once. The barn is located in pasture 1.
A total of N (1 <= N <= P) cows (in different pastures) sequentially contacts Farmer John via moobile phone with an integer message report_j (2 <= report_j <= P) that indicates that pasture report_j is undamaged but that the calling cow is unable to return to the barn from pasture report_j because she could not find a path that does not go through damaged pastures.
After all the cows report in, determine the minimum number of pastures that are damaged.
Input
* Line 1: Three space-separated integers: P, C, and N
* Lines 2..C+1: Line i+1 describes cowpath i with two integers: a_i and b_i
* Lines C+2..C+N+1: Line C+1+j contains a single integer: report_j
Output
* Line 1: One number, the minimum number of damaged pastures.