[Hidden ☆ before use]
#### 1346. I. Floating-Point Unrounding

#### Description

Juliana would like to extrapolate, as accurately as possible, a geometric sequence with terms that have all been rounded to D significant digits.

A geometric sequence is an ordered sequence of real numbers of the form a_{0}, a_{1}, a_{2}, a_{3}, … a_{n-1}, where the terms (i.e., the numbers in the sequence) are related by powers of a constant factor r, specifically, a_{1} = a_{0}r, a_{2} = a_{0}r^{2}, a_{3} = a_{0}r^{3}, …, and a_{n-1} = a0r^{(n-1)}. Generally, for the i^{th} term, a_{i} = a_{0}r^{i}, so if you know accurate values for a_{0} and r, you can find any term. For example, if a_{0} is exactly 180 and r is exactly 1.95, the first 4 terms (that is, n = 4) of the geometric sequence are 180, 351, 684.45, and 1334.6775.

Rounding to significant digits is a different method of rounding than the traditional, fixeddecimal/ fixed-precision rounding that you might be used to. Significant digits are the digits of a number, in standard decimal notation, starting at the leftmost nonzero digit (the one in the largest place after all leading zeroes, even zeroes after the decimal point) and continuing to the right for

exactly the next D digits, for some specified value of D. At the D^{th} digit, standard rounding rules are applied to remove all remaining digits (if after the decimal point) or to convert them to zeroes (if before the decimal point).

This method, unlike traditional rounding, does not always result in the same fixed number of digits after the decimal point, and it may result in mandatory trailing zeroes, which indicates that D digits (including those trailing zeroes) are significant. The decimal point itself is only included when there are significant digits after it, and a leading zero is shown before the decimal point only when the first significant digit is after the decimal point.

Here are some examples of numbers rounded to significant digits, according to the rules above, with different values for D:

Those last 4 rounding examples are the terms of the preceding example for a geometric sequence. If you are given a geometric sequence only after the terms have been rounded in this way (such as 180.0, 351.0, 684.5, 1335), you have only an approximation for many or all values, since many original values could yield the same rounding result. And if you weren't given the value of r, it will be difficult to extrapolate the sequence accurately, since rounding errors would accumulate

rapidly. So you first need to find a way to reverse the effect of this kind of rounding—that is, to “unround” the numbers.

So how would you get from a D = 4 rounded value of 1335 back to exactly 1334.6775? It's not possible since any value from 1334.5 to 1335.4999... (inclusive), would round to 1335 using D = 4. But while you might not be able to find the exact original values with complete precision, you should be able to find, for some larger D value, the minimum and maximum valid values (the tightest possible upper and lower bounds) that would still satisfy the entire geometric sequence. If you can find the minimum and maximum valid values for a0 and r in this way, it will enable Juliana to extrapolate the sequence with confidence.

The Problem:

Given the consecutive terms of a geometric sequence, each rounded to the same D significant digits, find the minimum and maximum valid values for a0 (the first given term), each expressed with D+3 significant digits, and the minimum and maximum valid values for r, each expressed with D+5 significant digits.

#### Input

The input will consist of two lines. The
first line will contain only an integer D (0 < D < 6), and an
integer N (1 < N < 200), separated by a single space. The second
line will contain the consecutive terms, a_{i} (10^{-8} < a_{i }< 10^{8}),
in order for the geometric sequence—exactly N numbers with D
significant digits each. Each term will contain a decimal point, leading
zero, and/or trailing

zeroes only as required by the rules above. Each term will be separated from the next by a single space. The input numbers have been constructed such that the judges' solution requires no more than 13 significant digits in any intermediate calculation.

#### Output

Output a single line with four numbers in standard decimal notation, each separated by a single space, in this order: the minimum and maximum valid values for a0, rounded (or “unrounded” in this case) to D+3 significant digits, and the minimum and maximum valid values for r, similarly “unrounded” to D+5 significant digits. Follow the rules for significant digits, decimal points, leading zeroes, and trailing zeroes, exactly as given above.

#### Samples

#### Source

UCF2019

A geometric sequence is an ordered sequence of real numbers of the form a

Rounding to significant digits is a different method of rounding than the traditional, fixeddecimal/ fixed-precision rounding that you might be used to. Significant digits are the digits of a number, in standard decimal notation, starting at the leftmost nonzero digit (the one in the largest place after all leading zeroes, even zeroes after the decimal point) and continuing to the right for

exactly the next D digits, for some specified value of D. At the D

This method, unlike traditional rounding, does not always result in the same fixed number of digits after the decimal point, and it may result in mandatory trailing zeroes, which indicates that D digits (including those trailing zeroes) are significant. The decimal point itself is only included when there are significant digits after it, and a leading zero is shown before the decimal point only when the first significant digit is after the decimal point.

Here are some examples of numbers rounded to significant digits, according to the rules above, with different values for D:

Those last 4 rounding examples are the terms of the preceding example for a geometric sequence. If you are given a geometric sequence only after the terms have been rounded in this way (such as 180.0, 351.0, 684.5, 1335), you have only an approximation for many or all values, since many original values could yield the same rounding result. And if you weren't given the value of r, it will be difficult to extrapolate the sequence accurately, since rounding errors would accumulate

rapidly. So you first need to find a way to reverse the effect of this kind of rounding—that is, to “unround” the numbers.

So how would you get from a D = 4 rounded value of 1335 back to exactly 1334.6775? It's not possible since any value from 1334.5 to 1335.4999... (inclusive), would round to 1335 using D = 4. But while you might not be able to find the exact original values with complete precision, you should be able to find, for some larger D value, the minimum and maximum valid values (the tightest possible upper and lower bounds) that would still satisfy the entire geometric sequence. If you can find the minimum and maximum valid values for a0 and r in this way, it will enable Juliana to extrapolate the sequence with confidence.

The Problem:

Given the consecutive terms of a geometric sequence, each rounded to the same D significant digits, find the minimum and maximum valid values for a0 (the first given term), each expressed with D+3 significant digits, and the minimum and maximum valid values for r, each expressed with D+5 significant digits.

zeroes only as required by the rules above. Each term will be separated from the next by a single space. The input numbers have been constructed such that the judges' solution requires no more than 13 significant digits in any intermediate calculation.

Time Limit: | 1000MS (C/C++,Others×2) |

Memory Limit: | 128MB (C/C++,Others×2) |

Special Judge: | No |

AC/Submit: | 1 / 1 |

Tags: |