I Would Walk 500 Miles
골드 II의견: 0
Farmer John wants to divide his \(N\) cows \((N \leq 7500)\), conveniently
numbered \(1 \ldots N\), into \(K\) non-empty
groups (\(2 \leq K \leq N\)) such that no two cows from two different groups can
interact with each other without walking some number of miles. Cow \(x\) and Cow \(y\) (where
\(1 \leq x < y \leq N\)) are willing to walk
\((2019201913x + 2019201949y)\text{ mod } 2019201997\) miles to see each other.
Given a division of the \(N\) cows into \(K\) non-empty groups, let \(M\) be the
minimum of the number of miles any two cows in two different groups are willing
to walk to see each other. To test the cows' devotion to each other, Farmer
John wants to optimally divide the \(N\) cows into \(K\) groups such that \(M\) is as
large as possible.
The memory limit for this problem is set to 512MB, above
the usual 256MB limit.
Problem credits: Brian Dean
Problem credits: Brian Dean
The input is just one line, containing \(N\) and \(K\), separated by a space.
Print out \(M\) in an optimal solution.
walk.inwalk.out3 22019201769In this example, Cow 1 and Cow 2 are willing to walk 2019201817 miles to see
each other. Cow 2 and Cow 3 are willing to walk 2019201685 miles. And Cow 1 and
Cow 3 are willing to walk 2019201769 miles. Thus, by grouping the cows such
that 1 is by herself and 2 and 3 are grouped together,
\(M = \min(2019201817,2019201769) = 2019201769\) (which is the best we can do
here).
평가 및 의견
I Would Walk 500 Miles
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
I Would Walk 500 Miles