Data Structures, Spring 2013
IIIT Hyderabad
Programming Assignment 4
1. Online Median
Let us define :
F[1] = 1
F[i] = (a*M[i] + b*i + c)%1000000007 for i > 1
where M[i] is the median of the array {F[1],F[2],..,F[i-1]}.
The median of an array is the middle element of that array when it is sorted. If there are an
even number of elements in the array, we choose the first of the middle two elements to be
the median.
Given a,b,c and n, calculate the sum F[1] + F[2] + .. + F[n].
Input Format
The first line contains T the number of test cases. Each of the next T lines contain 4
integers : a,b,c and n.
Output Format
Output T lines, one for each test case, containing the required sum.
Sample Input
2
1003
3126
Sample Output
3
103
Constraints
1
0
1
2. Shortest Path.
Given are 2 vertices, S and T, in a weighted graph. Find the shortest path between S and T.
Input
First line contains 2 integers N and M. N is the number of vertices and M is the number of
edges.
The next M lines contain 3 integers each: U, V and W. This means that there is an edge
between vertex u and vertex v with weight w.
Then follows 1 more line of input containing two integers S and T.
Output
Print the shortest distance between S and T. Print -1 if there is no path between vertex S and
vertex T.
Constraints
1
0
1
U !=V
W>0
1