Usaco Oct07 Bronze

Part of USACO Oct07

``````**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Two problems numbered 11 through 12
**********************************************************************

Problem 11: Privileged Cows [IOI 1996 Day 2, 2007]

Depending on their milk output, each of the N (1 <= N <= 1,000) cows is
assigned a 'privilege number' of 1, 2, or 3 that dictates whether they get
to drink water at the well earlier (privilege number 1) or later. The cows,
of course, never remember their privilege numbers until Farmer John

Thus, the cows are lined up in some order and must re-align themselves so
that all the privilege number 1's are together at the front of the line,
2's follow, and 3's are together at the end of the line.

Cows, as we are so often reminded, are lazy.  What is the minimum number of
exchanges that can take place to sort the cows properly?

PROBLEM NAME: privc

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer that is the
privilege number of the cow at place i in line

SAMPLE INPUT (file privc.in):

9
2
2
1
3
3
3
2
3
1

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of exchanges
required to order the cows properly

SAMPLE OUTPUT (file privc.out):

4

OUTPUT DETAILS:

Here is one way:
2   2   2< 1   1
2< 1   1   1   1
1< 2   2   2   2
3   3< 2   2   2
3   3   3   3< 2
3   3   3   3   3
2   2< 3   3   3
3   3   3   3   3
1   1   1< 2< 3

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

Problem 12: Perfect Squares [Neal Wu, 2007]

Farmer John is playing a game with Bessie. He picks two positive
integers A and B (1 <= B <= A <= 500), and Bessie is supposed to
deduce which numbers he picked. He gave Bessie the following hint:

The numbers I chose have the property that the square of the
larger number is N (1 <= N <= 1,000) larger than the square of
the smaller number.

Being a smart cow, Bessie knows that this hint will greatly reduce the
number of possibilities for A and B. However, she is asking you to help by
writing a program to compute the exact number of solutions possible.

PROBLEM NAME: squares

INPUT FORMAT:

* Line 1: A single integer: N

SAMPLE INPUT (file squares.in):

15

INPUT DETAILS:

How many pairs of positive integers (A, B) satisfy A^2 = B^2 + 15?

OUTPUT FORMAT:

* Line 1: A single integer representing the number of possible
solutions

SAMPLE OUTPUT (file squares.out):

2

OUTPUT DETAILS:

There are two solutions: (A, B) = (4, 1) and (A, B) = (8, 7)

**********************************************************************```
```
page revision: 3, last edited: 08 Jul 2011 02:49