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 11digit precision
Sample Input and Output
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$$
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 11digit 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$$
No comments:
Post a Comment