Information is present in the screenshot and below. Based on that need help in solving the code for this problem in python. 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 both test cases return correct answers.Output FormatThe 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 03 110Sample Output 04Explanation 0They can split as follows4 citizens from town 13 citizens from town 13 citizens from town 1The maximum number of citizens in one hiding place is 4.Sample Input 16 2125Sample Output 13Explanation 1They can split as follows3 citizens from town 13 citizens from town 13 citizens from town 13 citizens from town 13 citizens from town 22 citizens from town 2The maximum number of citizens in one hiding place is 3.Sample Input 210 523114Sample Output 22Explanation 2They can split as follows:2 citizens from town 11 citizen from town 21 citizen from town 21 citizen from town 21 citizen from town 31 citizen from town 41 citizen from town 51 citizen from town 51 citizen from town 51 citizen from town 5The maximum number of citizens in one hiding place is 2.Sample Input 34 4121051Sample Output 312Sample Input 410 52311004Sample Output 417The actual codep,n = list(map(int,input().rstrip().split(" ")))towns = [input().rstrip() for i in range(n)]# compute for answer Today is the 1055th birthday of Thor, God of Thunder (also, for posterity, today is Thorsday in Asgard). All thecitizens 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 throneroom. 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 canchoose another vacant hiding spot if available, occupying one additional hiding place. This means the citizensfrom the M towns will always be hiding with people from the same town, because the towns don't necessarilyget 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 mustdivide themselves such that the maximum number of people in one hiding spot is minimized.Input FormatInput consists of a single test case. The first line contains two space-separated integers N and M denotingthe 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 thehiding places can still accommodate the citizens.)Constraints1 ≤ M≤N ≤ 1051 ≤ P ≤ 10⁹

A greedy algorithm which refers to the one it is an approach for solving a problem by…

Information is present in the screenshot and below. Based on that need help in solving the code for this problem in python. 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 both test cases return correct answers. 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 p,n = list(map(int,input().rstrip().split(" "))) towns = [input().rstrip() for i in range(n)] # compute for answer

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Information is present in the screenshot and below. Based on that need help in solving the code for this problem in python. 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 both test cases return correct answers.

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

p,n = list(map(int,input().rstrip().split(" ")))
towns = [input().rstrip() for i in range(n)]
# compute for answer

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⁹

Expert Solution

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.