Problem: platform (2018 round1)

You're about to put on an exciting show at your local circus — a parkour
demonstration! **N** platforms with adjustable heights have been set up in a
row, and are numbered from 1 to **N** in order from left to right. The initial
height of platform _i_ is **Hi** metres.

When the show starts, **M** parkourists will take the stage. The _i_th
parkourist will start at platform **Ai**, with the goal of reaching a
different platform **Bi**. If **Bi** > **Ai**, they'll repeatedly jump to the
next platform to their right until they reach **Bi**. If **Bi** < **Ai**,
they'll instead repeatedly jump to the next platform to their left until they
reach **Bi**. All of the parkourists will complete their routes simultaneously
(but don't worry, they've been trained well to not impede one another).

Not all parkourists are equally talented, and there are limits on how far up
or down they can jump between successive platforms. The _i_th parkourist's
maximum upwards and downwards jump heights are **Ui** and **Di**,
respectively. This means that they're only able to move directly from platform
_x_ to some adjacent platform _y_ if **Hx** \- **Di** ≤ **Hy** ≤ **Hx** \+
**Ui**, where **Hx** and **Hy** are the current heights of platforms _x_ and
_y_, respectively.

With the show about to begin, a disastrous flaw has just occurred to you — it
may not be possible for all of the parkourists to actually complete their
routes with the existing arrangement of platforms! If so, you will need to
quickly adjust some of the platforms' heights first. The height of each
platform may be adjusted upwards or downwards at a rate of 1 metre per second,
to any non-negative real-valued height of your choice, and multiple platforms
may be adjusted simultaneously. As such, if the initial height of platform _i_
is **Hi** and its final height is **Pi**, then the total time required to make
your chosen height adjustments will be `max{`|**Hi** \- **Pi**|`}` over
_i_=1..**N**.

Determine the minimum amount of time required to set up the platforms such
that all **M** parkourists will then be able to complete their required
routes. Note that you may not perform further height adjustments once the show
starts. The platform heights must all remain constant while all **M**
parkourists complete their routes.

In order to reduce the size of the input data, you're given **H1** and **H2**.
**H3..N** may then be generated as follows using given constants **W**, **X**,
**Y**, and **Z** (please watch out for integer overflow during this process):

**Hi** = (**W** * **Hi-2** \+ **X** * **Hi-1** \+ **Y**) % **Z** (for _i_=3..**N**) 

### Input

Input begins with an integer **T**, the number of shows. For each show, there
is first a line containing the space-separated integers **N** and **M**. The
next line contains the space-separated integers **H1**, **H2**, **W**, **X**,
**Y**, and **Z**. Then, **M** lines follow. The _i_th of these lines contains
the space-separated integers **Ai**, **Bi**, **Ui**, and **Di**.

### Output

For the _i_th show, print a line containing "Case #_i_: " followed by 1 real
number, the minimum amount of time required to set up the platforms (in
seconds). Absolute and relative errors of up to 10-6 will be ignored.

### Constraints

1 ≤ **T** ≤ 85  
2 ≤ **N** ≤ 200,000  
1 ≤ **M** ≤ 20  
0 ≤ **Hi** < **Z**  
0 ≤ **W**, **X**, **Y** < **Z**  
1 ≤ **Z** ≤ 1,000,000  
1 ≤ **Ai**, **Bi** ≤ **N**  
0 ≤ **Ui**, **Di** ≤ 1,000,000  
**Ai**, ≠ **Bi**   

### Explanation of Sample

In the first case, **H** = [0, 10]. You can increase the first platform's
height by 3.5 and decrease the second's by 3.5 in 3.5 seconds, yielding **P**
= [3.5, 6.5]. The single parkourist will then be able to successfully complete
their route from platform 1 to platform 2 by jumping upwards by a height of at
most 3.

In the second case, **H** = [50, 59, 55, 51, 47]. One optimal possibility is
**P** = [54.0, 54.5, 53.5, 52.5, 51.5].

In the third case, **H** = [46, 38, 38, 22, 8].

In the fourth case, **H** = [53, 25, 24, 81, 77, 40, 29, 21].



Sample input:
5
2 1
0 10 0 0 0 11
1 2 3 8
5 1
50 59 0 1 96 100
1 5 2 1
5 2
46 38 2 4 44 50
4 1 3 2
3 5 4 1
8 5
53 25 15 23 54 100
1 8 14 9
3 1 5 7
6 8 2 1
5 4 1 8
8 1 11 10
100000 5
72464 815932 291056 735002 4758 972844
68327 29055 2880 3051
98105 26231 3531 3141
4018 31397 2797 3619
92594 65725 3824 3003
81932 8087 3372 3158


Sample output:
Case #1: 3.500000
Case #2: 4.500000
Case #3: 15.000000
Case #4: 24.000000
Case #5: 483009.500000



Code: // Platform Parkour
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 200000

int N;
int H[LIM],U[LIM],D[LIM];

bool Check(LD m)
{
	int i;
	LD a=H[0]-m;
	LD b=H[0]+m;
		Fox(i,N-1)
		{
			a=max(a-D[i],H[i+1]-m);
			b=min(b+U[i],H[i+1]+m);
				if (b<a)
					return(0);
		}
	return(1);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int M,W,X,Y,Z;
	int i,j,a,b,u,d;
	LD r1,r2,m;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
			Fill(U,60);
			Fill(D,60);
			// input
			Read(N),Read(M);
			Read(H[0]),Read(H[1]),Read(W),Read(X),Read(Y),Read(Z);
				FoxI(i,2,N-1)
					H[i]=((LL)W*H[i-2]+(LL)X*H[i-1]+Y)%Z;
				Fox(i,M)
				{
					Read(a),Read(b),Read(u),Read(d);
					a--,b--;
						if (a>b)
						{
							swap(a,b);
							swap(u,d);
						}
						FoxI(j,a,b-1)
						{
							Min(U[j],u);
							Min(D[j],d);
						}
				}
			// binary search
			r1=0,r2=1e6;
				while (r2>r1+EPS)
				{
					m=(r1+r2)/2;
						if (Check(m))
							r2=m;
						else
							r1=m;
				}
			// output
			printf("Case #%d: %.8lf\n",t,(double)r2);
		}
	return(0);
}