Olympiad hobby. Waste disposal task

Hey. You have an olympiad hobby. Here we select the Olympiad programming task for ourselves, analyze it, develop possible solutions and implement our plan, and 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.

Have you forgotten to stretch yourself? If you forgot, then quickly warm up, and come back to us.

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

Brief translation of the problem statement (free translation): Kerbside

garbage collection technology arrived in New Zealand. Five waste bins of different colors: red (red), orange (orange), yellow (yellow), green (green) and blue (blue), which identify 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 was able to solve all the unimportant tasks (such as the reorganization of healthcare, social security and education), it decided to tackle other problems. The Minister of Environmental Protection submitted to Parliament a document on regulating the compliance of types of waste with colored baskets, but for this he needs to choose his own distribution of waste by color. A proponent of democracy, he explored all cities, who use Kerbside. Using the data he wants to choose a city whose pattern of matching waste types to colored baskets (being common throughout the country) will cause the least amount of change. The size of the city does not matter, according to democracy: 1 city - 1 vote.

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

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

Output : For each incoming block, you need to display the serial number of the city whose distribution scheme should be selected 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

For those who want to test their own abilities, in this place it is recommended to interrupt to create their own solution to the problem, and then return to compare their thoughts with ours.

The first (wrong) solution to this problem that came to my mind almost instantly is this:

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

Unfortunately, it turned out that such a decision was wrong, if only because sometimes cities with the same similarity with the reference scheme (selected in paragraph 2) are found. Here is 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 according to paragraph 2 :
r / Po / S, y / P, g / N, b / G

The second and fourth cities are equally similar to the developed 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 calculate how many changes will need to be made if all cities are selected as a standard in turn. Those. I calculated for each city its total difference from all other cities.

Initially, it seemed to me such a solution was not optimal, it seemed that it would certainly go beyond the time limit. But let's try to estimate how much time this calculation of the number of differences between each city and all the others will take.

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, the number of comparisons does not exceed 5 * 100 * 99 = 49500. Comparison operations will also be accompanied by operations to increase the counter differences of each city. But even in total, under the worst conditions, the number of operations will not exceed 49,500 comparisons and 49,500 operations adding units. It becomes clear that our algorithm will be executed in a very short period of time even on the most complex tests.

Let's try to calculate the number of differences for one of the examples and the previous counterexample to 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 is 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 the plan and bring it to the judges . And here is my solution in C ++.

Accepted (0.012). Good luck