[shkola] Zadachite ot U.S. OPEN 2003

**********************************************************************
                           GREEN PROBLEMS
**********************************************************************
                  Four problems numbered 1 through 4
**********************************************************************

PROBLEM 1: Cowpals [Romanian Olympiad, via Stroe, 2002]

As in all human societies, the cows have friends, too. A new cow,
Clara, has joined Farmer John's farm.  Clara sees that the N (1 <= N
<= 3000) cows already on the farm have partitioned themselves into
sets of friends.

Each cow belongs to exactly one set of friends. Each cow in a set is
a friend of every other cow in the same set and no cow outside the
set.

Clara wants to be friends with some of the cows but does not know how
to identify the various sets of friends.  Farmer John has agreed to
help Clara by answering questions that are all of the same form: "Who
are the friends of cows A, B, ..., and Z?" FJ will answer such
questions with the list of all cows who are friends of any of the cows
in the query.

Your task is to help Clara determine the groups of friends by
disturbing FJ with the smallest possible number of queries.

Write an interactive (i.e., 'reactive') program that reads and writes
to standard input and output respectively.  Begin by reading a line
that contains nothing but a single integer, N, the total number of
cows.

After this, your program should print lines to stdout with a 'query' or,
when the solution has been determined, a 'solution'.  Each queries is an
N digit binary string:

bbbbb...b

in which each b is a '0' or a '1'.  The '1's in the query are the cows
for whom the friend-list is desired.  Consider a query for the friends
of five cows from a herd of 12 cows:

001001001011

This query means, "Please tell me all the friends of cows 3, 6, 9,
11, and 12".

For each query, read in a 'response' line of the same format. A
response to the above query might be:

111001001111

Which means cows 1, 2, 3, 6, 9, 10, 11, and 12 are friends with at
least one of cows 3, 6, 9, 11, and 12 from the query.  Of course, a
cow is always a friend with itself.

When your program has determined the entire list of friend sets, it
should write a line that summarizes those sets by telling their sizes
with one or more space-separated integers presented in sorted order,
smallest number first:

solution S1 S2 ... Sx

A sample of a solution might be:

solution 1 1 2 8

[though this solution might or might not apply to the query and
response above].

Your solution will receive points based upon its optimality.  Full
marks will be awarded for solutions that match the minimum number of
queries of all solutions submitted.  Proportionally fewer points will
be awarded to inferior solutions.  Solutions that do not determine a
valid friendset or require too many queries will receive no credit.

REACTIVE PROGRAM GRADING REQUIREMENTS:

C/C++ stdio Programmers:  Use "fflush(stdout);" to send your output to the grader.

C/C++ fstream Programmers:  "... << endl << flush;" to send your output to the
       grader.

Pascal Programmers: No special operations are required.

PROBLEM NAME: cowpal

SAMPLE INPUT/OUTPUT:

Program            Program
writes             reads
                    5
10001
                    10101
01010
                    01010
00100
                    10100
00001
                    00001
00010
                    01010
solution 1 2 2

EXPLANATION

The sets of cow friends were:  {1, 3}, {2, 4}, and {5}. The program probed
for this set using these queries and receiving these replies:

     Q: friends of {1,5}?     A: {1,3,5}
     Q: friends of {2,4}?     A: {2,4}
     Q: friends of {3}?       A: {1,3}
     Q: friends of {5}?       A: {5}
     Q: friends of {2}?       A: {2,4}

and then deduced the answer, counted the set members, sorted the results
and responded with the proper answer: 1 2 2.

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

PROBLEM 2: Mountain Walking [Jan Kuipers, 2003]

Farmer John and Bessie the cow have embarked on one of those 'active'
vacations. They spend entire days walking in the mountains and then,
at the end of the day, they tire and return to their vacation cabin.

Since climbing requires a lot of energy and they are already tired,
they wish to return to the cabin using a path that has the least
difference between its highest and lowest elevations, no matter how
long that path is. Help FJ find this easy-to-traverse path.

The map of the mountains is given by an N x N (2 <= N <= 100) matrix
of integer elevations (0 <= any elevation <= 110) FJ and Bessie are
currently at the upper left position (row 1, column 1) and the cabin
is at the lower right (row N, column N).  They can travel right, left,
toward the top, or toward the bottom of the grid.  They can not travel
on a diagonal.

PROBLEM NAME: mtwalk

INPUT FORMAT:

* Line 1: The single integer, N

* Lines 2..N+1: Each line contains N integers, each of which specifies
        a square's height. Line 2 contains the first (top) row of the
        grid; line 3 contains the second row, and so on.  The first
        number on the line corresponds to the first (left) column of
        the grid, and so on.

SAMPLE INPUT (file mtwalk.in):

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

OUTPUT FORMAT:

* Line 1: An integer that is the minimal height difference on the
        optimal path.

SAMPLE OUTPUT (file mtwalk.out):

2

OUTPUT DETAILS:

xx...   Taking the path shown here, the minimum height is 0 and the 
.xx..   maximum is 2, so the difference is 2.
..x..
..x..
..xxx


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

PROBLEM 3: Millenium Leapcow [via Nikolay Valtchanov, from Bulgaria '01, 2003]

The cows have revised their game of leapcow.  They now play in the
middle of a huge pasture upon which they have marked a grid that bears
a remarkable resemblance to a chessboard of N rows and N columns (3
<= N <= 365).

Here's how they set up the board for the new leapcow game:

* First, the cows obtain N x N squares of paper.  They write the
  integers from 1 through N x N, one number on each piece of paper.

* Second, the 'number cow' places the papers on the N x N squares in
  an order of her choosing.

Each of the remaining cows then tries to maximize her score in the
game.

* First, she chooses a starting square and notes its number.

* Then, she makes a 'knight' move (like the knight on a chess board)
  to a square with a higher number.  If she's particularly strong,
  she leaps to the that square; otherwise she walks.

* She continues to make 'knight' moves to higher numbered squares
  until no more moves are possible.

Each square visited by the 'knight' earns the competitor a single
point.  The cow with the most points wins the game.

Help the cows figure out the best possible way to play the game.

PROBLEM NAME: leap2

INPUT FORMAT:

* Line 1: A single integer: the size of the board

* Lines 2.. ...: These lines contain space-separated integers that tell
        the contents of the chessboard.  The first set of lines
        (starting at the second line of the input file) represents the
        first row on the chessboard; the next set of lines represents
        the next row, and so on.  To keep the input lines of
        reasonable length, when N > 15, a row is broken into
        successive lines of 15 numbers and a potentially shorter line
        to finish up a row.  Each new row begins on its own line.

SAMPLE INPUT (file leap2.in):

4
1 3 2 16
4 10 6 7
8 11 5 12
9 13 14 15

OUTPUT FORMAT:

* Line 1: A single integer that is the winning cow's score; call it W.

* Lines 2..W+1: Output, one per line, the integers that are the
        starting square, the next square the winning cow visits, and
        so on through the last square. If a winning cow can choose
        more than one path, show the path that would be the 'smallest'
        if the paths were sorted by comparing their respective 'square
        numbers'.

SAMPLE OUTPUT (file leap2.out):

7
2
4
5
9
10
12
13

OUTPUT DETAILS:

The longest tour consists of the moves 2 to 4, 4 to 5, 5 to 9, 9 to
10, 10 to 12, 12 to 13 and has length of 7 squares.

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

PROBLEM 4: Optimal Milking [Mihai Stroe, 2002]

FJ has moved his K (1 <= K <= 30) milking machines out into the cow
pastures among the C (1 <= C <= 200) cows.  A set of paths of various
lengths runs among the cows and the milking machines.  The milking machine
locations are named by ID numbers 1..K; the cow locations are named by ID
numbers K+1..K+C.

Each milking point can "process" at most M (1 <= M <= 15) cows each day.

Write a program to find an assignment for each cow to some milking
machine so that the distance the furthest-walking cow travels is
minimized (and, of course, the milking machines are not overutilized).
At least one legal assignment is possible for all input data sets.
Cows can traverse several paths on the way to their milking machine.

PROBLEM NAME: milking

INPUT FORMAT:

* Line 1: A single line with three space-separated integers: K, C, and
        M.

* Lines 2.. ...: Each of these K+C lines of K+C space-separated
        integers describes the distances between pairs of various
        entities. The input forms a symmetric matrix.  Line 2 tells
        the distances from milking machine 1 to each of the other
        entities; line 3 tells the distances from machine 2 to each of
        the other entities, and so on.  Distances of entities directly
        connected by a path are positive integers no larger than 200. 
        Entities not directly connected by a path have a distance of
        0.  The distance from an entity to itself (i.e., all numbers
        on the diagonal) is also given as 0.  To keep the input lines
        of reasonable length, when K+C > 15, a row is broken into
        successive lines of 15 numbers and a potentially shorter line
        to finish up a row.  Each new row begins on its own line.

SAMPLE INPUT (file milking.in):

2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0

OUTPUT FORMAT:

A single line with a single integer that is the minimum possible total
 distance for the furthest walking cow.

SAMPLE OUTPUT (file milking.out):

2

OUTPUT DETAILS:

Assign cow 1 to milk machine 1 (dist=2), cow 2 to machine 2 (dist=2) and 
cow 3 to machine 1 (dist=1). The maximum distance is then 2.

Type a file name below and then click `Send it in!' to submit. Submission file Name:

**********************************************************************
                           ORANGE PROBLEMS
**********************************************************************
                  Four problems numbered 6 through 9
**********************************************************************

PROBLEM 6: Bale Figures [Mihai Stroe, 2002]

Cows like to build shapes out of hay bales. Each new shape
is constructed from N (1 <= N <= 25,000) 1 x 1 x 1 cubic bales.

Bale 1 lies on the floor. After placing it, each successive bale from
2 through N is attached to the shape by placing the new bale in the
proper relative position to one of the bales already placed.  For
instance, imagine the following figure:

     Bale 1 - on the floor
     Bale 2 - RIGHT Bale 1 (to Bale 1's right)
     Bale 3 - FRONT Bale 2 (in front of Bale 2) 
     Bale 4 - FRONT Bale 3

This results in an (inverted) L-shape:

                     +--+--+                      
                1-> /  /  /| <-2                      
                   +--+--+ +
                   | /  /|/                         
                   ++--+ +                       
                   /  /|/ <-3                     
                  +--+ +                          
                  |  |/ <-4                       
                  +--+                            

Adding another bale:

    Bale 5 - OVER Bale 1

adds height to the shape:

                     +--+                            
                    /  /|                           
                   +--+ +--+                      
               5-> |  |/  /| <-2                      
                   +--+--+ +
               1-> | /  /|/                         
                   ++--+ +                       
                   /  /|/ <-3                     
                  +--+ +                          
                  |  |/ <-4                       
                  +--+                            

But adding another directive:

    Bale 6 - BACK Bale 4

results in an invalid shape, since bales 3 and 6 would overlap.

Given N bales and placements described as above, output the exposed
surface area of the solid figure if the shape is valid.  A face is
considered exposed if it is not touched by any face of any other bale
and does not touch the floor (i.e., is not the bottom of a cube on
the floor).  Output -1 if the shape is invalid.  No bale will be
placed farther than 25 bale-widths from the first bale.  No bale
will be placed below the floor level.

PROBLEM NAME: bales2

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N: These lines describe the placement of bales 2..N in the
        form "j X". Line 2 describes bale 2; line 3 describes bale 3;
        and so on. The letter "X" is one of: "L" (left), "R" (right),
        "F" (front), "B" (back), "O" (over), or "U" (under). The bales
        can be glued and require no underlying support if extended
        over an empty space.

SAMPLE INPUT (file bales2.in):

5
1 R
2 F
3 F
1 O

INPUT DETAILS:

5      5 cubes total. Bale 1 is placed on the floor.
1 R    Bale 2 is placed to the right of bale 1
2 F    Bale 3 is placed to the front of bale 2
3 F    Bale 4 is placed to the front of bale 3
1 O    Bale 5 is placed above bale 1 (yielding the first picture above).

OUTPUT FORMAT:

* Line 1: The exposed surface area of the resulting solid.  If the
        solid is invalid, output "-1".

SAMPLE OUTPUT (file bales2.out):

18

OUTPUT DETAILS:

On a per-bale basis:
Bale 1: 3 faces exposed
Bale 2: 3 faces exposed
Bale 3: 3 faces exposed
Bale 4: 4 faces exposed
Bale 5: 5 faces exposed


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

PROBLEM 7: Jumping Cows [Harry Wiggins [South Africa], 2002]

Farmer John's cows would like to jump over the moon, just like the
cows in their favorite nursery rhyme.  Unfortunately, cows can not
jump.

The local witch doctor has mixed up P (1 <= P <= 150,000) potions to aid
the cows in their quest to jump.  These potions must be administered
exactly in the order they were created, though some may be skipped.

Each potion has a 'strength' (1 <= strength <= 500) that enhances the cows'
jumping ability. Taking a potion during an odd time step increases the
cows' jump; taking a potion during an even time step decreases the jump. 
Before taking any potions the cows' jumping ability is, of course, 0.

No potion can be taken twice, and once the cow has begun taking
potions, one potion must be taken during each time step, starting at
time 1. One or more potions may be skipped in each turn.

Determine which potions to take to get the highest jump.

PROBLEM NAME: jumpcow

INPUT FORMAT:

* Line 1: A single integer, P

* Lines 2..P+1: Each line contains a single integer that is the
        strength of a potion. Line 2 gives the strength of the first
        potion; line 3 gives the strength of the second potion; and so
        on.

SAMPLE INPUT (file jumpcow.in):

8
7
2
1
8
4
3
5
6

OUTPUT FORMAT:

* Line 1: A single integer that is the maximum possible jump.

SAMPLE OUTPUT (file jumpcow.out):

17

OUTPUT DETAILS:

Skipping the second potion (2), fifth potion (4), and 7th potion (5) yields a
sequence of strengths: 7, 1, 8, 3, 6; and a jump of +7-1+8-3+6 = 17.


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

PROBLEM 8: Lost Cows (Bulg Ol, Mar02) [Nikolay Valtchanov, 2003]

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a
spectacular display of poor judgment, they visited the neighborhood
'watering hole' and drank a few too many beers before dinner.  When
it was time to line up for their evening meal, they did not line up
in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them.  Furthermore, he's
not very good at observing problems.  Instead of writing down each
cow's brand, he determined a rather silly statistic:  For each cow in
line, he knows the number of cows that precede that cow in line that
do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

PROBLEM NAME: lost

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N: These N-1 lines describe the number of cows that precede
        a given cow in line and have brands smaller than that cow.  Of
        course, no cows precede the first cow in line, so she is not
        listed. Line 2 of the input describes the number of preceding
        cows whose brands are smaller than the cow in slot #2; line 3
        describes the number of preceding cows whose brands are
        smaller than the cow in slot #3; and so on.

SAMPLE INPUT (file lost.in):

5
1
2
1
0

INPUT DETAILS:

Five cows are standing line.
One cow in line before the cow in slot #2 has a brand smaller than
that of cow #2.
Two cows in the line before cow #3 have brands smaller than that of cow #3.
One cow in the line before cow #4 has a brand smaller than that of cow #4.
No cows in the line before cow #5 have a brand smaller than that of cow #5.

OUTPUT FORMAT:

* Lines 1..N: Each of the N lines of output tells the brand of a cow
        in line.  Line #1 of the output tells the brand of the first
        cow in line; line 2 tells the brand of the second cow; and so
        on.

SAMPLE OUTPUT (file lost.out):

2
4
5
3
1

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

PROBLEM 9: Bovine Math Geniuses [Rob Kolstad, 2003]

Farmer John loves to help the cows further their mathematical skills.
He has promised them Hay-flavored ice cream if they can solve various
mathematical problems.

He said to Bessie, "Choose a six digit integer, and tell me what it
is. Then extract the middle four digits. Square them and discard
digits at the top until you have another number six digits or shorter.
Tell me the result."

Bessie, a mathematical genius in disguise, chose the six digit number
655554. "Moo: 6 5 5 5 5 4", she said. She then extracted the middle
four digits:  5555 and squared them: 30858025. She kept only the
bottom six digits:  858025. "Moo: 8 5 8 0 2 5", she replied to FJ.

FJ nodded wisely, acknowledging Bessie's prowess in arithmetic.  "Now
keep doing that until you encounter a number that repeats a number
already seen," he requested.

Bessie decided she'd better create a table to keep everything straight:

              Middle    Middle   Shrunk to
       Num   4 digits   square   6 or fewer
     655554    5555    30858025    858025
     858025    5802    33663204    663204
     663204    6320    39942400    942400
     942400    4240    17977600    977600
     977600    7760    60217600    217600 <-+
     217600    1760     3097600     97600   |
      97600    9760    95257600    257600   |
     257600    5760    33177600    177600   |
     177600    7760    60217600    217600 --+

Bessie showed her table to FJ who smiled and produced a big dish of
delicious hay ice cream.  "That's right, Bessie," he praised. "The
chain repeats in a loop of four numbers, of which the first
encountered was 217600.  The loop was detected after nine iterations."

Help the other cows win ice cream treats.  Given a six digit number,
calculate the total number of iterations to detect a loop, the first
looping number encountered, and also the length of the loop.

FJ wondered if Bessie knew all the tricks. He had made a table to help
her, but she never asked:

              Middle    Middle   Shrunk to
       Num   4 digits   square   6 or fewer
     200023    0002       4        4
          4       0       0        0
          0       0       0        0         [a self-loop]

whose results would be: three iterations to detect a loop, looping on
0, and a length of loop equal to 1.

Remember: Your program can use no more than 16MB of memory.

PROBLEM NAME: icecrm

INPUT FORMAT:

* Line 1: A single six digit integer that is the start of the sequence
        testing.

SAMPLE INPUT (file icecrm.in):

655554

OUTPUT FORMAT:

* Line 1: Three space-separated integers: the first number of a loop,
        the length of the loop, and the minimum number of iterations
        to detect the loop.

SAMPLE OUTPUT (file icecrm.out):

217600 4 9

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

Type a file name below and then click `Send it in!' to submit. Submission file Name: