PEG Test '14 - Fire - Olympiads Online Judge

PEG Test '14 - Fire

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 1.0s

Memory limit: 16M

Author:

frenzybenzy

Problem types

PEG Test – Oct 3rd, 2014

Firebending is an intense and aggressive bending art which uses concentrated barrages of fire, controlled by one's inner chi to overwhelm opponents. According to uncle Iroh, fire is the element of power. Of course, with great power comes great responsibility. Aang has just gained a new friend and firebending master, Zuko, to teach him the ways of the dragons.

In the past, Aang has attempted firebending on his own. However, due to a serious incident where he accidentally burned Katara, he's learned that fire is not to be toyed with. Ever since, Aang has been scared of firebending. Zuko realized what he must do – to teach Aang control. Only when Aang feels completely in control can his true training begin.

As an exercise, Zuko places $N$ $N$ $(1 \le N \le 10^4)$ $(1 \leq N \leq 10^{4})$ leaves in front of Aang. He simultaneously sets all of the leaves on fire. Aang's job must be to control the burning rate of the leaves. The leaves all start burning from the inside. The $i^\text{th}$ $i^{th}$ leaf $(1 \le i \le N)$ $(1 \leq i \leq N)$ will spend $s_i$ $s_{i}$ $(1 \le s_i \le 10^6)$ $(1 \leq s_{i} \leq 10^{6})$ seconds burning before it is completely gone.

Aang is very new at this, and can only handle a certain amount of leaves at once. Throughout the entire exercise, he is currently only able to focus his chi onto at most $K$ $K$ $(1 \le K \le N)$ $(1 \leq K \leq N)$ leaves. When Aang focuses on a leaf, the time it takes for the leaf to completely burn out will double. Aang will pick the $K$ $K$ leaves at the beginning of the exercise and cannot switch after he's made the decision. Can you help Aang determine the time it takes for the first leaf to burn out?

Input Specification

Line 1: Two integers $N$ $N$ and $K$ $K$ , respectively representing the number of total leaves and the number of leaves Aang can focus on controlling.
Line 2: $N$ $N$ space-separated integers $s_1, s_2, \dots, s_N$ $s_{1}, s_{2}, \dots, s_{N}$ , representing the time it takes for each leaf to burn out without Aang's interference.

Output Specification

A single integer representing the number of seconds until the earliest leaf to burn out has fully burned out.

Sample Input 1

Copy

10 3
8 7 3 8 5 5 6 3 9 3

Sample Output 1

Copy

Sample Input 2

Copy

1 1
3

Sample Output 2

Copy

Comments

1

Humanthe2nd commented 57 days ago ← edited →

The statement claims, $(1 \leq K \leq N)$ $(1 \leq K \leq N)$ . However, there is a case where $K$ $K$ is equal to zero. https://dmoj.ca/submission/6933803

8

planT_444 commented on June 16, 2021, 8:17 p.m.

Could the problem statement mention that Aang wants to make time it takes before the first leaf burns out as long as possible?

I was kind of confused about which leaves he wanted to choose, I didn't understand what the point was.

0

RandomPerson123 commented on Dec. 25, 2023, 1:53 p.m. ← edited →

I agree. They didn't make it clear.