sainiarpit12's blog

Problem Solution Ideas for the given problem ??
By sainiarpit12, history, 8 years ago, In English

There are n classes in which there are a1,a2,..an students in each class. You have given b cakes (b >= n) , you have to divide the cakes in each class such that the number of students per cake in each class is minimum and each class should have atleast 1 cake in it. You need to find the maximum number of students per cake in any class such that cakes are divided in each class optimally. How should I approach? First I give 1 cake to each class. Then I left with b-n cakes , how one should distribute it optimally ?? Lets say I give x1 cakes to class 1 and x2 to class 2 and so on such that x1+x2+..+xn = b and ans = find max( a1/x1 , a2/x2 ,...,an/xn) Sample Input 1 2 7 20 50 ans = 10 , I give 2 cake to class 1 and 5 cake to class 2. Sample Input 2 6 7 1 1 1 1 1 10 ans = 5 , I give 1 cake to first 5 class and then 2 to last class , so ans = 10/2 which is maximum . Thanks for any solutions.

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sainiarpit12 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Binary search on answer. for each value m, give each class cakes until the ratio is less than or equal to m.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks , But can you tell me with some more explanation or with some sample example? I didn't got it through.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Use binary search to find the best ratio. for each value (i.e. mid value) do the following:
      for each class, keep giving it cakes until the ratio (students/cakes) for this class is less than or equal to the mid value. if you ran out of cakes and some class has a ratio larger than the mid value, try searching for larger ratios. otherwise search for smaller ratios.

      → Reply