Connection Status:
Competition Arena > TheOlympiadInInformatics

TheOlympiadInInformatics

TCO13 Round 1C · 2013-02-19 · by Vasyl[alphacom]

TCO13 Round 1C · 2013-02-19 · by Vasyl[alphacom] · Simple Search, Iteration
Class Name: TheOlympiadInInformatics
Return Type: int
Method Name: find
Arg Types: (vector<int>, int)
Problem Statement

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.

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
0)
{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).

1)
{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.

2)
{999999999}
1000000000
Returns: 0

Here it is enough to gain 0 points.

3)
{95, 23, 87, 23, 82, 78, 59, 44, 12}
70
Returns: 6
4)
{31}
99
Returns: 0

Submissions are judged against all 169 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheOlympiadInInformatics with a public method int find(vector<int> sums, int k) · 169 test cases · 2 s / 256 MB per case

Submitting as anonymous