Usaco Mar12 Bronze

Part of USACO Mar12

``````**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Three problems numbered 1 through 3
**********************************************************************

Problem 1: Times17 [Brian Dean, 2012]

After realizing that there is much money to be made in software
development, Farmer John has launched a small side business writing short
programs for clients in the local farming industry.

Farmer John's first programming task seems quite simple to him -- almost
too simple: his client wants him to write a program that takes a number N
as input, and prints 17 times N as output.  Farmer John has just finished
writing this simple program when the client calls him up in a panic and
informs him that the input and output both must be expressed as binary
numbers, and that these might be quite large.

Please help Farmer John complete his programming task.  Given an input
number N, written in binary with at most 1000 digits, please write out the
binary representation of 17 times N.

PROBLEM NAME: times17

INPUT FORMAT:

* Line 1: The binary representation of N (at most 1000 digits).

SAMPLE INPUT (file times17.in):

10110111

OUTPUT FORMAT:

* Line 1: The binary representation of N times 17.

SAMPLE OUTPUT (file times17.out):

110000100111

OUTPUT DETAILS:

The binary number 10110111 is equal to 183 in decimal form.
183 x 17 = 3111 is 110000100111 in binary format.

**********************************************************************

Problem 2: Connect the Cows [Brian Dean, 2012]

Every day, Farmer John walks around his farm to check on the health and
well-being of his N (1 <= N <= 10) cows.

The location of each cow is described by a point in the 2D plane, and
Farmer John starts out at the origin (0,0).  To make his route more
interesting, Farmer John decides that he will only walk in directions
parallel to the coordinate axes -- that is, only north, south, east, or
west.  Furthermore, he only changes his direction of travel when he reaches
the location of a cow (he may also opt to pass through the location of a
cow without changing direction, if desired).  When he changes his direction
of travel, he may make either a 90-degree or 180-degree turn.  FJ's route
must take him back to the origin after visiting all his cows.

Please compute the number of different routes FJ can take to visit his N
cows, if he changes direction exactly once at the location of each cow.  He
is allowed to pass through the location of a cow without changing direction
an arbitrary number of times.  The same geometric route taken forward
versus backward counts as two different routes.

PROBLEM NAME: connect

INPUT FORMAT:

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains the x and y coordinates
(space-separated) of the ith point (each values is in the
range -1000...1000).

SAMPLE INPUT (file connect.in):

4
0 1
2 1
2 0
2 -5

INPUT DETAILS:

There are 4 cows, at positions (0,1), (2,1), (2,0), and (2,-5).

OUTPUT FORMAT:

* Line 1: The number of different routes FJ can take (this could be
zero if there are no valid routes).

SAMPLE OUTPUT (file connect.out):

2

OUTPUT DETAILS:

There are two different routes: Farmer John can visit cows in the orders
1-2-4-3 or 3-4-2-1 before returning to the origin.

**********************************************************************

Problem 3: Wrong Directions [Brian Dean, 2012]

Farmer John has just purchased a fancy new programmable tractor.  To make
the tractor move, he types in a string of length N (1 <= N <= 100,000)
consisting of only the characters F, L, and R.  Each 'F' instructs the
tractor to move forward one unit, and the characters 'L' and 'R' result in
left and right turns of 90 degrees, respectively. The tractor starts out at
the origin (0,0) facing north.

After programming his tractor by typing in his intended command string, FJ
remembers that he typed exactly one character in the command string
incorrectly, but he can't remember which one!  For example, he might have
typed 'F' or 'L' when his intended string contained the character 'R'.
Please compute the number of different locations in the plane at which the
tractor might end up as a result (the direction the tractor faces in its
final location does not matter).

PROBLEM NAME: wrongdir

INPUT FORMAT:

* Line 1: Farmer John's intended command string.

SAMPLE INPUT (file wrongdir.in):

FF

INPUT DETAILS:

Farmer John wants the tractor to advance forward twice, ideally ending at
position (0,2).

OUTPUT FORMAT:

* Line 1: The number of positions at which the tractor might end up,
given that FJ mistypes one of the characters in his command
string.

SAMPLE OUTPUT (file wrongdir.out):

3

OUTPUT DETAILS:

There are 4 possible mistyped sequences: FL, FR, LF, an RF.  These will
land the tractor at (0,1), (0,1), (-1,0), and (1,0) respectively, a total
of 3 distinct locations.

**********************************************************************```
```
page revision: 0, last edited: 12 Mar 2012 10:47
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License