HW1

Problem 3-1: Gas Station -- Minimum Stops

There are two cities, A and B, on a straight road, and we want to drive from A to B. The distance between A and B is s; the capacity of the fuel tank is c; the car can run for distance d with a unit of fuel. There are N gas stations down the road, and the first gas station is in the city A. Now we start the trip with an empty fuel tank. Find the minimum number of stops we need to make at gas stations so that we can reach B from A.

Input

• First input the number of test cases.
• For each test case,
  • the first line contains 3 float numbers for s c d, and an integer for N.
  • then N-1 float numbers in one line, the i-th number is the distance from i+1-th station to city A.

Output

• For each test case,
  • output an integer representing the minimum stops make at gas stations (including the one at city A) if the car can reach city B.
  • output "fail" if the car cannot reach city B.
• There should be an empty line at the end of the output.

Sample Input

2
13 4 1 6
2 3 5 8 9
13 3 1 6
2 3 5 8 9

Sample Output

4
fail

Problem 3-2: Gas Station -- Minimum Cost

There are two cities, A and B, on a straight road, and we want to drive from A to B. The distance between A and B is s; the capacity of the fuel tank is c; the car can run for distance d with a unit of fuel. There are N gas stations down the road, and the first gas station is in the city A. Now we start the trip with an empty fuel tank. The gas price at i-th gas station is p_i for a unit of fuel. Find the gas-filling strategy to minimize the cost for gas to get to B from A.

Input

• First input the number of test cases.
• For each test case,
  • the first line contains 3 float numbers for s c d, and an integer for N.
  • then N-1 lines of input, each line contains 2 float numbers, the first one is the distance from the station to city A , and the second one is the gas price at the station.

Output

• For each test case,
  • output a float number representing the minimum cost if the car can reach city B.
  • output "fail" if the car cannot reach city B.
• There should be an empty line at the end of the output.

Sample Input

3
13 4 1 6
0 4
2 2
3 3
5 4
8 2
9 1
13 3 1 6
0 4
2 2
3 3
5 4
8 2
9 1

Sample Output

29
fail

Problem 4: Time-varying MST

One of the first things you learn in calculus is how to minimize a differentiable function such as $y = ax^2+bx+c$, where $a > 0$. The Minimum Spanning Tree Problem, on the other hand, is a minimization problem of a very different flavor: there are now just a finite number of possibilities for how the minimum might be achieved rather than a continuum of possibilities and we are interested in how to perform the computation without having to exhaust this (huge) finite number of possibilities.

One can ask what happens when these two minimization issues are brought together, and the following question is an example of this. Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a function $f_e : R \to R$. Thus, at time t, it has cost $f_e(t)$. Well assume that all these functions are positive over their entire range. Observe that the set of edges constituting the minimum spanning tree of G may change over time. Also, of course, the cost of the minimum spanning tree of G becomes a function of the time t; well denote this function $c_G(t)$. A natural problem then becomes: find a value of t at which $c_G(t)$ is minimized.

Suppose each function fe is a polynomial of degree 2: $f_e(t) = a_et^2 + 2b_et + c_e$, where $a_e > 0$. Give an algorithm that takes the graph G and the values $(a_e, b_e, c_e) : e \in E$ and returns a value of the time t at which the minimum spanning tree has minimum cost. Design an algorithm to find $t$ which minimizes the total weight of the MST of the graph.

Input

• First input the number of test cases.
• For each test case,
  • First line contain 2 numbers n, m, the number of nodes and edges.
  • Then m lines, each contain 2 integers and 3 floats, representing two vertices of an edge and its $a_e, b_e, c_e$.

Output

• For each test case, output 2 floats in one line, the $t$ minimizes total cost of the MST and the minimum total cost of the MST.

Sample Input

1
3 3
1 2 2 1 0
2 3 1 0 0
1 3 2 -2 0

Sample Output

0.333333 -0.333333

Problem 5: Zero-Skew

Timing circuits are a crucial component of VLSI chips. Here’s a simple model of such a timing circuit. Consider a complete balanced binary tree with n leaves, where n is a power of two. Each edge e of the tree has an associated length le, which is a positive number. The distance from the root to a given leaf is the sum of the lengths of all the edges on the path from the root to the leaf.

The root generates a clock signal which is propagated along the edges to the leaves. We’ll assume that the time it takes for the signal to reach a given leaf is proportional to the distance from the root to the leaf.

Now, if all leaves do not have the same distance from the root, then the signal will not reach the leaves at the same time, and this is a big problem. We want the leaves to be completely synchronized, and all to receive the signal at the same time. To make this happen, we will have to increase the lengths of certain edges, so that all root-to-leaf paths have the same length (we’re not able to shrink edge lengths). If we achieve this, then the tree (with its new edge lengths) will be said to have zero skew. Our goal is to achieve zero skew in a way that keeps the sum of all the edge lengths as small as possible. Give an algorithm that increases the lengths of certain edges so that the resulting tree has zero skew and the total edge length is as small as possible.

Input

• First input the number of test cases.
• For each test case,
  • First line contain an integer $n$ represent the number of leaves for the complete binary tree.
  • Then $\log_2 n$ lines, the i-th line contain $2^i$ integers representing the weight from corresponding parent node to its child node.

Output

• For each test case, output the total weight of the zero-skew tree.

Sample Input

2
4
2 1
2 1 2 1
8
4 6
2 1 3 4
2 3 7 1 2 2 3 3

Sample Output

12
56