Država
레이팅 미적용의견: 0
\(2^{th}\) round, November \(7^{th}\) 2015
A distant country has \(N\) cities in it. The elections were just held in this country, so the new prime
minister was elected. Currently, there is not a single road in this country, so the prime minister decided
to modernize the country by connecting some cities with t\(wo-wa\)y highways and form counties. Two
cities will be located in the same county if it is possible to get to one city from the other using the
newly built roads. Each city will be located in exactly one county. Each conty consists of one or
more cities.
The cities are represented as points in a t\(wo-di\)mensional coordinate system. The road between two
cities is represented as a line segment connecting two points where the cities are located. The length
of the road is equal to the length of the line segment in kilometers.
The country is currently suffering from recession, so the prime minister decided that, because of the
lack of budget, they will not build roads longer than \(D\) kilometers. Additionally, the prime minister
is happy about the small things, so he will be happy if, in at least one county, there exists a nonempty
subset of cities (it can include all cities in the county) where the total sum of residents is divisible by
\(K\). For instance, if \(K = 4\) and there is a county with cities that have 3, 5, 7 residents respectively, the
prime minister will be happy because the sum of residents in the first two cities is equal to 8.
Help the prime minister in cutting the costs by determining the minimal \(D\) such that the prime minister
can build roads and be happy about the small things at the same time.
In test cases worth 40% of points the number of cities \(N\) will be less than or equal to 1000.
The first line of input contains the integers \(N\) and \(K\) (1 ⩽\(N\) ⩽50 000, 1 ⩽\(K\) ⩽30). Each of the
following \(N\) lines contains three integers \(x@@RISE_MATH_BLOCK_0@@i\), y\(i\), k\(i\) ⩽100 000 000), that represent the \(x\)
coordinate of the city, the \(y\) coordinate and the number of residents in that city, respectively. There
will not be two cities with the same coordinates in the input data. Additionally, there will not be a
single city with the number of residents divisible by \(K\).
The first and only line of output must contain the minimal \(D\) such that it is possible to build roads
with the condition that the prime minister is happy. Output \(D\) rounded to 3 decimal places. The
input data will be such that there is always a solution.
3 3
0 4 4
1 5 1
2 6 1
6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10
6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3output
output
1.414
5.657
2.000Clarification of the first example: The only way to keep the prime minister happy is if all the cities are in
the same county. The minimal D for which that is possible is 1.414.
Clarification of the second example: The prime minister will be happy if the first 5 cities are in the same
county. If D = 5.657, the prime minister can connect cities 1, 2, 3, 5 with city 4. In that case, the sum of
residents in cities 1, 2, 3, 4, 5 will be 11, which is divisible by 11, so the prime minister will be happy.
평가 및 의견
Država
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Država