PEG Test – Oct 3rd, 2014

Problem C: Fire

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 (1 ≤ N ≤ 10⁴) 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-th leaf (1 ≤ i ≤ N) will spend s_i (1 ≤ s_i ≤ 10⁶) 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 (1 ≤ K ≤ 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 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 Format

Line 1: Two integers N and K, respectively representing the number of total leaves and the number of leaves Aang can focus on controlling.
Line 2: N space-separated integers s₁, s₂, … s_N, respresenting the time it takes for each leaf to burn out without Aang's interference.

Output Format

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

Sample Input 1

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

Sample Output 1

5

Sample Input 2

1 1
3

Sample Output 2

6

All Submissions
Best Solutions

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 06, 2014
Author: frenzybenzy

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

could anyone tell me why im getting the last 2 test cases wrong?

You are not using some of your variables.

SUPER_ET_DUPER on Dec 03, 2014 - 12:41:36 am UTC Don't get the question

• (0/0)

How do you know witch leaves Aang picks?

What are you supposed to find?

How do you know witch leaves Aang picks?

What are you supposed to find?

Hzhang on Dec 04, 2014 - 12:03:10 am UTC Re: Don't get the question

• (3/0)

You choose the leaves that Aang picks, and you find the maximum amount of time before the first leaf runs out of time.

In the sample input Aang gets 3 leaves in which he can double the durability

The most logical decisions is to pick:

8 7 [color=red][b]3[/b][/color] 8 5 5 6 [color=red][b]3[/b][/color] 9 [color=red][b]3[/b][/color]

That leaves the 2 fives as the fastest burning leaves.

so you output 5 because the first leaves burn at 5 seconds.

:wink:

You choose the leaves that Aang picks, and you find the maximum amount of time before the first leaf runs out of time.

In the sample input Aang gets 3 leaves in which he can double the durability

The most logical decisions is to pick:

8 7 3 8 5 5 6 3 9 3

That leaves the 2 fives as the fastest burning leaves.

so you output 5 because the first leaves burn at 5 seconds.