From: Subject: SWERC\'96 Problem Set Date: Fri, 27 Jul 2007 02:30:47 +0500 MIME-Version: 1.0 Content-Type: multipart/related; type="text/html"; boundary="----=_NextPart_000_000A_01C7CFF6.2423F830" X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 This is a multi-part message in MIME format. ------=_NextPart_000_000A_01C7CFF6.2423F830 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Location: http://www.acm.inf.ethz.ch/ProblemSetArchive/B_EU_SWERC/1996/problems96.html SWERC\'96 Problem Set

1996--1997 ACM International Collegiate Programming=20 Contest
Southwestern European Regional Contest
ETH Z=FCrich, = November 16,=20 1996

Sponsored by Microsoft
Supported by Union = Bank of=20 Switzerland

Problem Set

Stars=20
Hexagon=20
Domino=20 Effect=20
Pendulum=20
Border=20
The=20 New Villa=20
Ships=20
Jury=20 Compromise

Problem A: Stars

Source file:
Input file: stars.pas/stars.c/stars.C stars.in

On a clear moon-less night, you can see millions of stars glimmering = in the=20 sky. Faced with this overwhelming number, the Greeks started nearly = 2,000 years=20 ago to bring some order to the chaos. They identified groups of stars, = called=20 constellations, and gave them names, mostly from the Greek mythology, = that are=20 still in use today. Examples are ``Ursa Minor'', ``Pisces'', ``Cancer'', = and=20 many others.

Given a sketch of the constellation, it is not easy for the amateur = to=20 actually find the constellation in the sky. Moreover, simple = constellations,=20 such as ``Triangulum'' (triangle,) which consists of only three stars, = may=20 appear several times in the sky. Again, singling out the ``correct'' = occurrence=20 is not easy.

Traditionally, maps were printed for just this purpose. But in this = problem,=20 we will see how the computer can help us find constellations in the sky. =

You will be given a star map; for simplicity this will be a = collection of=20 points in the plane, each having a certain brightness associated with = it. Then,=20 given a constellation, also as a set of points in the plane, you are to=20 determine:

the number of occurrences of the constellation in the star map, = and=20
the position of the brightest occurrence, if one exists. (The = rationale=20 behind this is as follows: if a constellation seems to appear several = times in=20 the sky, the brightest one is most likely to be the real one, since it = is the=20 most eye-catching one.)

An occurrence is a subset of stars from the map that forms a = (possibly)=20 arbitrarily rotated and/or scaled copy of the stars in the = constellation.

The brightness of an occurrence is the average brightness of the = stars it=20 consists of, i.e. the sum of individual brightnesses divided by the = number of=20 stars in the constellation.

Input Specification

The input file contains the descriptions of several star maps. Each = map=20 starts with a line containing a single integer n, specifying the = number=20 of stars in the map (1 <=3D n < 1000). The following = n lines=20 contain three integers each, namely the x- and = y-coordinates and=20 the brightness of every star. The larger the value, the brighter the = star=20 shines.

The next line contains a single integer m, the number of=20 constellations to follow (1 <=3D m < 50). Each = constellation=20 description starts with a line containing an integer s_i, the number of stars in constellation = i, and a=20 string N_i, the name of the = constellation.=20 (N_i will consist of no more = than 40=20 characters and contain no blanks.) The following s_i lines then contain the coordinates of the=20 constellation, again as x/y-pairs.

A blank line separates the star map from the next map. The input file = ends=20 with an empty map (having n =3D 0), which should not be = processed.

N.B.: Since all star coordinates are integer numbers, you can = easily=20 rule out any rotated or scaled constellation whose points do not fall on = integer=20 coordinates.

Output Specification

For each star map first output the number of the map (`Map = #1',=20 `Map #2', etc.) on a line of its own.

For each constellation, in the same order as in the input, output = first its=20 name and how many times it occurs in the map on one line, as shown in = the output=20 sample.

If there is at least one occurrence, output the position of the = brightest=20 occurrence by listing the positions of the stars that form the brightest = occurrence. The star positions have to be printed in ascending = x-order.=20 Positions having the same x-coordinates must be sorted in = ascending=20 y-order. If there are several equally bright solutions, output = only one=20 of them. Adhere to the format shown in the sample output.

Output a blank line before each constellation and a line of 5 dashes=20 (`-----') after every star map.

Sample Input

6
1 2 1
2 1 4
2 4 3
3 2 1
4 1 5
4 3 2
2
3 Triangulum
1 1
3 1
2 4
4 Cancer
1 3
4 3
6 1
7 5

0

Output for Sample Input

Map #1

Triangulum occurs 2 time(s) in the map.
Brightest occurrence: (1,2) (4,1) (4,3)


Cancer occurs 0 time(s) in the map.

-----

[End of Problem A]

Problem B: Hexagon

<= /TR>

Source file:
Input file: hexagon.pas/hexagon.c/hexagon.C hexagon.in

Consider a game board consisting of 19 hexagonal fields, as shown in = the=20 figure below. We can easily distinguish three main directions in the = shape of=20 the board: from top to bottom, from top-left to bottom-right, and from = top-right=20 to bottom-left. For each of these primary directions, the board can be = viewed as=20 a series of rows, consisting of 3, 4, 5, 4, and 3 fields, respectively. =

The game board has to be completely covered using a set of hexagonal = pieces.=20 Each piece carries three numbers, one for every primary board direction. = Only=20 three different numbers are used for each direction. Every possible = combination=20 of three numbers for all three directions is assigned to a piece, = leading to a=20 set of 27 unique pieces. (The board in the above figure is still in the = process=20 of being covered.)

The score of a board is calculated as the sum of all 15 row scores (5 = rows=20 for each primary direction). The row scores are calculated as follows: = if all=20 pieces in a row carry the same number for the direction of the row, the = row=20 score is this number multiplied by the number of pieces in the row. = Otherwise=20 (the pieces carry different numbers in the row direction) the row score = is zero.=20 Note that the pieces may not be rotated. For example, the score of the = leftmost=20 row in the figure is 3 ^. 3 =3D 9, the score of the row to its = right is=20 4 ^. 11 =3D 44.

While in the real game the pieces are chosen randomly and the set of = pieces=20 is fixed, we are interested in the highest possible score for a given = set of=20 numbers for each direction. This means you have to choose those 19 = pieces that=20 result in the highest score.

Input Specification

The first line of the input file contains an integer n which = indicates=20 the number of test cases. Each test case consists of three lines = containing=20 three integers each. Each of these three line contains the numbers for a = single=20 primary direction. From these numbers the set of pieces is generated. =

Output Specification

For each test case output a line containing the number of the case = (`Test=20 #1', `Test #2', etc.), followed by a line containing the = highest=20 possible score for the given numbers. Add a blank line after each test = case.=20

Sample Input

Output for Sample Input

Test #1
308

[End of Problem B]

The following clarification was added to the problem during the = last=20 minute announcements:
To simplify the problem, you should only = consider=20 boards where each row has a score greater than zero, i.e. each piece in = a row=20 carries the same number.

Problem C: Domino Effect

=

Source file:
Input file: domino.pas/domino.c/domino.C domino.in

Did you know that you can use domino bones for other things besides = playing=20 Dominoes? Take a number of dominoes and build a row by standing them on = end with=20 only a small distance in between. If you do it right, you can tip the = first=20 domino and cause all others to fall down in succession (this is where = the phrase=20 ``domino effect'' comes from).

While this is somewhat pointless with only a few dominoes, some = people went=20 to the opposite extreme in the early Eighties. Using millions of = dominoes of=20 different colors and materials to fill whole halls with elaborate = patterns of=20 falling dominoes, they created (short-lived) pieces of art. In these=20 constructions, usually not only one but several rows of dominoes were = falling at=20 the same time. As you can imagine, timing is an essential factor here. =

It is now your task to write a program that, given such a system of = rows=20 formed by dominoes, computes when and where the last domino falls. The = system=20 consists of several ``key dominoes'' connected by rows of simple = dominoes. When=20 a key domino falls, all rows connected to the domino will also start = falling=20 (except for the ones that have already fallen). When the falling rows = reach=20 other key dominoes that have not fallen yet, these other key dominoes = will fall=20 as well and set off the rows connected to them. Domino rows may start = collapsing=20 at either end. It is even possible that a row is collapsing on both = ends, in=20 which case the last domino falling in that row is somewhere between its = key=20 dominoes. You can assume that rows fall at a uniform rate.

Input Specification

The input file contains descriptions of several domino systems. The = first=20 line of each description contains two integers: the number n of = key=20 dominoes (1 <=3D n < 500) and the number m of rows = between=20 them. The key dominoes are numbered from 1 to n. There is at most = one row=20 between any pair of key dominoes and the domino graph is connected, i.e. = there=20 is at least one way to get from a domino to any other domino by = following a=20 series of domino rows.

The following m lines each contain three integers a, = b,=20 and l, stating that there is a row between key dominoes a = and=20 b that takes l seconds to fall down from end to end.

Each system is started by tipping over key domino number 1. =

The file ends with an empty system (with n =3D m =3D = 0), which=20 should not be processed.

Output Specification

For each case output a line stating the number of the case = (`System=20 #1', `System #2', etc.). Then output a line containing the = time=20 when the last domino falls, exact to one digit to the right of the = decimal=20 point, and the location of the last domino falling, which is either at a = key=20 domino or between two key dominoes. Adhere to the format shown in the = output=20 sample. If you find several solutions, output only one of them. Output a = blank=20 line after each system.

Sample Input

Output for Sample Input

System #1
The last domino falls after 27.0 seconds, at key domino 2.


System #2
The last domino falls after 7.5 seconds, between key dominoes 2 and 3.

[End of Problem C]

Problem D: Pendulum

Source file:
Input file: pendulum.pas/pendulum.c/pendulum.C pendulum.in

Consider a pendulum hanging on a string from a hook on a wall. When = pushed,=20 this pendulum will swing back and forth. Now imagine other hooks on the = wall,=20 placed in the path of our pendulum's string. The pendulum will bend = around them,=20 possibly even loop around them. In general, it will follow a much more = complex=20 path than before. After some time, the pendulum's motion will repeat, = the=20 pendulum will follow a periodic orbit. What we would like you to = do is to=20 compute the distance travelled by the pendulum as it completes one cycle = of the=20 orbit.

More formally, we place a cartesian coordinate system on the wall. = The=20 pendulum's string is affixed at the origin (0, 0). As usual, the = x-axis=20 points to the right and the y-axis points upwards. The string of = the=20 pendulum has a length of r. The pendulum is released at position=20 (-r, 0) and therefore starts swinging to the right. Furthermore, = there=20 are n additional hooks distributed over the plane which may = influence the=20 path of the pendulum.

In our ideal world, the following assumptions are true:

The diameters of the hooks and of the string are zero.=20
The pendulum loses no energy (e.g. by friction).=20
The pendulum will never hit a hook, only its string will.=20
The pendulum's string is made of some futuristic material that = only bends=20 where it touches a hook but is otherwise rigid.

Your program should simulate the movement of the pendulum and output = the=20 spatial length of the periodic orbit that it finally enters. As you may = remember=20 from physics: due to gravity, the pendulum will never reach a height = greater=20 than the one it started from! That is, it will never get above the=20 x-axis. It will either reach its initial height again or circle = endlessly=20 around a hook in the wall.

Input Specification

The input file contains several test cases. Each case begins with a = line=20 containing an integer n (the number of hooks, 1 <=3D n = < 500)=20 and a real r (the length of the pendulum's string). The following = n lines each contain two integers specifying the x- and=20 y-coordinate of the corresponding hook.

The file ends with a case having r =3D 0, which should not be = processed.=20

Output Specification

For each case output a line containing the number of the case = (`Pendulum=20 #1', `Pendulum #2', etc.).

Then print a line that contains the distance which the pendulum = travels for=20 completing one cycle of its periodic orbit. Do not count the distance = travelled=20 to reach the starting point of the orbit. (Adhere to the format shown in = the=20 output sample.) The distance should be exact to two digits to the right = of the=20 decimal point.

Output a blank line after each test case.

Sample Input

Output for Sample Input

Pendulum #1
Length of periodic orbit =3D 87.66


Pendulum #2
Length of periodic orbit =3D 31.42

[End of Problem D]

Problem E: Border

=

Source file:
Input file: border.pas/border.c/border.C border.in

You are to write a program that draws a border around a closed path = into a=20 bitmap, as displayed in the following figure:

The path is closed and runs along the grid lines, i.e. between the = squares of=20 the grid. The path runs counter-clockwise, so if following the path is=20 considered as going ``forward'', the border pixels are always to the = ``right''=20 of the path. The bitmap always covers 32 by 32 squares and has its lower = left=20 corner at (0, 0). You can safely assume that the path never touches the = bounding=20 rectangle of the bitmap and never touches or crosses itself. Note that a = bit=20 gets set if it is on the outside of the area surrounded by the path and = if at=20 least one of its edges belongs to the path, but not if only one of its = corners=20 is in the path. (A look at the convex corners in the figure should = clarify that=20 statement.)

Input Specification

The first line of the input file contains the number of test cases in = the=20 file. Each test case that follows consists of two lines. The first line = of each=20 case contains two integer numbers x and y specifying the = starting=20 point of the path. The second line contains a string of variable length. = Every=20 letter in the string symbolizes a move of length one along the grid. = Only the=20 letters `W' (``west''), `E' (``east''), `N'=20 (``north''), `S' (``south''), and `.' (``end of = path'', no=20 move) appear in the string. The end-of-path character ( `.') is = immediately followed by the end of the line.

Output Specification

For each test case, output a line with the number of the case = (`Bitmap=20 #1', `Bitmap #2', etc.). For each row of the bitmap from = top to=20 bottom, print a line where you print a character for every bit in that = row from=20 left to right. Print an uppercase `X' for set bits and a period = `.' for unset bits. Output a blank line after each bitmap.

Sample Input

1
2 1
EENNWNENWWWSSSES.

Output for Sample Input

Bitmap = #1 ................................ <24=20 lines of periods=20 omitted> ................................ .XXX.......= ..................... X...X........................... X..X........= .................... X...X........................... .X..X........= ................... ..XX............................=20

[End of Problem E]

Problem F: The New Villa

Source file:
Input file: villa.pas/villa.c/villa.C villa.in

Mr. Black recently bought a villa in the countryside. Only one thing = bothers=20 him: although there are light switches in most rooms, the lights they = control=20 are often in other rooms than the switches themselves. While his estate = agent=20 saw this as a feature, Mr. Black has come to believe that the = electricians were=20 a bit absent-minded (to put it mildly) when they connected the switches = to the=20 outlets.

One night, Mr. Black came home late. While standing in the hallway, = he noted=20 that the lights in all other rooms were switched off. Unfortunately, Mr. = Black=20 was afraid of the dark, so he never dared to enter a room that had its = lights=20 out and would never switch off the lights of the room he was in.

After some thought, Mr. Black was able to use the incorrectly wired = light=20 switches to his advantage. He managed to get to his bedroom and to = switch off=20 all lights except for the one in the bedroom.

You are to write a program that, given a description of a villa, = determines=20 how to get from the hallway to the bedroom if only the hallway light is=20 initially switched on. You may never enter a dark room, and after the = last move,=20 all lights except for the one in the bedroom must be switched off. If = there are=20 several paths to the bedroom, you have to find the one which uses the = smallest=20 number of steps, where ``move from one room to another'', ``switch on a = light''=20 and ``switch off a light'' each count as one step.

Input Specification

The input file contains several villa descriptions. Each villa starts = with a=20 line containing three integers r, d, and s. = r is the=20 number of rooms in the villa, which will be at most 10. d is the = number=20 of doors/connections between the rooms and s is the number of = light=20 switches in the villa. The rooms are numbered from 1 to r; room = number 1=20 is the hallway, room number r is the bedroom.

This line is followed by d lines containing two integers = i and=20 j each, specifying that room i is connected to room = j by a=20 door. Then follow s lines containing two integers k and = l=20 each, indicating that there is a light switch in room k that = controls the=20 light in room l.

A blank line separates the villa description from the next one. The = input=20 file ends with a villa having r =3D d =3D s =3D 0, = which should=20 not be processed.

Output Specification

For each villa, first output the number of the test case (`Villa=20 #1', `Villa #2', etc.) in a line of its own.

If there is a solution to Mr. Black's problem, output the shortest = possible=20 sequence of steps that leads him to his bedroom and only leaves the = bedroom=20 light switched on. (Output only one shortest sequence if you find more = than=20 one.) Adhere to the output format shown in the sample below.

If there is no solution, output a line containing the statement = `The=20 problem cannot be solved.'

Output a blank line after each test case.

Input Sample

Output for Input Sample

Villa #1

The problem can be solved in 6 steps:
 - Switch on light in room 2.
 - Switch on light in room 3.
 - Move to room 2.
 - Switch off light in room 1.
 - Move to room 3.
 - Switch off light in room 2.


Villa #2
The problem cannot be solved.

[End of Problem F]

Problem G: Ships

Source file:
Input file: ships.pas/ships.c/ships.C ships.in

Probably everyone who ever attended school knows the game where two = opposing=20 players place a set of ships on a sheet of paper and try to eliminate = each=20 other's ships by guessing their location.

In our version of the game, your opponent has distributed the = following seven=20 ship patterns over a rectangular grid of squares:

xx xx xx=20 x x x xx = xx=20 xx xxx xxx xxx xx= xx

Each ship pattern covers exactly four squares. The patterns may be = rotated=20 but not mirrored. All patterns are guaranteed to be placed completely = within the=20 boundaries of the rectangle and not to overlap each other, whereas = touching=20 another pattern or the border is allowed.

We assume that we are in the middle of the game and that several = squares have=20 already been uncovered. You will be given a rectangular grid of squares=20 representing your current knowledge about the positions of your enemy's = ships.=20 Every square is marked by one of the following characters:

`x' if a ship covers the square=20
`o' if no ship covers the square=20
`.' if the square has not yet been uncovered

Given that information, you are to decide whether you can determine = all=20 remaining `x' squares with at most one miss, i.e. whether you = could=20 uncover the `.' squares without getting more than one = `o'=20 square before you had all `x' squares uncovered. This means you = are=20 allowed to hit a `o' if then the solution becomes unique.

Input Specification

The input file contains several game situations. Every test case = starts with=20 a line containing two integers w and h. These define width = and=20 height of the game rectangle, where 2 <=3D w, h <=3D 16. =

Each of the next h lines contains a string of w = characters.=20 Each of these characters is either `x', `o' or = `.',=20 depending on the state of the corresponding square.

A blank line separates each game from the next. The input file ends = with a=20 game having w =3D 0 and h =3D 0. This game should not be = processed.=20

Output Specification

For each test case you should first output a line containing the = number of=20 the game, followed by a line containing either `yes.' (if you = can=20 determine all `x' with at most one miss) or `no.' (if = you=20 cannot determine all `x' without at least two misses).

Output a blank line after every game.

Sample Input

10 10
.x..x.....
oooooxoooo
oxooxxx...
xxoooooo..
xoooxooo..
ooxxxxoo..
oooooxxoox
ooooooxoox
ooooooooxx
oooooooooo


0 0

Output for Sample Input

Game #1
yes.

[End of Problem G]

Problem H: Jury Compromise

=

Source file:
Input file: jury.pas/jury.c/jury.C jury.in

In Frobnia, a far-away country, the verdicts in court trials are = determined=20 by a jury consisting of members of the general public. Every time a = trial is set=20 to begin, a jury has to be selected, which is done as follows. First, = several=20 people are drawn randomly from the public. For each person in this pool, = defence=20 and prosecution assign a grade from 0 to 20 indicating their preference = for this=20 person. 0 means total dislike, 20 on the other hand means that this = person is=20 considered ideally suited for the jury.

Based on the grades of the two parties, the judge selects the jury. = In order=20 to ensure a fair trial, the tendencies of the jury to favour either = defence or=20 prosecution should be as balanced as possible. The jury therefore has to = be=20 chosen in a way that is satisfactory to both parties.

We will now make this more precise: given a pool of n = potential jurors=20 and two values d_i (the = defence's value)=20 and p_i (the prosecution's = value) for each=20 potential juror i, you are to select a jury of m persons. = If J=20 is a subset of {1,...,n} with m elements, then = D(J) =3D=20 sum_{k in J}d_k and P(J) = =3D=20 sum_{k in J}p_k are the total = values of=20 this jury for defence and prosecution.

For an optimal jury J, the value |D(J) - P(J)| = must be=20 minimal. If there are several jurys with minimal |D(J) - = P(J)|,=20 one which maximizes D(J) + P(J) should be selected since = the jury=20 should be as ideal as possible for both parties.

You are to write a program that implements this jury selection = process and=20 chooses an optimal jury given a set of candidates.

Note: If your solution is based on an inefficient algorithm, = it may=20 not execute in the allotted time.

Input Specification

The input file contains several jury selection rounds. Each round = starts with=20 a line containing two integers n and m. n is the = number of=20 candidates and m the number of jury members. These values will = satisfy 1=20 <=3D n <=3D 200, 1 <=3D m <=3D 20 and of = course m <=3D=20 n. The following n lines contain the two integers = p_iand d_{i =}for=20 i =3D 1,...,n. A blank line separates each round from the = next.

The file ends with a round that has n =3D m =3D 0.

Output Specification

For each round output a line containing the number of the jury = selection=20 round (`Jury #1', `Jury #2', etc.).

On the next line print the values D(J) and P(J) of your = jury as=20 shown below and on another line print the numbers of the m chosen = candidates in ascending order. Output a blank before each individual = candidate=20 number.

Output an empty line after each test case.

Sample Input

Output for Sample Input

Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
 2 3

[End of Problem H]

Home Page. Comments. Last update: November 28, = 1996=20 (eos).

------=_NextPart_000_000A_01C7CFF6.2423F830 Content-Type: image/gif Content-Transfer-Encoding: base64 Content-Location: http://www.acm.inf.ethz.ch/ProblemSetArchive/B_EU_SWERC/1996/hexagon.gif R0lGODdhoQCuAKEAAAAAAMzMzP///wAAACwAAAAAoQCuAAAC/pSPqcvtj4CctFqIs968+w0E4kiW JfCl6sq2R2jGMerW9l3D8j7S+A8MMnQ8nk+ITNqIxd1RCY2CmtSn9IpNMKnOrPe75cqs33IwLJ6Z 10h02kRmy1Xu92mOZ9Xt97y/s8dHEvdXqCUoRmi4GIjYswh56MilGInXOClSablk4emZmfg5OsHJ sdmAOakKZ6qBmhpaxNrq+kDogyvrtGp7m/riQPs2XOuroJgrvAsXChuZHLzM3CP7bFipPE1dPHYc 8SIBYlDazct87ad8TYPSjk4dkD73JP5KLvBuHS//feQ+Lp9Acvv4zVtTb2CGdvbyOeOnydfBV5nM VXE1cQoi/ouUOGXUyIdjR0sfQRKDaEwJqZVRVpJCCcflpw8TS1IMCXOQoHkZbWIwJ7LKxlMrfG7b mZMjO2ENh4DL1/RWVIerYIqEhSrbU4ALFRKsiDIoVghTkUnjurBewXhB+/36Sfas11//drU9YTeu 1Kz4oD5DS3WtXXTCwi31O1cPt8WEnWoJyFVr31hsB7N1/LSrQG2Ys0Fse7dPZmn3NpNewBl12Ief zT6G3BTXaWRWwYYd/UP2ZNq1HYVWMzs3nZzyfBNvpzLF7zEbifcz+lMmKOfypFug/hxKTerdlnuD Xpimc6Djg+P46B1v86TmlwDbLWm1cauv+5ZKm/B94gjy/qu2dj0QYHDhVp9nBgnWWIH4pPPPW/vx VxmC1ryH3GHtkbbJcqFpSCE5Zemn0H2alcOYZXmF50J+IwYIT4nOOJjKhwRayKKErL2oF4yoAaiZ V2L151tpMer4IIWx2fZZRUKCyGNu/gEZElFDyFhkDvP1tpOUHoBHGU7HDQWIdReohNR4WYYpJgXa pUkBd2yKuKSWQpD35ZkB0ZSERenpBGaPqFHJJW/rQWkHjZgdytBfU12FZZ9EIiOZfVXuCOGTEfaS 46MKXoioiS3iiGKMfIUoZ2A3eqqkfnDqVY59VPL4W6zcoCjgW5EtcempE1Iazp0BOmigi5aeCOuk m8J3/uwQSepK7Gy1hidiNMhWmuuglxF4g25F7qnJsNdOm21nXRKaBrcRGdtCT2aWyR666Yq3bqFu tvSmuYPUi92zwm3JHbvsBcorIPHKexyn7w7XqJe3jZboK4uqelS1ChtU369/zSVtlXv++F+y7KjI a7DCWptgZqnF1SCttxxoY6qUNtzVySGTNbK3mDJZlGFE1YUqs0GGOmWG4DDoY88+2wn0oUq/apZa RyN5c9KQ6qgv1U9D7aim2OJWNc6m+itxoXFqAWgbNn+K9IBbkgn2slECgifbBNcpNpps0vtmvvXG DXdy/Ja3dqm+nqEc4IEPLvh5CNOnHOIRlD2n1l8t/jyz0lI32WTXf4L8J80dV2556GRnqnnTFW/u +begi7415sXylHJhGVKs8uWt65ypu8HELupPqq/Ouo9wp8YTqR4eRmKCq9oqTsa6735736aVFlnJ z1cILudw8Q585jTqA6rBr92KeU2nJ5v59aeJ5Tq0xs94eOsyc60+Yi+4LP74sUWvB8TBpxu1fYHL Pd3LX1F+FrnnNY5vc8oaEEqXg72t6U0tUeACpdcGBkYOYO1TWwLjR7gB5oAOeSJhBkV4sAKisH+9 8xoBnWVBMmjLeTCLjhWEFqoakuVh9Cve+UyWwwXdQ3tTC+L04iTDoWFwUvMDogE9xL8VagOCDGOS /g8N1sStPPGIxlrey4SIRBAdhHdEQwxy7Lc9DDFtK81z1fckh8Eyki9F0KPer0ZoO9wBrYySyt3S kHdH/7nwhx2E4Z24V0QYUVFSWXzf/6QYqS0GqCHZeFVCkEfJ2j1SfM4T4I46qThxbVJ+kPsgpEAZ SgBpy0+JS+USH3hBx3nQlLJ0ZS2ZQsEJ3k2XaboCBwuZxxdC4peSJKQwh3nCWHqSJGw0FApx6EaH 3dAWKVtkYipJOjCmMYrqWB/iKglN7DnMmIzAUKmEFk5tooybfzijF8VowwHpkC7FzAN4EMm8M9Lx G8/EIjm/qM8WBtMjmlyalNAyqoEyU5ABW+H4ihw5JThihKHlO+j+4EhMX1KUnRokGyr5acF6vnJs IBVpRk1a0qDtUiUSTCkeS+hSM5w0pDG15TJrmoWMzhSn2UTjLGnK01SKk5VADeoLhzrLnRqVVerM nVKX6j6f9hSqCDkmVcHgx4ZeFatMyepWvZAMS35VDtH46FhzKlCtnhWsylxrGer1VBwUAAA7 ------=_NextPart_000_000A_01C7CFF6.2423F830 Content-Type: image/gif Content-Transfer-Encoding: base64 Content-Location: http://www.acm.inf.ethz.ch/ProblemSetArchive/B_EU_SWERC/1996/border.gif R0lGODdhygDLAKEAAAAAAP///7OzswAAACwAAAAAygDLAAAC/oyPB6CcD6OctNqLs978LvN14kiW 5olGn5O27gvHXijX9o1rdM73vs36CYfETrCITCoVy6bzCY1Kp9Sq9YrNarfcrvcLAounx7EZuTur h+m1m7cov+exuJyOT9nz/Jf93heo8ydYWAJomGiBqNio4gjpETk5wUjpaHmpmKlpyNkp+AnaJzqa V2pKh5r6tsq65vp6Fis7RlsLdovrpbvL1eurBRyMNUxsZXxMlawsxdwM9QztJD29VG2dhJ1dtM3N 9hcuPk5ebn6Onq6+Pv4rufhOwTkfL19ffC9BX7HPn/8Ib0s/ewEJ+itoMGEldwgXNgR4MKJCff+q DHQokeJD/ogTOWLMclFjRo8iO0IISRJZxQcoWa5M0NLlRosvEcS0WZPJTJkjVe6EmTPATZw/ifak WVTnUaBJwzQVGvTJUKUmmS61WhXrR3xPp0LtGtWr1LBBxZqNSo1s07Ngn1JjBzeu3Ll02TG8ajQr 1a0l+aY8eVfv3r5/eQp2inewz8SID7Nl/BVy2raMHx+OfHkyZK+W/QJ226Qz4c+b1UoObdpxas+G WZNZPbp1bNmFtc5+TVl1btd5eUcRXVsx6cvAkZZeCzu4cNrGiZdNPtx3Y67HK0Nnjt32YufId9/u /f133fHky5snF1g6ZunFs4NXHu26dvfL59OfHj6+d/jt/u37f9+cepzJB+B9613RX4EKLlgfg/jB N9Z+0UGYYIMW6ledbhkKiBZqEt5X4YMTQqgZd9Z9+N+FB27HYXcb5rfiiAHCOCCKDsZoYIktnvgi hR1eQ+CFIeKYoojLBGnkjUOK9dZ5Tj4JpTrp6SNAlVZeeSUAWG5ppZZcYrkkkhHy8+WWXpbZJZpd ijmkjlSqWeWZaspZZpg2/uYBnHHqKQCdX9rZ44wq8Onnn3oCaiJIeR5K6KFsiunmoIxOOuejd2Io T6OUoonojoouoimchZppaaBHgropp45eSqSSU0oqaqiclpoodZmmWueqphbZqoqRniSrqqLS6qmt +kSZ/g6rbYaGbLPORvnLoSEuoGutNEYr6rSjgkksjNRIiyS1wyr7oxLbZqlttcVeKxC4l4pbKbmg XePurg2oy669v9Vr7UnnrinvafRmG+6/cXZLYmj8rusvvj6y+i3B7xrcJ8IyLrNwvpVQ3Km3Ckus r1AcW5zjx3OmO27IvSbpTMb8rePwxbwyyeyzNt9MF7YnlzVywP1a5LLM96b8s4E0D7zzWj2rvCzS nHK2dNEzl6tN0CBGzbDQKnrjh9VFwjurz1ljDLJjWGs8Nq8RJ13Z2Q8zrfPTPMdsNMlkeO0g2HXa 7Wq7ZbPnttYsb001GngLGXjdYiN4+OAi0z314sg0/r6yXXBDXDPOmm9+Ttx1ohzv5QKbSznUkPet 8tpyT3w64Zg7/XnBrTu+cu1cu8Ax6GGLnpnJq4es9598++p77KwTnTbqIJU+N/JoPz/539CzlHjk qRf/p+57Sy64VMwrPbvtkGLPZRtvbxx+x9GzLfXQobfvujCcz08/IQItsk7z7ycf/6dkSv+y9A0P U5X4njyqpzz+EfBN7AOcALl3qv81MD/BK98Aa/crlhgQfc47nwLHdKsJBrCD3WuauRYlQsFVkFQQ VJuHJPg7sz2Qd8ZiYAwdSELFXQ9IqErh1WYIP9plECYbPBYQP3i7FsyjiCpAYP8+OESbMLFhObRe 2xClUr8szu9VKoRSCxOIoLAES3hffGIYuzJGC5aRdknUgxhxpUYaTi+CxEkjC+XowTNuxo7cWqP4 7odGON7xiibUxhtjVUUw5jFhPNyjIPuIxxJy0Wh8zNIFj3bCQCJyf3O0onqiuLVKAiySOvRfHR9p ST9i8oD8cEAcdHDIOR2xk4ocgf2aKDKRaXGXvNwi9cw3um+Q4Ja45EAbhQnMXxpTmNF45QaOycyA JNNj0QQCC6bZvWqySJu84KYtvCkGaIJTieP8gjjLeYJzovMQ65xkO53xTmHEswgFAAA7 ------=_NextPart_000_000A_01C7CFF6.2423F830--

1996--1997 ACM International Collegiate Programming=20 ContestSouthwestern European Regional ContestETH Z=FCrich, = November 16,=20 1996

Problem Set

Contents

Problem A: Stars

Input Specification

Output Specification

Sample Input

Output for Sample Input

Problem B: Hexagon

Input Specification

Output Specification

Sample Input

Output for Sample Input

Problem C: Domino Effect

Input Specification

Output Specification

Sample Input

Output for Sample Input

Problem D: Pendulum

Input Specification

Output Specification

Sample Input

Output for Sample Input

Problem E: Border

Input Specification

Output Specification

Sample Input

Output for Sample Input

Problem F: The New Villa

Input Specification

Output Specification

Input Sample

Output for Input Sample

Problem G: Ships

Input Specification

Output Specification

Sample Input

Output for Sample Input

Problem H: Jury Compromise

Input Specification

Output Specification

Sample Input

Output for Sample Input

1996--1997 ACM International Collegiate Programming=20 Contest
Southwestern European Regional Contest
ETH Z=FCrich, = November 16,=20 1996