Vrtić
레이팅 미적용의견: 0
2 \(s / 256\) \(MB / 160\) points
There are \(N\) children in a kindergarten, and each child considers one child to be their best
friend. Children are quite unusual, so it holds that no two children consider the same child
their best friend, but it is possible that a child is a best friend to themself! Additionally, if child
\(B\) is best friend of child \(A\) , \(A\) is not necessarily best friend of child \(B\) .
The kindergarten teacher has \(N\) bags of candy that she wishes to distribute to the children
such that each child gets exactly one bag. However, the problem is that the bags don’t
necessarily contain the same amounts of candy, so the children can become displeased.
Since the children have a very developed sense of justice, the dissatisfaction of child \(A\) is
equal to the absolute difference between the number of candy \(A\) and their best friend
received.
The kindergarten teacher has decided to distribute the bags so that the maximal
dissatisfaction of a child is as small as possible. Help her determine the optimal distribution
of candy bags!
In test cases worth 20% of total points, the best friend of the \(i\) {th}{ } child will be the the ( \(i+1\)) ^{th}
child for all \(i < N\), and the best friend of the \(N\) {th}{ } child will be the first child.
In additional test cases worth 30% of total points, it will hold \(N\) ≤ 20.
2 \(s / 256\) \(MB / 160\) points
The first line of input contains the integer \(N\) (1 ≤ \(N\) ≤ 150).
The second line of input contains \(N\) distinct integers, whereas the \(i\) ^{th} number is the label of
the best friend of the \(i\) {th}{ } child. The children are labelled with numbers from 1 to \(N\) .
The third line of input contains \(N\) integers, whereas the \(i\) ^{th} number is equal to the number of
candy in the \(i\) {th}{ } bag. The numbers won’t exceed 10 {9}{ }.
The first line of output must contain the minimum possible maximal dissatisfaction of a child.
The second line of output must contain \(N\) numbers, separated by space, whereas the \(i\) ^{th}
number denotes the number of candy for the \(i\) {th}{ } child. If there are multiple optimal
distributions, output any.
3
2 1 3
3 8 5
5
3 5 4 1 2
24 45 39 19 16
8
6 3 7 1 4 8 2 5
6 5 2 4 7 4 4 3output
output
2
5 3 8
8
16 39 24 19 45
2
3 4 4 4 6 5 2 7평가 및 의견
Vrtić
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Vrtić