Today is the 1055th birthday of Thor, God of Thunder (also, for posterity, today is Thorsday in Asgard). All the citizens of Asgard have been invited to assist in surprising Thor when he enters the Halls of Valhalla. Unfortunately, there are a limited number of hiding places in the throne room of Valhalla: N to be exact. Also, the citizens of Asgard are quite picky with regard to the people they hide with. Initially, Asgard is divided into M towns and each town has claimed exactly one hiding place in the throne room. This means that, initially, M distinct hiding places in the throne room are occupied, one for each town. To maximize the space, people from one hiding spot can divide into two groups and one of the groups can choose another vacant hiding spot if available, occupying one additional hiding place. This means the citizens from the M towns will always be hiding with people from the same town, because the towns don't necessarily get along and don't like to mix with each other. Since it will be easier for Thor to see the Asgardians if there are more people in one hiding spot, they must divide themselves such that the maximum number of people in one hiding spot is minimized. Input Format Input consists of a single test case. The first line contains two space-separated integers N and M denoting the number of hiding places in the throne room of Valhalla and the number of towns respectively. M lines follow, the ith of which contains a single integer P; denoting the number of people in the ith town. (The tranquiline halls of Valhalla have very large hiding places, so P; can easily reach to high values and the hiding places can still accommodate the citizens.) Constraints 1 ≤ M≤N ≤ 105 1 ≤ P ≤ 10⁹

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

100%

Information is present in the screenshot and below. Based on that need help in solving the code for this problem in java. The time complexity has to be as less as possible (nlogn or n at best, no n^2). Apply greedy algorithm in the problem. Make sure all test cases return expected outputs.

Output Format
The output consists of one line, which is the maximal number of citizens hiding in one hiding place given the optimal division of the citizens as described in the problem statement. The optimal division is the division where the maximal citizens hiding in one hiding spot are minimized.

Sample Input 0
3 1
10

Sample Output 0
4

Explanation 0
They can split as follows

4 citizens from town 1
3 citizens from town 1
3 citizens from town 1

The maximum number of citizens in one hiding place is 4.

Sample Input 1
6 2
12
5

Sample Output 1
3

Explanation 1

They can split as follows

3 citizens from town 1
3 citizens from town 1
3 citizens from town 1
3 citizens from town 1
3 citizens from town 2
2 citizens from town 2

The maximum number of citizens in one hiding place is 3.

Sample Input 2
10 5
2
3
1
1
4

Sample Output 2
2

Explanation 2

They can split as follows:

2 citizens from town 1
1 citizen from town 2
1 citizen from town 2
1 citizen from town 2
1 citizen from town 3
1 citizen from town 4
1 citizen from town 5
1 citizen from town 5
1 citizen from town 5
1 citizen from town 5

The maximum number of citizens in one hiding place is 2.

Sample Input 3
4 4
12
10
5
1

Sample Output 3
12

Sample Input 4
10 5
2
3
1
100
4

Sample Output 4
17

The actual code

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] parts = br.readLine().trim().split(" ");
int p = Integer.parseInt(parts[0]);
int n = Integer.parseInt(parts[1]);
int[] towns = new int[n];
for(int i = 0; i < n; i++) {
towns[i] = Integer.parseInt(br.readLine().trim());
}
System.out.println(solve(p,n,towns));
}

public static int solve(int p, int n, int[] towns) {
// solve for answer here

}
}