| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 7276 | PA - Going Once, Going Twice, Gone! |
|
| 7277 | PB - Buying Hay |
|
| 7278 | PC - Guarding the Farm |
|
| 7279 | PD - Time Management |
|
| 7280 | PE - Mixed Up Cows |
|
| 7281 | PF - Cheering up the Cows |
|
| 7282 | PG - Light Switching |
|
| 7283 | PH - Toys |
|
Description
The cows' slimming diet has left Farmer John with extra hay so he has decided to hold an auction to reduce his inventory. He has N (1 <= N <= 1,000) identical lots (each of about 100 bales) of hay; his potential customers comprise M (1 <= M <= 1,000) other farmers in the area.
Each farmer i tells Farmer John how much he is willing to pay P_i (1 <= P_i <= 1,000,000) for a lot of hay. Each of the farmers wishes to purchase a single lot of hay.
To make sure the other farmers do not get jealous of each other, Farmer John decides that he must sell the lots of hay at a fixed price to each customer who is willing to pay at least that price; the rest will decline the purchase.
Help Farmer John determine the smallest price he should set on a lot of hay to maximize the amount of money he makes.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains a single integer: P_i
Output
* Line 1: Two space-separated integers: the smallest price that Farmer John should choose to maximize his revenue and the amount of money he takes in.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John is running out of supplies and needs to purchase H (1 <= H <= 50,000) pounds of hay for his cows.
He knows N (1 <= N <= 100) hay suppliers conveniently numbered 1..N. Supplier i sells packages that contain P_i (1 <= P_i <= 5,000) pounds of hay at a cost of C_i (1 <= C_i <= 5,000) dollars. Each supplier has an unlimited number of packages available, and the packages must be bought whole.
Help FJ by finding the minimum cost necessary to purchase at least H pounds of hay.
Input
* Line 1: Two space-separated integers: N and H
* Lines 2..N+1: Line i+1 contains two space-separated integers: P_i and C_i
Output
* Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least H pounds of hay.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.
He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map.
A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij
Output
* Line 1: A single integer that specifies the number of hilltops
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning the barn, mending the fences, and so on).
To manage his time effectively, he has created a list of the jobs that must be finished. Job i requires a certain amount of time T_i (1 <= T_i <= 1,000) to complete and furthermore must be finished by time S_i (1 <= S_i <= 1,000,000). Farmer John starts his day at time t=0 and can only work on one job at a time until it is finished.
Even a maturing businessman likes to sleep late; help Farmer John determine the latest he can start working and still finish all the jobs on time.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: T_i and S_i
Output
* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Each of Farmer John's N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.
Gangsta cows are rebellious and line up to be milked in an order called 'Mixed Up'. A cow order is 'Mixed Up' if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a 'Mixed Up' lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).
How many different ways can N cows be Mixed Up?
Input
* Line 1: Two space-separated integers: N and K
* Lines 2..N+1: Line i+1 contains a single integer that is the serial
number of cow i: S_i
Output
* Line 1: A single integer that is the number of ways that N cows can be 'Mixed Up'. The answer is guaranteed to fit in a 64 bit integer.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John has grown so lazy that he no longer wants to continue maintaining the cow paths that currently provide a way to visit each of his N (5 <= N <= 10,000) pastures (conveniently numbered 1..N). Each and every pasture is home to one cow. FJ plans to remove as many of the P (N-1 <= P <= 100,000) paths as possible while keeping the pastures connected. You must determine which N-1 paths to keep.
Bidirectional path j connects pastures S_j and E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j) and requires L_j (0 <= L_j <= 1,000) time to traverse. No pair of pastures is directly connected by more than one path.
The cows are sad that their transportation system is being reduced. You must visit each cow at least once every day to cheer her up. Every time you visit pasture i (even if you're just traveling through), you must talk to the cow for time C_i (1 <= C_i <= 1,000).
You will spend each night in the same pasture (which you will choose) until the cows have recovered from their sadness. You will end up talking to the cow in the sleeping pasture at least in the morning when you wake up and in the evening after you have returned to sleep.
Assuming that Farmer John follows your suggestions of which paths to keep and you pick the optimal pasture to sleep in, determine the minimal amount of time it will take you to visit each cow at least once in a day.
For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.
Input
* Line 1: Two space-separated integers: N and P
* Lines 2..N+1: Line i+1 contains a single integer: C_i
* Lines N+2..N+P+1: Line N+j+1 contains three space-separated integers: S_j, E_j, and L_j
Output
* Line 1: A single integer, the total time it takes to visit all the cows (including the two visits to the cow in your sleeping-pasture)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John tries to keep the cows sharp by letting them play with intellectual toys. One of the larger toys is the lights in the barn.
Each of the N (2 <= N <= 100,000) cow stalls conveniently numbered 1..N has a colorful light above it.
At the beginning of the evening, all the lights are off. The cows control the lights with a set of N pushbutton switches that toggle the lights; pushing switch i changes the state of light i from off to on or from on to off.
The cows read and execute a list of M (1 <= M <= 100,000) operations expressed as one of two integers (0 <= operation <= 1).
The first kind of operation (denoted by a 0 command) includes two subsequent integers S_i and E_i (1 <= S_i <= E_i <= N) that indicate a starting switch and ending switch. They execute the operation by pushing each pushbutton from S_i through E_i inclusive exactly once.
The second kind of operation (denoted by a 1 command) asks the cows to count how many lights are on in the range given by two integers S_i and E_i (1 <= S_i <= E_i <= N) which specify the inclusive range in which the cows should count the number of lights that are on.
Help FJ ensure the cows are getting the correct answer by processing the list and producing the proper counts.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line represents an operation with three space-separated integers: operation, S_i, and E_i
Output
* Lines 1..number of queries: For each output query, print the count as an integer by itself on a single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Bessie's birthday is coming up, and she wishes to celebrate for the next D (1 <= D <= 100,000; 70% of testdata has 1 <= D <= 500) days.
Cows have short attention spans so Bessie wants to provide toys to entertain them. She has calculated that she will require T_i (1 <= T_i <= 50) toys on day i.
Bessie's kindergarten provides many services to its aspiring bovine programmers, including a toy shop which sells toys for Tc (1 <= Tc <= 60) dollars. Bessie wishes to save money by reusing toys, but Farmer John is worried about transmitting diseases and requires toys to be disinfected before use. (The toy shop disinfects the toys when it sells them.)
The two disinfectant services near the farm provide handy complete services. The first one charges C1 dollars and requires N1 nights to complete; the second charges C2 dollars and requires N2 nights to complete (1 <= N1 <= D; 1 <= N2 <= D; 1 <= C1 <= 60; 1 <= C2 <= 60). Bessie takes the toys to the disinfecters after the party and can pay and pick them back up the next morning if one night service is rendered, or on later mornings if more nights are required for disinfecting.
Being an educated cow, Bessie has already learned the value of saving her money. Help her find the cheapest way she can provide toys for her party.
Input
* Line 1: Six space-separated integers: D, N1, N2, C1, C2, Tc
* Lines 2..D+1: Line i+1 contains a single integer: T_i
Output
* Line 1: The minimum cost to provide safe and sanitary toys for Bessie's birthday parties.