Zebra Herd
C_K_Yang liuguangxi Philippe_57721 thefinder faust gerrob stuvtro Mart mathpseudo Quandray mihtanat nireal kwisatz petr0v sinan amaroq hervas sirpoot benito255 tripleedged Flynt tehron Zeta2 LKM sinpaxi Suritrex lesnik7 R2D2 lordoric HvT Caesum drmervy BanKai walek20 yog s_ha_dum st0le mtoader Buri totoiste Hertz teebee Ryan dloser jablonskim Spaulding Juampi noother Mr_KaLiMaN Veric Garfield CommComm phoenix1204 ch0wch0w TheHiveMind dyke elasolova
Public  09/25/09  10xp  Programming  31.6% 
Zebras are very social animals. Like other members of the horse family, they form groups that tend to stick together and
hang out fairly regularly, though not exclusively. (Humans also come to mind in this respect.) Lately, researchers have
been trying to understand just how the communities of zebras evolve over time, what triggers changes, and so forth. Of
course, all they have to go by is observations of where the zebras are over time. From that, we would like to figure out what
are the most natural groups. The assumptions are that (a) if a zebra is part of a group, it tends to spend time close to
others in that group, (b) if a zebra is not part of a group, it tends to spend time further away from others in that group,
and (c) zebras do not change their group membership very often.
Let us make this more precise. You will be given a sequence of observations of zebras. For each observation time, you will have the exact location of each zebra. The distance between two zebras is exactly their Euclidean (straightline) distance. We assume that there are exactly two groups of zebras in the herd, and will denote them by two colors. What we want to do is color each zebra either red or blue for each time step, expressing membership to one or the other group. To express assumption (c) above, we will assess a penalty of some given number c every time a zebra changes colors. To express assumptions (a) and (b), we look at the distance d(i, j) between every pair i, j of zebras. If i and j are of the same color, then we assess a penalty of a * d(i, j) for this pair. If i and j are of opposite colors, then we assess a penalty of b * d(i, j) (i.e., we give a bonus).
Thus, if you are given a proposed labeling of all zebras with either red or blue for each time step, you can compute how good an explanation of zebra activity it is. Your goal is to find the best possible labeling, in the sense that it has the smallest possible total penalty. But you will only need to output the total penalty of the labeling, not the labeling itself.
Input Format
The first line of data set contains two integers z, t, the number of zebras 2 <= z <= 10, and the number of time steps 2 <= t <= 50. Next comes a line with three floating point numbers a, b, c >= 0, the penalty multipliers. This is followed by t lines, describing zebra positions. Each line contains 2z floating point numbers, giving the positions of the zebras in the form x1 y1 x2 y2 . . . xz yz . The first line contains the positions at time 1, the second line at time 2, and so forth.
Input zebra.txt
Give your answer rounded to two decimals like [wholepart].cd
Source:USC Contest Fall 2008
Let us make this more precise. You will be given a sequence of observations of zebras. For each observation time, you will have the exact location of each zebra. The distance between two zebras is exactly their Euclidean (straightline) distance. We assume that there are exactly two groups of zebras in the herd, and will denote them by two colors. What we want to do is color each zebra either red or blue for each time step, expressing membership to one or the other group. To express assumption (c) above, we will assess a penalty of some given number c every time a zebra changes colors. To express assumptions (a) and (b), we look at the distance d(i, j) between every pair i, j of zebras. If i and j are of the same color, then we assess a penalty of a * d(i, j) for this pair. If i and j are of opposite colors, then we assess a penalty of b * d(i, j) (i.e., we give a bonus).
Thus, if you are given a proposed labeling of all zebras with either red or blue for each time step, you can compute how good an explanation of zebra activity it is. Your goal is to find the best possible labeling, in the sense that it has the smallest possible total penalty. But you will only need to output the total penalty of the labeling, not the labeling itself.
Input Format
The first line of data set contains two integers z, t, the number of zebras 2 <= z <= 10, and the number of time steps 2 <= t <= 50. Next comes a line with three floating point numbers a, b, c >= 0, the penalty multipliers. This is followed by t lines, describing zebra positions. Each line contains 2z floating point numbers, giving the positions of the zebras in the form x1 y1 x2 y2 . . . xz yz . The first line contains the positions at time 1, the second line at time 2, and so forth.
Input zebra.txt
Give your answer rounded to two decimals like [wholepart].cd
Source:USC Contest Fall 2008
New Members
 choiyd 4d:12h
 phacks 5d:7h
 MemorySlices 5d:12h
 n3chto 1w
 2997ms 1w:1d
Fresh Problems

Special Squares 4d:19h
solved by 8 
Sum of phi 1w:1d
solved by 4 
Decomposable Triangles 1w:4d
solved by 6 
A cubic form 1w:6d
solved by 4 
Automatic typewriter 2w:1d
solved by 5