Qanat! {Time limit: 2 seconds}

Computer Science Level 5

A qanat is an irrigation system widely used to deliver water in hot, arid climates. The technology was originally developed by Persians over 2000 years ago. In Morocco, qanats are known as khettara and are still used today in the southern part of the country.

The basic feature of a qanat is an essentially horizontal channel that brings water from an underground water source to an outlet near a civilization. There is also a shaft known as a mother well that rises vertically from the underground water source to the surface of a mountain or hill. Creating such a system is extremely expensive, and was especially so in ancient times, since all of the materials excavated from the channel and mother well must be carried above ground, either through the channel outlet or the top of the mother well. To aid in the construction, there are often one or more additional vertical shafts placed at strategic locations above the underground channel. Although these shafts must also be excavated, they provide a means for lifting additional dirt from the horizontal channel as illustrated in Figure H.1.

For this problem, model the cross-section of a qanat as shown in Figure H.2, with the channel outlet at (0; 0), the water source at $(\omega; 0)$ , and the top of the mother well at $(\omega; h)$ with $\omega> h$ . The surface of the mountain extends along a straight line from $(\omega; h)$ to $(0;0)$ .

Every qanat must have a vertical mother well from the water source to the mountain surface above, along with n additional vertical shafts. The channel and all shafts are modeled as line segments. Your goal is to determine the placement for those additional shafts so as to minimize the overall excavation cost. This cost is equal to the sum of the distances that each piece of excavated dirt must be transported to reach the surface (using any combination of horizontal and vertical movement). For example, the cost of excavating a continuous section of dirt starting from the surface and going along a path of length ` (possibly including turns) is $∫_0^l xdx=l^2 /2$ .

Input The input consists of a single line containing three integers $\omega (1, \omega, 10 000), h (1, h < w)$ , and n (1 n 1 000). The value w is the horizontal distance from the water source to the qanat outlet. The value h is the vertical distance from the water source to the mountain surface. The value n is the number of vertical shafts that must be used in addition to the mother well.

Output First, display the minimum overall excavation cost. Next, display the x-coordinates, in increasing order, for n optimally placed vertical shafts. If n > 10, display only the first 10 x-coordinates. Answers within an absolute or relative error of 10􀀀4 will be accepted. You may assume that there is a unique solution. No test case will result in a shaft within 0:001 units from the outlet of the qanat channel or from another shaft.

What is $⌊(A-B+C-D+E)*10^4⌋$ ?

this problem is a last ICPC problem.

The answer is 492788.

1 solution

Jafar Badour
Oct 10, 2015

include "stdafx.h"

include<iostream>

include<cmath>

using namespace std; double jeff(double b, int i, int c, int w){//بتطالع امثال اول حد

if (i == 0){
    return 0;
}
if (i == 1){
    return 1;
}
else{
    return (-jeff(b, i - 2, c, w) + jeff(b, i - 1, c, w) / b);
}

}

int main(){

double w;
double h;
int n;
double allas[10];

cin >> w >> h >> n;
double b = (1 - pow(h / w, 2)) / 2;

double f = jeff(b, n + 1, n, w);
double x = w / f;
for (int i = 1; i < n + 1; i++){
    double d = jeff(b, i, n, w);
    allas[i] = d*x;

    if (i == 10)break;
}

double c = h / w;
double borabe = 0;

allas[0] = 0;
allas[n + 1] = w;
for (int i = n; i >0; i--){
    borabe = borabe + 0.25*pow(c*allas[i] + allas[i] + (c - 1)*allas[i - 1], 2) - pow(c*allas[i], 2) / 2;
}

borabe = borabe + 0.25*pow(c*allas[n + 1] + allas[n + 1] + (c - 1)*allas[n], 2);
cout << "cost is" << borabe << "\n";
for (int i = 1; i < n + 1; i++){
    double d = jeff(b, i, n, w);
    allas[i] = d*x;
    cout << i << " qanat " << d*x << "\n";
    if (i == 10)break;
}



return 0;

}

Let $m=\dfrac{h}{w}$ and $k=m^2-1$ . (We have $0<m<1$ and $-1<k<0$ .)

The cost for the segment between shafts at position $x_{i-1}$ and $x_{i}$ , plus the shaft at $x_i$ is: $cost(x_{i-1},x_i)= \dfrac{\big((m+1)·x_i+(m-1)·x_{i-1}\big)^2}4-\dfrac{(m·x_{i-1})^2}2$

The partial derivative of the total cost in respect to the shaft at position $x_i$ is: $\dfrac{\partial cost}{\partial x_i}=k·x_{i-1}+2·x_i+k·x_{i+1}$ With $x_0=0$ and $x_{n+1}=w$ .

Python code, which solves equation system of partial derivatives = 0: $\begin{pmatrix}2 & k & 0 & 0 & 0\\ k & 2 & k & 0 & 0\\ 0 & k & 2 & k & 0\\ 0 & 0 & k & 2 & k\\ 0 & 0 & 0 & k & 2 \end{pmatrix}\cdot\begin{pmatrix}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5} \end{pmatrix}=\begin{pmatrix}0\\ 0\\ 0\\ 0\\ -k\cdot w \end{pmatrix}$

import sys                                                                                                                                                                                                                               
from numpy.linalg import inv

(w,h,n)=map(int, sys.argv[1:])

m = h / w
k = m**2 - 1

matrix =  [  ]
for i in range(n):
    matrix += [n*[0]]
    if i > 0:
        matrix[-1][i-1] = k
    matrix[-1][i] = 2
    if i + 1 < n:
        matrix[-1][i+1] = k

matinv = inv(matrix)
wells  =  [0]  +  [ -row[-1] * k * w  for row in matinv ]  +  [w]    
cost = sum([ ((m+1)*wells[i+1]+(m-1)*wells[i])**2/2-(m*wells[i])**2 for i in range(len(wells)-1)])/2

print(cost)
print("\n".join(map(str, wells[1:-1])))

if n == 5:
    print(int(10000*(wells[1] - wells[2] + wells[3] - wells[4] + wells[5])))

Outputs:

$ python well.py 8 4 1  
31.5
3.0

$ python well.py 195 65 2
12220.0
48.0
108.0

$ python well.py 100 7 5
825.4750892845979
15.747647618639588
31.65038210961629
47.86481768055908
64.55063825127021
81.8721700619195
492836

The exact answer I find is $\dfrac{50729003382450}{102932797}\simeq 492836.15$ . Therefore, it can't be a rounding error on my side that gives another result than 492788. I don't know if I missed something or not.

Laurent Shorts - 2 years, 1 month ago