Internet Problem Solving Contest

IPSC 2018

Problem K – Kids draw the darndest things

Kelly is drawing pictures with circles. In order to draw a picture, she does the following:

  1. She draws a horizontal line segment of length 1 and she assigns the coordinates 0 and 1 to its left and right end, respectively.
  2. She draws two equally big circles that touch the line of the segment from above (one at each end of the segment) and touch each other above the middle of the segment. These two circles become her active circles.
  3. She draws a third circle that touches the line segment and both active circles.
  4. She chooses a sequence of n ≥ 0 directions, each being either “left” or “right”.
  5. Exactly n times she repeats the following:
    1. She looks at the next direction. Only one of the two active circles remains active: the one that touches the segment farther in that direction.
    2. The most recently drawn circle becomes active.
    3. She draws a new circle that touches the segment and both active circles.

For example, this is the picture she would draw for the sequence “left, right, left”. Circles were drawn in the order red, orange, green, blue. (The blue one is quite tiny, don’t miss it!)

As boys often do, Kevin forgot his compass at home. But he also likes pretty pictures, so he decided that he will do the same with squares (rotated 45 degrees, so that their diagonals are parallel to the coordinate axes). For example, for the sequence “left, right, left” Kevin would draw this:

Problem specification

The “circles-to-squares” function c is defined as the only continuous function on [0, 1] with the following property: For any sequence of directions, if Kelly drew her picture and the last circle touches the segment at xc, and Kevin drew his picture and the last square touches the segment at xs, then let c(xc)=xs.

You will be given a collection of inputs for c. Compute the corresponding outputs.

Input specification

The first line of the input file contains an integer t ≤ 100 specifying the number of test cases. Each test case is preceded by a blank line and consists of a single line.

Each test specifies the number xc for which you must compute c(xc). Decimal numbers are not exact, so the inputs are specified as roots of polynomials. Each test case has the form “p k”, where p is a polynomial with integer coefficients (see below) and k is a positive integer. Find the k-th smallest distinct real root of p and use that value as xc. It is guaranteed that it exists and lies in [0, 1].

In the easy subproblem K1 each p is linear. (Therefore, every xc is a rational number.)

In the hard subproblem K2 each p is either linear or quadratic.

Additionally, the input will be such that each line of correct output will have fewer than 40,000 characters.

Output specification

For each test case, output a single line. If the corresponding xs = c(xc) is an algebraic number (i.e., it can be expressed as a root of a polynomial with integer coefficients), output it using the same formatting as in the input. You must output the polynomial with the smallest possible positive degree. If the corresponding xs is transcendental, output the line “transcendental” instead.

Polynomial formatting for input and output

Examples of correctly formatted polynomials include “1*x^3+0*x^2+0*x-0” and “7*x^2-47*x+123456”. For more examples see the input files directly.




2*x-1 1

3*x-1 1


2*x-1 1
4*x-1 1