logo Your Math Help is on the Way!

More Math Help

Algebraic Symmetries
Radical Expressions and Equation
The Exponential Function
Math 1010-3 Exam #3 Review Guide
Rational Numbers Worksheet
Are You Ready for Math 65?
Solving Simultaneous Equations Using the TI-89
Number Theory: Fermat's Last Theorem
Course Syllabus for Intermediate Algebra
Solving Inequalities with Logarithms and Exponents
Introduction to Algebra Concepts and Skills
Other Miscellaneous Problems
Syllabus for Calculus
Elementary Linear Algebra
Adding and Subtracting Fractions without a Common Denominator
Pre-Algebra and Algebra Instruction and Assessments
Mathstar Research Lesson Plan
Least Common Multiple
Division of Polynomials
Counting Factors,Greatest Common Factor,and Least Common Multiple
Real Numbers, Exponents and Radicals
Math 115 Final Exam Review
Root Finding and Nonlinear Sets of Equations
Math 201-1 Final Review Sheet
Powers of Ten and Calculations
Solving Radical Equations
Factoring Polynomials
Section 8
Declining Price, Profits and Graphing
Arithmetic and Algebraic Structures
Locally Adjusted Robust Regression
Topics in Mathematics
Syllabus for Mathematics
The Quest To Learn The Universal Arithmetic
Solving Linear Equations in One Variable
Examples of direct proof and disproof
Algebra I
Quadratic Functions and Concavity
More on Equivalence Relations
Solve Quadratic Equations by the Quadratic Formula
Solving Equations and Inequaliti
MATH 120 Exam 3 Information
Rational Number Ideas and Symbols
Math Review Sheet for Exam 3
Linear Algebra Notes
Factoring Trinomials
Math 097 Test 2
Intermediate Algebra Syllabus
How to Graphically Interpret the Complex Roots of a Quadratic Equation
The General, Linear Equation
Written Dialog for Problem Solving
Radian,Arc Length,and Area of a Sector
Internet Intermediate Algebra
End Behavior for linear and Quadratic Functions
Division of Mathematics
161 Practice Exam 2
General linear equations
Algebraic Symmetries
Math 20A Final Review Outline
Description of Mathematics
Math 150 Lecture Notes for Chapter 2 Equations and Inequalities
Course Syllabus for Prealgebra
Basic Operations with Decimals: Division
Mathematics Content Expectations
Academic Systems Algebra Scope and Sequence
Syllabus for Introduction to Algebra
Syllabus for Elementary Algebra
Environmental Algebra
More Math Practice Problems
Intermediate Algebra
Syllabus for Linear Algebra and Differential Equations
Intermediate Algebra
Rational Expressions and Their Simplification
Course Syllabus for Intermediate Algebra
GRE Review - Algebra
Foundations of Analysis
Finding Real Zeros of Polynomial Functions
Model Academic Standards for Mathematics
Study Guide for Math 101 Chapter 3
Real Numbers
Math 9, Fall 2009, Calendar
Final Review Solutions
Exponential and Logarithmic Functions

Try the Free Math Solver or Scroll down to Tutorials!












Please use this form if you would like
to have this math solver on your website,
free of charge.

More Math Practice Problems

1 Introduction

The way to learn how to solve problems is to practice. Here are a few problems, including
the entire February 2003 contest!

2 The Algorithm

Some things in life change, but not good contest strategy. First, and most importantly, read
the problem. Make sure you understand it thoroughly, and note the limits. As you think
about an algorithm, think about three things: run time, memory usage, and coding time.
There is a working solution; if your solution doesn’t quite work in time, keep looking! While
an incorrect solution may get significant partial credit, you really rack up points when you
get a full solution, since those last three cases might be worth a third or half of the problem.

3 The Problems

1. (Dwarve’s Casino, UMD 2004 (sort of)) Farmer John wants to gamble with the cows.
But since the cows don’t have opposable thumbs, they can’t do much. So they agreed
that Farmer John will bet some integer amount of money, and the cows will tell him if
he wins or loses. However, out of the N rounds played the cows can only
make FJ lose L times Help FJ maximize his winnings given his initial
amount of money D

2. (Prisoner, USACO sometime) Bessie has been a bad cow, and FJ wants to put her in
as secure a prison as possible. A prison consists of a set of concentric nonintersecting
closed loops of fences around Bessie, and its security is defined by the number of fences
enclosing her. However, FJ only has a fixed set of N posts that he
can build fences between. Given Bessie’s position and these posts, find the maximum
security prison FJ can build around Bessie.

3. (Cow Math USACO Feb 2003)
Taking their cue from the builders of the USA’s Interstate Highway system, the cows
have introduced the Interpasture Path numbering system. They have already numbered
the N (2 ¡= N ¡= 25) pastures with the integers 1..N and now are numbering
each path between two pastures with its own distinct Interpasture Path number in the
range 1..2000 (e.g., I-9 and I-16).

In an example Interpasture Path map, four pastures numbered 1, 2, 3, and 4 are
connected by Interpasture Paths I-3, I-6, I-9, and I-16:

Bessie likes to walk from pasture 1 to pasture 2 on the nifty new Interpasture system.
During each walk, she never visits the same pasture twice, so possible walks on the
sample map above are 1-4-2 and 1-3-2.

Over the years, Bessie has developed an amazing mathematical skill that she likes to
exercise. During each walk, she enjoys finding the greatest common factor (GCF) of the
Interpasture Paths that she traverses. For instance, the walk designated 1-4-2 touches
I-16 and I-6 which have the greatest common factor of 2 (since 2 properly divides into
16 and 6 but no larger integer does).

As she walks the pastures day after day, she takes all the possible routes from pasture
1 to pasture 2 and remembers each of the GCFs. After she has taken every possible
walk once, she computes the least common multiple (LCM) of all the GCFs. For this
example, the two GCF values are 2 and 3 (GCF(6,16)=2 and GCF(3,9)=3), so the
LCM is 6.

For large networks of paths, Bessie might get tired of all the walking, but she really
wants to know the LCM for every map. Calculate that number for her.

4. (Cow Imposters, USACO Feb 2003)
FJ no longer uses the barbaric custom of branding to mark the cows that he owns.
Instead, he creates a binary code of B (1 ¡= B ¡= 16) bits for each cow and embosses
it onto a metal strip that is fastened to each cow’s ear.

The cows have taken in a stray and wish to create an ID strip for it. Unknown to FJ,
they have created a machine that can make a new ID strip by combining two existing
ID strips using the XOR operation (ID strips are not consumed by this machine, and
the same ID strip can be used for both inputs).

The cows wish to create a specific ID strip for the stray or at least get as close to a
desired ID as possible – with the smallest possible number of bits differing between the
goal ID strip and the best possible new ID strip.

Given a set of E (1 ¡= E ¡= 100) existing ID strips, the goal ID strip, and a large
number of blank ID strips to hold intermediate results, calculate the closest possible
ID strip that can be created from the existing ID strips.

If more than one ID is closest, choose the one that can be created in the fewest steps.
If there is still a tie, choose the ‘smallest’ ID (i.e., if you sorted all the IDs, the one
that is first).

5. (Traffic Lights, USACO Feb 2003)
The cows are going downtown! Just like everyone else, they want to optimize their
driving time.

They have noted that when driving on a straight road with traffic lights, the best
strategy to get to their destination as quickly as possible is not necessarily to drive
as fast as possible to the next traffic light, brake if it’s red, wait for a green light,
accelerate, and then drive on. It is often better to approach a traffic light more slowly
in order to have some speed when the light turns green.

The cows have observed the traffic lights for a very long time. They know that each
traffic light behaves in the following way: * it is green for a certain amount of time Tg,
* then it is red for an amount of time Tr, * then green again, * and so on.

Given * the integer length of the road L (1 ¡= L ¡= 100) * the number of traffic lights
N (0 ¡= N ¡= L+1) along with information about each light: * the unique position (0
¡= position ¡= L) * Tg (1 ¡= Tg ¡= 10) * Tr (1 ¡= Tr ¡= 10) * color at t=0 (R or G)
* Tc (the integer amount of time since the light last changed)

write a program to determine the minimal amount of time needed to get to the end of
the road. Note that at each discrete time (starting at t=0), a car may either change
its speed (expressed in positional units per time unit) by one or keep it constant. The
speed is always 0 or positive, of course. No driving backwards!

The car starts at position zero has has speed zero. The car must complete its trip at
position L, also with speed zero. The car must stop at all lights that are red when
encountered – be sure its speed is 0 at the red light’s position if it encounters a red
light. The car may move when the light changes from red to green, but not when it
changes from green to red.

6. (Farm Tour, USACO Feb 2003)
When FJ’s friends visit him on the farm, he likes to show them around. His farm
comprises N (1 ¡= N ¡= 1000) fields numbered 1..N, the first of which contains his
house and the Nth of which contains the big barn. A total M (1 ¡= M ¡= 10000) paths
that connect the fields in various ways. Each path connects two different fields and
has a nonzero length smaller than 35,000.

To show off his farm in the best way, he walks a tour that starts at his house, potentially
travels through some fields, and ends at the barn. Later, he returns (potentially
through some fields) back to his house again.

He wants his tour to be as short as possible, however he doesn’t want to walk on any
given path more than once. Calculate the shortest tour possible. FJ is sure that some
tour exists for any given farm.