Milk Man and His Bottles

A Milkman serves milk in packaged bottles of varied sizes. The possible size of the bottles are {1, 5, 7 and 10} litres. He wants to supply desired quantity using as less bottles as possible irrespective of the size. Your objective is to help him find the minimum number of bottles required to supply the given demand of milk.
Input Format:
First line contains number of test cases N
Next N lines, each contain a positive integer Li which corresponds to the demand of milk.
Output Format:
For each input Li, print the minimum number of bottles required to fulfill the demand
Constraints:
1 <= N <= 1000
Li > 0
1 <= i <= N
Sample Input and Output
SNo. Input Output
1
2
17
65
2
7
Explanation:
Number of test cases is 2
1. In first test case, demand of milk is 17 litres which can be supplied using minimum of 2 bottles as follows
o 1 x 10 litres and
o 1 x 7 litres
2. In second test case, demand of milk is 65 litres which can be supplied using minimum of 7 bottles as follows
o 6 x 10 litres and
o 1 x 5 litres

Showing Answers 1 - 7 of 7 Answers

john

  • Aug 7th, 2015
 

Code
  1. int main()

  2. {

  3.    int n, first = 0, second = 1, next, c;

  4.  

  5.    printf("Enter the number of puk

  6. ");

  7.    scanf("%d",&n);

  8.  

  9.    printf("First %d terms of fate sanka are :-

  10. ",n);

  11.  

  12.    FOR ( c = 0 ; c < n ; c++ )

  13.    {

  14.       IF ( c <= 1 )

  15.          next = c;

  16.       else

  17.       {     //mlik man will save you FROM code vita

  18.          next = first + second;

  19.          first = second;

  20.          second = next;

  21.       }

  22.       printf("%d

  23. ",next);

  24.    }

  25.  

  26.    RETURN 0;

  27. }

  Was this answer useful?  Yes

john

  • Aug 7th, 2015
 

Code
  1. #include <stdio.h>

  2. #include <stdlib.h>

  3.  

  4. #define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

  5.  

  6. static int total_nodes;

  7. // prints subset found

  8. void printSubset(int A[], int size)

  9. {

  10.     for(int i = 0; i < size; i++)

  11.     {

  12.         printf("%*d", 5, A[i]);

  13.     }

  14.  

  15.     printf("

  16. ");

  17. }

  18.  

  19. // inputs

  20. // s            - set vector

  21. // t            - tuplet vector

  22. // s_size       - set size

  23. // t_size       - tuplet size so far

  24. // sum          - sum so far

  25. // ite          - nodes count

  26. // target_sum   - sum to be found

  27. void subset_sum(int s[], int t[],

  28.                 int s_size, int t_size,

  29.                 int sum, int ite,

  30.                 int const target_sum)

  31. {

  32.     total_nodes++;

  33.     if( target_sum == sum )

  34.     {

  35.         // We found subset

  36.         printSubset(t, t_size);

  37.         // Exclude previously added item and consider next candidate

  38.         subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);

  39.         return;

  40.     }

  41.     else

  42.     {

  43.         // generate nodes along the breadth

  44.         for( int i = ite; i < s_size; i++ )

  45.         {

  46.             t[t_size] = s[i];

  47.             // consider next level node (along depth)

  48.             subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);

  49.         }

  50.     }

  51. }

  52.  

  53. // Wrapper to print subsets that sum to target_sum

  54. // input is weights vector and target_sum

  55. void generateSubsets(int s[], int size, int target_sum)

  56. {

  57.     int *tuplet_vector = (int *)malloc(size * sizeof(int));

  58.  

  59.     subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

  60.  

  61.     free(tuplet_vector);

  62. }

  63.  

  64. int main()

  65. {

  66.     int weights[] = {10, 7, 5, 18, 12, 20, 15};

  67.     int size = ARRAYSIZE(weights);

  68.  

  69.     generateSubsets(weights, size, 35);

  70.     printf("Nodes generated %d

  71. ", total_nodes);

  72.     return 0;

  73. }

  74. Run on IDE

  75. The power of backtracking appears when we combine explicit and implicit constraints, and we stop generating nodes when these checks fail. We can improve the above algorithm by strengthening the constraint checks and presorting the data. By sorting the initial array, we need not to consider rest of the array, once the sum so far is greater than target number. We can backtrack and check other possibilities.

  76.  

  77. Similarly, assume the array is presorted and we found one subset. We can generate next node excluding the present node only when inclusion of next node satisfies the constraints. Given below is optimized implementation (it prunes the subtree if it is not satisfying contraints).

  78.  

  79. #include <stdio.h>

  80. #include <stdlib.h>

  81.  

  82. #define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

  83.  

  84. static int total_nodes;

  85.  

  86. // prints subset found

  87. void printSubset(int A[], int size)

  88. {

  89.     for(int i = 0; i < size; i++)

  90.     {

  91.         printf("%*d", 5, A[i]);

  92.     }

  93.  

  94.     printf("

  95. suls");

  96. }

  97.  

  98. // qsort compare function

  99. int comparator(const void *pLhs, const void *pRhs)

  100. {

  101.     int *lhs = (int *)pLhs;

  102.     int *rhs = (int *)pRhs;

  103.  

  104.     return *lhs > *rhs;

  105. }

  106.  

  107. // inputs

  108. // s            - set vector

  109. // t            - tuplet vector

  110. // s_size       - set size

  111. // t_size       - tuplet size so far

  112. // sum          - sum so far

  113. // ite          - nodes count

  114. // target_sum   - sum to be found

  115. void subset_sum(int s[], int t[],

  116.                 int s_size, int t_size,

  117.                 int sum, int ite,

  118.                 int const target_sum)

  119. {

  120.     total_nodes++;

  121.  

  122.     if( target_sum == sum )

  123.     {

  124.         // We found sum

  125.         printSubset(t, t_size);

  126.  

  127.         // constraint check

  128.         if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )

  129.         {

  130.             // Exclude previous added item and consider next candidate

  131.             subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);

  132.         }

  133.         return;

  134.     }

  135.     else

  136.     {

  137.         // constraint check

  138.         if( ite < s_size && sum + s[ite] <= target_sum )

  139.         {

  140.             // generate nodes along the breadth

  141.             for( int i = ite; i < s_size; i++ )

  142.             {

  143.                 t[t_size] = s[i];

  144.  

  145.                 if( sum + s[i] <= target_sum )

  146.                 {

  147.                     // consider next level node (along depth)

  148.                     subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);

  149.                 }

  150.             }

  151.         }

  152.     }

  153. }

  154.  

  155. // Wrapper that prints subsets that sum to target_sum

  156. void generateSubsets(int s[], int size, int target_sum)

  157. {

  158.     int *tuplet_vector = (int *)malloc(size * sizeof(int));

  159.  

  160.     int total = 0;

  161.  

  162.     // sort the set

  163.     qsort(s, size, sizeof(int), &comparator);

  164.  

  165.     for( int i = 0; i < size; i++ )

  166.     {

  167.         total += s[i];

  168.     }

  169.  

  170.     if( s[0] <= target_sum && total >= target_sum )

  171.     {  //mlikman will save you from code vita

  172.  

  173.         subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

  174.  

  175.     }

  176.  

  177.     free(tuplet_vector);

  178. }

  179.  

  180. int main()

  181. {

  182.     int weights[] = {15, 22, 14, 26, 32, 9, 16, 8};

  183.     int target = 53;

  184.  

  185.     int size = ARRAYSIZE(weights);

  186.  

  187.     generateSubsets(weights, size, target);

  188.  

  189.     printf("pukss generated %d

  190. ", total_nodes);

  191.  

  192.     return 0;

  193. }

  Was this answer useful?  Yes

Code
  1. #include <stdio.h>

  2.  

  3. int main(void) {

  4.     int t;

  5.     scanf("%d",&t);

  6.     while(t--)

  7.     {

  8.         int n,b,k,l;

  9.         scanf("%d",&n);

  10.         b=n/10;

  11.         k=n%10;

  12.         if(k!=0)

  13.         {

  14.         printf("%d",b+1);

  15.         }

  16.         else

  17.         {

  18.             printf("%d",b+0);

  19.         }

  20.     }

  21.     // your code goes here

  22.     return 0;

  23. }

  24.  

  Was this answer useful?  Yes

Ritobrata Choudhury

  • Aug 7th, 2015
 

Code
  1. #include<stdio.h>

  2. int process(int num)

  3. {

  4.     int k1=0,k2=0,num2=num;

  5.     while(num>0)

  6.     {

  7.         if(num%10==0)

  8.         {

  9.             k1=k1+num/10;

  10.             num=num%10;

  11.         }

  12.         else if(num%7==0)

  13.         {

  14.             k1=k1+num/7;

  15.             num=num%7;

  16.         }

  17.         else if(num%5==0)

  18.         {

  19.             k1=k1+num/5;

  20.             num=num%5;

  21.         }

  22.         else

  23.         {

  24.             k1=k1+num;

  25.             num=0;

  26.         }

  27.  

  28.     }

  29.     while(num2>0)

  30.     {

  31.             if(num2>=10)

  32.                 num2=num2-10;

  33.             else if(num2>=7)

  34.                 num2=num2-7;

  35.             else if(num2>=5)

  36.                 num2=num2-5;

  37.             else

  38.                 num2=num2-1;

  39.             k2++;

  40.     }

  41.     if(k1>k2)

  42.         return k2;

  43.     else

  44.         return k1;

  45. }

  46. void main()

  47. {

  48.     int a[1000];

  49.     int n,i,num;

  50.     //printf("Enter Number of test cases:--");

  51.     scanf("%d",&n);

  52.     for(i=0;i<n;i++)

  53.     {

  54.         //printf("Enter a number >0:--");

  55.         scanf("%d",&num);

  56.         a[i]=process(num);

  57.     }

  58.     for(i=0;i<n;i++)

  59.     {

  60.         printf("%d

  61. ",a[i]);

  62.     }

  63.  

  64. }

  65.  

  Was this answer useful?  Yes

Bikash Choudhury

  • Aug 27th, 2015
 

Code
  1. #include<iostream>

  2. using namespace std;

  3. int TestCase(int Num);

  4.  

  5.  

  6. int main()

  7. {

  8.         int N,Num,c=0,i=0;

  9.  

  10.         cin>>N;

  11.         for(i=0;i<N;i++)

  12.         {

  13.                 cin>>Num;

  14.                 c=TestCase(Num);

  15.                 cout<<c<<endl;

  16.         }

  17.  

  18. return 0;

  19. }

  20.  

  21.         int TestCase(int Num)

  22.         {

  23.                 int mod=Num%10,c=0;

  24.                 switch(mod)

  25.                 {

  26. case 0 :c=(Num/10);break;

  27. case 1 :c=(Num/10)+1;break;

  28. case 2 :c=(Num/10)+2;break;

  29. case 3 :c=(Num/10)+3;break;

  30. case 4 :c=((Num-1)/10)+2;break;

  31. case 5 :c=(Num/10)+1;break;

  32. case 6 :c=(Num/10)+2;break;

  33. case 7 :c=(Num/10)+1;break;

  34. case 8 :c=(Num/10)+2;break;

  35. case 9 :c=((Num+10)/10)+1;break;

  36. default :break;

  37.                 }

  38.         return c;

  39.         }

  Was this answer useful?  Yes

lavanya

  • Jul 19th, 2016
 

Code
  1. #include<stdio.h>

  2. int main()

  3. {

  4.  int b,n,l;

  5.  scanf("%d",&n);

  6.  while(n>0)

  7.  {

  8.  scanf("%d",&l);

  9.  b=0;

  10.  while(l>0)

  11.  {

  12.  b++;

  13.  if(l>=10)

  14.   l=l-10;

  15.  else if(l>=7)

  16.   l=l-7;

  17.  else if(l>=5)

  18.   l=l-5;

  19.  else

  20.   l=l-1;

  21.  }

  22.  printf("%d

  23. ",b);

  24.  n--;

  25.  }

  26.  return 0;

  27. }

  Was this answer useful?  Yes

t3chn0tr0n

  • Jun 26th, 2019
 

Here is a take in Python.
Hope this helps.

Code
  1. def get_bottles(demand):

  2.     l = []

  3.     bottles = [1, 5, 7, 10]

  4.     for b in bottles:

  5.         if demand % b is 0:

  6.             l.append(int(demand / b))

  7.     demand_left = demand

  8.     bottles_needed = 0

  9.     i = 3

  10.     while demand_left != 0:

  11.         bottle_size = bottles[i]

  12.         if i != 0:

  13.             bottles_needed += int(demand_left / bottle_size)

  14.             demand_left -= int(demand_left / bottle_size) * bottle_size

  15.            

  16.             i -= 1

  17.         else:

  18.             bottles_needed += demand_left

  19.             demand_left = 0

  20.     l.append(bottles_needed)

  21.     print(min(l))

  22.  

  23.  

  24. n = int(input().strip())

  25. while n:

  26.     get_bottles(int(input().strip()))

  27.     n -= 1

  28.  

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions