TheOlympiadInInformatics | Topcoder Archive

Problem Statement

John takes part in a regional olympiad in informatics together with other participants. At the contest each participant gains some nonnegative integer score. Each participant (except for John) is assigned to one of the N contest rooms (numbered from 0 to N-1) and John is the only contestant in the room number N. John has no idea how many participants are in the other rooms. For each of the other rooms he only knows the sum of scores of all participants in it.

You are given a int[] sums containing N elements and an int k. The i-th element of sums is the sum of participants' scores in the i-th contest room. Return the minimal score John has to gain to be sure that there are at most k participants with strictly higher scores.

Definition

Class:: TheOlympiadInInformatics
Method:: find
Parameters:: int[], int
Returns:: int
Method signature:: int find(int[] sums, int k)
(be sure your method is public)

Constraints

sums will contain between 1 and 47 elements, inclusive.
Each element of sums will be between 0 and 1,000,000,000, inclusive.
k will be between 0 and 1,000,000,000, inclusive.

Examples

```
{4, 7, 0, 5}
```
```
0
```
```
Returns: 7
```
John has to gain at least 7 points, because there might be a competitor with 7 points in room number 1 (0-based index).
```
{4, 7}
```
```
2
```
```
Returns: 3
```
It is possible that there are three contestants who scored more than 2 points: there can be one in room 0 and two more in room 1. There can only be at most two contestants who scored more than 3 points: there can be at most one such contestant in each of the two rooms. (Note that the score of each contestant has to be an integer.) Therefore, John has to score at least 3 points.
```
{999999999}
```
```
1000000000
```
```
Returns: 0
```
Here it is enough to gain 0 points.

{95, 23, 87, 23, 82, 78, 59, 44, 12}

Returns: 6

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.