Problem: interception (2018 quals)

Consider an N-degree polynomial, expressed as follows:

**P**N * xN \+ **P**N-1 * xN-1 \+ ... + **P**1 * x1 \+ **P**0 * x0

You'd like to find all of the polynomial's x-intercepts — in other words, all
distinct real values of x for which the expression evaluates to 0.

Unfortunately, the order of operations has been reversed: Addition (**+**) now
has the highest precedence, followed by multiplication (*****), followed by
exponentiation (**^**). In other words, an expression like ab \+ c * d should
be evaluated as a((b+c)*d). For our purposes, exponentiation is right-
associative (in other words, abc = a(bc)), and 00 = 1. The unary negation
operator still has the highest precedence, so the expression -2-3 * -1 + -2
evaluates to -2(-3 * (-1 + -2)) = -29 = -512.

### Input

Input begins with an integer **T**, the number of polynomials. For each
polynomial, there is first a line containing the integer **N**, the degree of
the polynomial. Then, **N**+1 lines follow. The _i_th of these lines contains
the integer **Pi-1**.

### Output

For the _i_th polynomial, print a line containing "Case #_i_: **K**", where
**K** is the number of distinct real values of **x** for which the polynomial
evaluates to 0. Then print **K** lines, each containing such a value of **x**,
in increasing order.

Absolute and relative errors of up to 10-6 will be ignored in the x-intercepts
you output. However, **K** must be exactly correct.

### Constraints

1 ≤ **T** ≤ 200  
0 ≤ **N** ≤ 50  
-50 ≤ **Pi** ≤ 50   
**PN** ≠ 0   

### Explanation of Sample

In the first case, the polynomial is 1 * x1 \+ 1 * x0. With the order of
operations reversed, this is evaluated as (1 * x)(((1 + 1) * x)0), which is
equal to 0 only when x = 0.

In the second case, the polynomial does not evaluate to 0 for any real value
x.



Sample input:
2
1
1
1
4
9
0
-6
2
-2


Sample output:
Case #1: 1
0.0
Case #2: 0



Code: // Interception
// 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-12;
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);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N;
	int i,p;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
				Fox(i,N+1)
					Read(p);
			// output
			printf("Case #%d: ",t);
				if (N%2==0)
					printf("0\n");
				else
					printf("1\n0\n");
		}
	return(0);
}