A group of N children, who are numbered 1, 2, . . . , N, want to play hide and seek. In a single round of hide and seek, there will one seeker, and N −1 hiders. Children like to hide and not seek and each child has her own idea of how many times she would like to hide. You will be given for each child i, a number H[i] denoting the number of rounds she would like to be a hider. She will be satisfied only if she gets to be a hider in at least H[i] rounds.
For example, suppose N = 4, and H[1] = 1, H[2] = 3, H[3] = 2 and H[4] = 1. Here is one way to satisfy them all. In Round 1, Child 1 is the seeker, and in Rounds 2 and 3, Child 4 is the seeker. Then Child 1 has been a hider in 2 Rounds, Child 2 has been a hider in 3 Rounds, Child 3 has been a hider in 3 Rounds, and Child 4 has been a hider in 1 Round. Thus, they are all satisfied. You can check it is not possible to satisfy all of them in fewer than 3 Rounds.
You aim is to determine the least number of rounds that needs to be played so that every child is satisfied. For the example in the previous paragraph, the answer is 3.
Determine the minimum number of rounds needed in the following cases: **(a) N = 7, H[1] = 6, H[2] = 13, H[3] = 9, H[4] = 5, H[5] = 15, H[6] = 8, H[7] = 9.
(b) N = 12 H[1] = 6, H[2] = 7, H[3] = 7, H[4] = 8, H[5] = 9, H[6] = 9, H[7] = 9, H[8] = 9, H[9] = 9, H[10] = 9, H[11] = 9, H[12] = 9**
(c) N = 15 H[1] = 131, H[2] = 135, H[3] = 130, H[4] = 138, H[5] = 132, H[6] = 140, H[7] = 137, H[8] = 133, H[9] = 131, H[10] = 137, H[11] = 138, H[12] = 132, H[13] = 135, H[14] = 136, H[15] = 134.
Is there any mathematical or algorthmic way to solve this problem. Ans:- (a) 15 (b) 10
My attempt:- For (a) , H[4] can be seeker 6 times so H{1] get satisifed, and then H[1] will be next seeker for 9 times, so the rest like H[5] get satisfied.
I can't think about (b).