Olympiad hobby. Waste disposal task

Hey. With you Olympiad hobby. Here we choose an olympiad programming problem, analyze it, work out possible solutions and implement our plans, then send it to the court. We will need knowledge of one of the programming languages: c, c ++, java, pascal, patience, dexterity and basic knowledge of the English language in order to understand the condition of the problem, although the last point is optional, because I will freely retell the condition in Russian.

Did you remember to warm up ? If you forget, then warm up quickly, and come back to us.

I remind you that I am taking tasks from the site http://uva.onlinejudge.org , and today a random choice fell on the task number 154 - the problem of waste disposal.

A brief translation of the conditions of the problem (free translation):
')
Kerbside garbage collection technology has arrived in New Zealand. Five recycle bins of different colors: red (red), orange (orange), yellow (yellow), green (green) and blue (blue), which define 5 types of waste: plastic waste (Plastic), glass (Glass), aluminum (Aluminum), steel (Steel) and paper (Newspaper). Unfortunately, there was no coordination between the cities, so each city assigned an arbitrary type of waste to the colored baskets. Now that the government has been able to solve all the unimportant tasks (such as reorganizing health care, social services, and education), it has decided to tackle other problems. The Minister of Environmental Protection submitted to the Parliament a document on the regulation of the conformity of waste types with colored baskets, but for this it needs to choose its own distribution of waste by color. A supporter of democracy, he explored all the cities that use Kerbside. Using the data he wants, he wants to choose a city whose scheme of matching waste types to colored baskets (being distributed throughout the country) will cause the least amount of changes. The size of the city does not matter, according to democracy: 1 city - 1 vote.

It is necessary to write a program that counts data on the distribution of waste types by color in each city, and will determine which scheme should be chosen. Keep in mind that there will always be a clear leader.

Input : a series of blocks. Each block will contain several lines expressing the distribution of waste types by color, 1 line per city. There can be up to 100 cities. Each block ends in a line, starting with an “e”. The end of the input data is marked with a string of one "#" character.

Output : For each incoming block, you must output the ordinal number of the city, whose distribution scheme should be chosen as a reference.

:
r/P,o/G,y/S,g/A,b/N
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
e
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
r/P,o/G,y/S,g/A,b/N
ecclesiastical
#

:
1
4

Those who want to test their own abilities in this place are recommended to stop at creating their own problem solving, and then come back to compare their thoughts with ours.

The first (wrong) solution to this problem, which occurred to me almost instantly, is:

1. For each color, select the type of waste that is represented by this color in the maximum number of cities
2. Create a color matching scheme for waste types that were selected in paragraph 1.
3. Choose a city whose scheme of distribution of waste types by color is as close as possible to the scheme of paragraph 2.

Unfortunately, it turned out that such a solution is incorrect, if only because sometimes cities with the same pattern as the reference scheme (selected in paragraph 2) are encountered. Here's a counterexample:

r / P, o / G, y / S, g / A, b / N
r / P, o / S, y / A, g / N, b / G
r / S, o / G, y / P, g / N, b / G
r / A, o / S, y / P, g / N, b / G
r / G, o / S, y / P, g / A, b / N

Reference scheme in accordance with clause 2:
r / Po / S, y / P, g / N, b / G

The second and fourth cities are equally similar to the elaborated scheme; the topic is no less; when choosing a city No. 4, the number of changes in other cities is less than when choosing a city No. 2.

The second option : I decided to count how many changes would need to be made if, in turn, I selected all cities as a standard. Those. I calculated for each city its total difference from all other cities.

Initially, this solution seemed to me not optimal, it seemed that it would certainly go beyond the time limit. But let's try to estimate how much time it takes to calculate the number of differences of each city from all the others.

Each city must be compared with all the others, and there will be 5 comparisons, for each color, i.e. 5 (n-1) comparisons for each city, where n is the number of cities. In total there are 5n (n-1) comparisons for all cities. If we take into account the fact that there are no more than 100 cities, then the number of comparisons does not exceed 5 * 100 * 99 = 49500. Comparison operations will also be accompanied by incrementing the counter differences of each city. But even in the sum, under the worst conditions, the number of operations will not exceed 49,500 comparisons and 49,500 unit addition operations. It becomes clear that our algorithm will be executed in a very short period of time, even on the most difficult tests.

Let us try to calculate the number of differences for one of the examples and the previous counterexample to the variant of solution No. 1:

Scheme	The number of differences from other cities
r / P, o / G, y / S, g / A, b / N r / G, o / P, y / S, g / A, b / N r / P, y / S, o / G, g / N, b / A r / P, o / S, y / A, g / G, b / N	1 + 2 + 1 + 2 + 1 = 7 <- the best option 3 + 3 + 1 + 2 + 1 = 10 1 + 2 + 1 + 3 + 3 = 10 1 + 3 + 3 + 3 + 1 = 11
r / P, o / G, y / S, g / A, b / N r / P, o / S, y / A, g / N, b / G r / S, o / G, y / P, g / N, b / G r / A, o / S, y / P, g / N, b / G r / G, o / S, y / P, g / A, b / N	3 + 3 + 4 + 3 + 3 = 16 3 + 2 + 4 + 2 + 2 = 13 4 + 3 + 2 + 2 + 2 = 13 4 + 2 + 2 + 2 + 2 = 12 <- the best option 4 + 2 + 2 + 3 + 3 = 14

Actually it remains to implement our plans and carry to the judges . And here is my solution in C ++.

Accepted (0.012). Good luck!