nealgavin的专栏

Fence LoopsThe fences that surround Farmer Brown's collection of pastures have gotten out of control. They are made up of straight segments from 1 through 200 feet long that join together only a

FactorialsThe factorial of an integer N, written N!, is the product of all the integers from 1 through N inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit

ContactIOI'98 The cows have developed a new interest in scanning the universe outside their farm with radiotelescopes. Recently, they noticed a very curious microwave pulsing emission sent right f

StampsGiven a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent

Shaping RegionsN opaque rectangles (1 <= N <= 1000) of various colors are placed on a white sheet of paper whose size is A wide by B long. The rectangles are put with their sides parallel to the s

Humble NumbersFor a given set of K prime numbers S = {p1, p2, ..., pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, a

Score InflationThe more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would li

Agri-NetRuss Cox Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.Farmer Jo

Cow ToursFarmer John has a number of pastures on his farm. Cow paths connect some pastures with certain other pastures, forming a field. But, at the present time, you can find at least two pasture

Fractions to DecimalsWrite a program that will accept a fraction of the form N/D, where N is the numerator and D is the denominator and print the decimal representation. If the decimal representat

Bessie Come HomeKolstad & Burch It's dinner time, and the cows are out in their separate pastures. Farmer John rings the bell so they will start walking to the barn. Your job is to figure out whic

Controlling CompaniesSome companies are partial owners of other companies because they have acquired part of their total shares of stock. For example, Ford owns 12% of Mazda. It is said that a com

StringsobitsKim Schrijvers Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.This set of strings is interesting because it is ordered and contai

Magic SquaresIOI'96 Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares:1234

Spinning Wheels1998 ACM NE Regionals Each of five opaque spinning wheels has one or more wedges cut out of its edges. These wedges must be aligned quickly and correctly. Each wheel also has an ali

Fence RailsBurch, Kolstad, and SchrijversFarmer John is trying to erect a fence around part of his field. He has decided on the shape of the fence and has even already installed the posts, but h

Closed FencesA closed fence in the plane is a set of non-crossing, connected line segments with N corners (3 i, yi}, i in (1..N).Every pair of adjacent vertices defines a side of the fence.

Raucous RockersYou just inherited the rights to N (1 <= N <= 20) previously unreleased songs recorded by the popular group Raucous Rockers. You plan to release a set of M (1 <= M <= 20) compact

American HeritageFarmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow genealogies as binary trees and, instead of writing them

A GameIOI'96 - Day 1 Consider the following two-player game played with a sequence of N positive integers (2 <= N <= 100) laid onto a game board. Player 1 starts the game. The players move alterna

Home on the RangeFarmer John grazes his cows on a large, square field N (2 <= N <= 250) miles on a side (because, for some reason, his cows will only graze on precisely square land segments). Regr

CamelotIOI 98 Centuries ago, King Arthur and the Knights of the Round Table used to meet every year on New Year's Day to celebrate their fellowship. In remembrance of these events, we consider a b

Shopping OffersIOI'95 In a certain shop, each kind of product has an integer price. For example, the price of a flower is 2 zorkmids (z) and the price of a vase is 5z. In order to attract more cus

Riding the FencesFarmer John owns a large number of fences that must be repaired annually. He traverses the fences by riding a horse along each and every one of them (and nowhere else) and fixing

Feed Ratios1998 ACM Finals, Dan Adkins Farmer John feeds his cows only the finest mixture of cow food, which has three components: Barley, Oats, and Wheat. While he knows the precise mixture of th

Sweet ButterGreg Galperin -- 2001Farmer John has discovered the secret to making the sweetest butter in all of Wisconsin: sugar. By placing a sugar cube out in the pastures, he knows the N (1 <=

Money SystemsThe cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Tradi

Zero SumConsider the sequence of digits from 1 through N (where N=9) in increasing order:1 2 3 ... N. Now insert either a `+' for addition or a `-' for subtraction or a ` ' [blank] to run the

Longest PrefixIOI'96 The structure of some biological objects is represented by the sequence of their constituents, where each part is denote by an uppercase letter. Biologists are interested in

Mother's MilkFarmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty

Packing RectanglesIOI 95 The six basic layouts of four rectangles Four rectangles are given. Find the smallest enclosing (new) rectangle into which these four may be fitted without overlapping. B

Prime CryptarithmThe following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime

Calf FlacIt is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes

Barn RepairIt was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John's cows. Happily, many of the cows were on vacation, so the barn was not completely full. T

Mixing MilkSince milk packaging is such a low margin business, it is important to keep the price of the raw product (milk) as low as possible. Help Merry Milk Makers get the milk they need in the

Name That NumberAmong the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of th

Palindromic SquaresRob Kolstad Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome. Given a number base B (2 Print both the number and its squ

Milking CowsThree farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time

The ClocksIOI'94 - Day 2 Consider nine clocks arranged in a 3x3 array thusly: |-------| |-------| |-------| | | | | | | | |---O | |---O | | O |

Number TrianglesConsider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base