Olympiad#7503

Olympiad (Editorial)

A total of $s = \sum_{i = 1}^{n} a_{i}$ s = \sum_{i=1}^n a_i participants arrived at the competition. Since each classroom is equipped with $m$ computers, at least $⌈ s / m ⌉$ rooms are required.

Let $p$ be the largest number of participants in a single team (the maximum among all values $a_{i}$ a_i). If $p > ⌈ s / m ⌉$ p > ⌈s/m⌉, then at least $p$ rooms are needed.

It can be shown constructively that it is always sufficient to have $ma x (⌈ s / m ⌉, p)$ max(⌈s/m⌉, p) classrooms to conduct the olympiad.

Example

A total of $2 + 3 + 4 + 1 + 2 = 12$ 2 + 3 + 4 + 1 + 2 = 12 students arrived at the olympiad. Since each classroom is equipped with $3$ computers, at least $12/3 = 4$ 12 / 3 = 4 classrooms are required.

The largest team is the third one, with $4$ participants. They can be seated one by one in $4$ different classrooms.

For example, the following seating arrangement is possible:

Algorithm implementation

Read the input data.

scanf("%d %d",&n,&m);

Compute the total number of participants $s$ , as well as the size $p$ of the largest team.

p = 0;
for (i = 0; i < n; i++)
{
  scanf("%d",&x);
  s += x;
  if (x > p) p = x;
}

C++

The value $r es = ⌈ s / m ⌉$ res = ⌈s/m⌉ is computed as $(s + m - 1) / m$ (s + m - 1) / m.

res = (s + m - 1) / m;

If $p > ⌈ s / m ⌉$ p > ⌈s/m⌉, then the answer is $p$ .

if (res < p) res = p;

Print the answer.

printf("%d\n",res);