Singing Competition :
Difficulty Level : Medium
Submissions : 157
Asked In :
Marks :30
: 9 | : 1
Rose a music professor, decides to organize a group song competition in the Music Universe College. $$$N$$$ number of departments will participate in the singing competition. Each department has $$$M$$$ number of groups that want to participate. Rose decides the initial size of the groups in every department. The competition is organized in such a way that all the groups from the same department will sing on the stage together at the same time. Each department will sing in succession
The music department has some mics that they will distribute to the groups and they will assign one mic to each group. In case they have surplus mics, they will regroup the students so that the number of students sharing each mic is minimized.
After re-grouping Rose needs to find the number of students in the largest group from each department who are sharing a mic.
Write an algorithm to help Rose calculate the number of students in the largest group from each department who are sharing a mic after re-grouping.
The first line of the input consists of three space separated integers - $$$N$$$, $$$M$$$ and $$$mic$$$, representing the number of departments of the college, the number of groups from each department and the number of mics, respectively.
The next $$$N$$$ lines consist of M space-separated integers- $$$g[0], g[1].....g[M-1]$$$, representing the initial size of the group from each department.
Print $$$N$$$ space-separated integers representing the number of students in the largest groups from each department who are sharing a mic after re-grouping.$$$(1 \le N,M \le 10^3)$$$$$$(1\le mic \le 10^6)$$$$$$(1 \le g[i] \le 10^9).$$$
2 5 7 10 8 6 4 3 12 10 8 4 5
6 8
1- The number of mics is more than or equal to the initial number of groups from each department.
2- Here the regrouping happens for each group of the department and not for the total number of students in the department.
Explanation Test Case 1:
In the first test case i.e. given $$$N$$$ is $$$2$$$, M is $$$5$$$, and no of mics is $$$7$$$. Also, the initial grouping is given as $$$10$$$ $$$8$$$ $$$6$$$ $$$4$$$ $$$3$$$.
The re-grouping would happen in the following manner $$$6$$$($$$10$$$),$$$4$$$($$$10$$$),$$$6$$$($$$8$$$), $$$2$$$($$$8$$$), $$$6$$$($$$6$$$), $$$4$$$($$$4$$$), $$$3$$$($$$3$$$).[(num) denotes original group from which breakdown happens].
Hence the maximum number of students in a group is $$$6$$$.
