Milk Man and His Bottles

Problem : 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

C++ Program:

#include <iostream>
 using namespace std;

 int main() {
  int N,a,A[4]={1, 5, 7, 10};
  cin>>N;
  while(N--)
  {
   cin>>a;
   int sum = 0;
   for(int i=3;i>=0;i--)
   {
    sum+=a/A[i];
    a=a%A[i];
   }
   cout<<sum<<endl;
  }
  return 0;
 }

 

Optimum Cost Calculator

Problem : Optimum Cost Calculator

A town A is located on a river. We have to send cargo to town B which is located 'a' kilometers downstream and 'd' kilometers from the river. Government wants to construct a sea link between B and the river such that the cost of transportation of goods from A to B is the cheapest. The transport cost of a unit of cargo per kilometer by waterway is half the cost incurred by taking the highway.

Your task is to help the government find a point in the river from which to construct a highway to town B so that the government's objective of reducing transportation cost is achieved. More specifically, calculate the distance from town A where the highway has to be constructed and the length of the highway to be constructed.

Input Format:
First line contains the distance between A and C along the river denoted 'a'
Second line contains the distance between C and B along the road denoted by 'd'

Output Format:
Print the distance of the point in the river denoted by D from Town A.
Print the length of the highway that needs to be built from D to B.

OR

Print "Invalid Input", if any constraint is violated

Constraints:
0 < a <= (57 * d)
0 < d <= (1.7 * a)
Calculations and printing of output should be done upto 11­digit precision

Sample Input and Output

SNo. 1	Input 50 10	Output X= 44.22649730810 Y= 11.54700538379
2	40 10	X= 34.22649730810 Y= 11.54700538379
3	172 3	Invalid Input

Mathematical logic:
Cost = $$c = c_1 x + c_2y$$ where \(c_1\) is cost of travelling on water and \(c_2\) is cost of travelling on land. As per the given condition, $$c_1 = \frac{c_2}{2}$$ Hence the equation becomes: $$c = \frac{cx}{2} + cy$$
$$ => c = c(x/2 + y)$$
Also, as per the given figure, the relation between \(x\) and \(y\) can be represented as follows: $$y^2 = (a-x)^2 + d^2$$
$$=> y = \sqrt{(a-x)^2 + d^2}                               \cdots 1 $$                                                  
The objective is to minimize the cost function c. So $$ \frac{d}{dx}c[\frac{x}{2}+ \sqrt{(a-x)^2 + d^2}] = 0$$ Solving the above differential equation: $$\frac{1}{2} - \frac{2(a - x)}{2\sqrt{(a-x)^2 + d^2}} = 0$$ $$=> \frac{1}{2} = \frac{(a - x)}{\sqrt{(a-x)^2 + d^2}} $$ Squaring both sides, we get: $$=> \frac{1}{4} = \frac{(a - x)^2}{(a-x)^2 + d^2} $$ $$=> 4(a-x)^2 = (a-x)^2 + d^2$$ $$ => 3(a-x)^2 = d^2$$$$ => x = a - \frac{d}{\sqrt{3}}$$ From equation 1 above, $$y = \frac{2}{\sqrt3}d$$

Equation

Cost = $$c = c_1 x + c_2y$$ where \(c_1\) is cost of travelling on water and \(c_2\) is cost of travelling on land. As per the given condition, $$c_1 = \frac{c_2}{2}$$ Hence the equation becomes: $$c = \frac{cx}{2} + cy$$
$$ => c = c(x/2 + y)$$
Also, as per the given figure, the relation between \(x\) and \(y\) can be represented as follows: $$y^2 = (a-x)^2 + d^2$$
$$=> y = \sqrt{(a-x)^2 + d^2}                               \cdots 1 $$                                                  
The objective is to minimize the cost function c. So $$ \frac{d}{dx}c[\frac{x}{2}+ \sqrt{(a-x)^2 + d^2}] = 0$$ Solving the above differential equation: $$\frac{1}{2} - \frac{2(a - x)}{2\sqrt{(a-x)^2 + d^2}} = 0$$ $$=> \frac{1}{2} = \frac{(a - x)}{\sqrt{(a-x)^2 + d^2}} $$ Squaring both sides, we get: $$=> \frac{1}{4} = \frac{(a - x)^2}{(a-x)^2 + d^2} $$ $$=> 4(a-x)^2 = (a-x)^2 + d^2$$ $$ => 3(a-x)^2 = d^2$$$$ => x = a - \frac{d}{\sqrt{3}}$$ From equation 1 above, $$y = \frac{2}{\sqrt3}d$$

Robot's move

Problem : Robot's move

A robot is programmed to move forward F meters and backwards again, say B meters, in a straight line. The Robot covers 1 meter in T units of time. On Robot's path there is an obstacle after distance D from initial position in forward direction. This forward and backward movement is performed repeatedly by the Robot.

Your task is to calculate amount of time taken before the Robot hits the obstacle.

Input Format:
First line contains total number of test cases, denoted by N
Next N lines, contain a tuple containing 4 values delimited by space
F B T D, where

1. F denotes forward displacement in meters
2. B denotes backward displacement in meters
3. T denotes time taken to cover 1 meter
4. D denotes distance from Robot's starting position and the obstacle in forward direction

Output Format:

For each test case print time taken by the Robot to hit the obstacle

Constraints:

First move will always in forward direction

1 <= N <= 100

backward displacement < forward displacement i.e. (B < F)

forward displacement (F) > 0

backward displacement (B) > 0

time (T) > 0

distance (D) > 0

All input values must be positive integers only

Sample Input and Output

SNo.	Input	Output
1	2 5 4 8 10 8 2 3 15	400 69

Solution:
Find the distance to the point just before the last forward cycle starts. Find the time taken to reach this point. Beyond this point just add the time taken to take the forward steps.

C++ Program:

#include <iostream>
using namespace std;

int main(void) 
{
 int F,B,T,D;
 int N;
 cin>>N;
 while(N--)
 {
  cin>>F>>B>>T>>D;
  int forward = F-B; //The distance moved by robot in one forward and backward cycle
  int timeInOneCycle = (F+B)*T; //The time taken by robot to complete one forward and backward cycle
  int secondLastDistance = D-F; //The distance that the robot has to move before it can hit the obstacle
  int timeToSecondLastDistance = 0;
  int quotient = secondLastDistance/forward; //The number of forward and backward cycles needed to reach the secondLastDistance
  int remainder = secondLastDistance%forward;
  timeToSecondLastDistance = timeInOneCycle*quotient; //The time taken to reach the secondLastDistance
  int currentDistance = quotient*forward; //The distance covered by robot after completing quotient number of cycles
  int remainingTime = 0;
  int remainingDistance = D-currentDistance; //The distance remaining from the secondLastDistance point
  if(secondLastDistance <= 0) //If the total distance needed to be covered is less than or equal to the distance F covered by robot in forward direction
  {
   timeToSecondLastDistance = D*T;
  }
  else if(remainingDistance <= F) //If the remaining distance needed to be covered is less than or equal to the distance F covered by robot in forward direction
  {
   remainingTime = remainingDistance*T;
  }
  else //If the quotient calculated above is less than the number of cycles needed to reach the secondLastDistance point
  {
   currentDistance = currentDistance + forward;
   remainingTime = remainingTime + timeInOneCycle;
   remainingDistance = remainingDistance - forward;
   remainingTime = remainingTime + remainingDistance*T;
  }
  cout<<timeToSecondLastDistance + remainingTime<<endl;
 }
 return 0;
}