| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 7268 | PA - Checkers |
|
| 7269 | PB - Bad Grass |
|
| 7270 | PC - Hay Expenses |
|
| 7271 | PD - Hay For Sale |
|
| 7272 | PE - Patting Heads |
|
| 7273 | PF - Jigsaw Puzzles |
|
| 7274 | PG - Trick or Treat on the Farm |
|
| 7275 | PH - Secret Message |
|
Description
The cows have taken up the game of checkers with a vengeance.
Unfortunately, despite their infinite enjoyment of playing, they are terrible at the endgame. They want your help.
Given an NxN (4 <= N <= 30) checkboard, determine the optimal set of moves to end the game on the next move. Checkers move only on the '+' squares and capture by jumping 'over' an opponent's piece.
The piece is removed as soon as it is jumped. See the example below where N=8:
- + - + - + - + The K's mark Bessie's kings; the o's represent the
+ - + - + - + - opponent's checkers. Bessie always moves next. The
- + - K - + - + Kings jump opponent's checkers successively in any
+ - + - + - + - diagonal direction (and removes pieces when jumped).
- o - o - + - +
+ - K - + - + - For this board, the solution requires the lower left
- o - + - + - + King to jump successively across all three of the
+ - K - + - K - opponents' checkers, thus ending the game (moving K marked as >K<):
Original After move 1 After move 2 After move 3
- + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - +
+ - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + -
- + - K - + - + - + - K - + - + - + - K - + - + - + - K - + - +
+ - + - + - + - + - + - + - + - + ->K<- + - + - + - + - + - + -
- o - o - + - + - o - o - + - + - + - o - + - + - + - + - + - +
+ - K - + - + - >K<- K - + - + - + - K - + - + - + - K ->K<- + -
- o - + - + - + - + - + - + - + - + - + - + - + - + - + - + - +
+ ->K<- + - K - + - + - + - K - + - K - + - K - + - K - + - K -
The moves traversed these squares:
1 2 3 4 5 6 7 8 R C
1 - + - + - + - + start: 8 3
2 + - + - + - + - move: 6 1
3 - + - K - + - + move: 4 3
4 + - * - + - + - move: 6 5
5 - o - o - + - +
6 * - K - * - + -
7 - o - + - + - +
8 + - K - + - K -
Write a program to determine the (unique, as it turns out) game-ending sequence for an NxN input board if it exists. There is at least a king and at least one opponent piece on the board.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains N characters (each one of: '-', '+', 'K', or 'o') that represent row i of a proper checkboard.
Output
* Lines 1..?: If this sequence of moves is impossible, output "impossible" on a line by itself. If such a sequence exist, each line contains two space-separated integers that represent successive locations of a king whose moves will win the game.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Bessie was munching on tender shoots of grass and, as cows do,contemplating the state of the universe. She noticed that she only enjoys the grass on the wide expanses of pasture whose elevation is at the base level of the farm. Grass from elevations just 1 meter higher is tougher and not so appetizing. The bad grass gets worse as the elevation increases.
Continuing to chew, she realized that this unappetizing food grows the sides of hills that form a set of 'islands' of bad grass among the sea of tender, verdant, delicious, abundant grass.
Bessie donned her lab coat and vowed to determine just how many islands of bad grass her pasture had. She created a map in which she divided the pasture into R (1 < R <= 1,000) rows and C (1 < C <= 1,000) columns of 1 meter x 1 meter squares. She measured the elevation above the base level for each square and rounded it to a non-negative integer. She noted hungrily that the tasty grass all had elevation 0.
She commenced counting the islands. If two squares are neighbors in any of the horizontal, vertical or diagonal directions then they are considered to be part of the same island.
How many islands of bad grass did she count for each of the supplied maps?
Input
* Line 1: Two space-separated integers: R and C
* Lines 2..R+1: Line i+1 describes row i of the map with C space separated integers
Output
* Line 1: A single integer that specifies the number of islands.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Every day Farmer John feeds the cows a lavish meal of premium gourmet hay. He then records the number of bales on the next line of his expense notebook.
When tax time comes, FJ realizes that he neglected to record the dates for the hay feedings. He must calculate a number of different totals of successive hay feedings in order to solve the puzzle of which feedings went with which month of expenses.
FJ has created a dataset with N (4 <= N <= 500) days conveniently numbered 1..N of hay bale counts H_i (1 <= H_i <= 1,000). He has an additional Q (1 <= Q <= 500) queries -- each query is a pair of integers S_j and E_j (1 <= S_j <= E_j <= N) that denote that start and end indices of some hay bale counts. Your job is to sum the hay bale counts for the days S_j..E_j (inclusive) and report one sum for each query.
Input
* Line 1: Two space-separated integers: N and Q
* Lines 2..N+1: Line i+1 contains a single hay bale count for day i: H_i
* Lines N+2..N+Q+1: Line j+N+1 describes query j with a pair of integers: S_j and E_j
Output
* Lines 1..Q: Line j of the output file contains a single integer that is the sum of the hay bale counts for days S_j through E_j
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John suffered a terrible loss when giant Australian cockroaches ate the entirety of his hay inventory, leaving him with nothing to feed the cows. He hitched up his wagon with capacity C (1 <= C <= 50,000) cubic units and sauntered over to Farmer Don's to get some hay before the cows miss a meal.
Farmer Don had a wide variety of H (1 <= H <= 5,000) hay bales for sale, each with its own volume (1 <= V_i <= C). Bales of hay, you know, are somewhat flexible and can be jammed into the oddest of spaces in a wagon.
FJ carefully evaluates the volumes so that he can figure out the largest amount of hay he can purchase for his cows.
Given the volume constraint and a list of bales to buy, what is the greatest volume of hay FJ can purchase? He can't purchase partial bales, of course. Each input line (after the first) lists a single bale FJ can buy.
Input
* Line 1: Two space-separated integers: C and H
* Lines 2..H+1: Each line describes the volume of a single bale: V_i
Output
* Line 1: A single integer which is the greatest volume of hay FJ can purchase given the list of bales for sale and constraints.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It's Bessie's birthday and time for party games! Bessie has instructed the N (1 <= N <= 100,000) cows conveniently numbered 1..N to sit in a circle (so that cow i [except at the ends] sits next to cows i-1 and i+1; cow N sits next to cow 1). Meanwhile, Farmer John fills a barrel with one billion slips of paper, each containing some integer in the range 1..1,000,000.
Each cow i then draws a number A_i (1 <= A_i <= 1,000,000) (which is not necessarily unique, of course) from the giant barrel. Taking turns, each cow i then takes a walk around the circle and pats the heads of all other cows j such that her number A_i is exactly divisible by cow j's number A_j; she then sits again back in her original position.
The cows would like you to help them determine, for each cow, the number of other cows she should pat.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: A_i
Output
* Lines 1..N: On line i, print a single integer that is the number of other cows patted by cow i.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The cows have taken up alphabetical jigsaw puzzles. In these puzzles with R (1 <= R <= 10) rows and C (1 <= C <= 10) columns, the edges are not funny-shaped cardboard shapes but rather are letters.
Each piece has a serial number and 4 letters (or borders) that must be aligned as in a regular jigsaw puzzle. The pseudo-letter '0' (the digit 0) will represent a border (and a piece can have several borders if it is a corner piece or even the top of column in a, e.g., 4x1 puzzle). Below is a set of six pieces (the borders are marked with lines instead of '0's) assembled in one way (of many) that completes the puzzle:
+---+ +---+ +---+
| 1 c c 3 d d 5 |
+-d-+ + a + +-e-+
+-d-+ +-a-+ +-e-+
| 2 b b 4 b b 6 |
+---+ +---+ +---+
Note that each edge letter of each piece matches the border letter of the piece adjacent to it; the borders appear properly on the top, bottom, and sides.
Pieces are represented by a serial number and a clockwise list of their four edges (where edges are the letters a..z and 0). Pieces might require rotation when placed in the puzzle.
Given a set of pieces, find at least one way to assemble them into a puzzle. Test data for puzzles with larger R and C are easier to solve because they have a more varied set of edge letters.
Input
* Line 1: Two space-separated integers: R and C
* Lines 2..R*C+1: Each line contains five space-separated entities: an integer serial number and four edge identifiers
Output
* Lines 1..R*C: Line R*(i-1)+j describes the puzzle piece placed a row i, column j with an integer and five space-separated entities: the serial number of the puzzle piece and the four piece edge identifiers in the order top, right, bottom, left.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Every year in Wisconsin the cows celebrate the USA autumn holiday of Halloween by dressing up in costumes and collecting candy that Farmer John leaves in the N (1 <= N <= 100,000) stalls conveniently numbered 1..N.
Because the barn is not so large, FJ makes sure the cows extend their fun by specifying a traversal route the cows must follow. To implement this scheme for traveling back and forth through the barn, FJ has posted a "next stall number" next_i (1 <= next_i <= N) on stall i that tells the cows which stall to visit next; the cows thus might travel the length of the barn many times in order to collect their candy.
FJ mandates that cow i should start collecting candy at stall i. A cow stops her candy collection if she arrives back at any stall she has already visited.
Calculate the number of unique stalls each cow visits before being forced to stop her candy collection.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: next_i
Output
* Lines 1..N: Line i contains a single integer that is the total number of unique stalls visited by cow i before she returns to a stall she has previously visited.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Bessie is leading the cows in an attempt to escape! To do this, the cows are sending secret binary messages to each other.
Ever the clever counterspy, Farmer John has intercepted the first b_i (1 <= b_i <= 10,000) bits of each of M (1 <= M <= 50,000) of these secret binary messages.
He has compiled a list of N (1 <= N <= 50,000) partial codewords that he thinks the cows are using. Sadly, he only knows the first c_j (1 <= c_j <= 10,000) bits of codeword j.
For each codeword j, he wants to know how many of the intercepted messages match that codeword (i.e., for codeword j, how many times does a message and the codeword have the same initial bits). Your job is to compute this number.
The total number of bits in the input (i.e., the sum of the b_i and the c_j) will not exceed 500,000.
Input
* Line 1: Two integers: M and N
* Lines 2..M+1: Line i+1 describes intercepted code i with an integer b_i followed by b_i space-separated 0's and 1's
* Lines M+2..M+N+1: Line M+j+1 describes codeword j with an integer c_j followed by c_j space-separated 0's and 1's
Output
* Lines 1..M: Line j: The number of messages that the jth codeword could match.