1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Ela's Fitness and the Luxury Number
Contest: Dytechlab Cup 2022
Difficulty rating: 1300
Tags: binary search, implementation, math

While working at DTL, Ela is very aware of her physical and mental health. She started to practice various sports, such as Archery, Yoga, and Football.

Since she started engaging in sports activities, Ela switches to trying a new sport on days she considers being "Luxury" days. She counts the days since she started these activities, in which the day she starts is numbered as day $$$1$$$. A "Luxury" day is the day in which the number of this day is a luxurious number.

An integer $$$x$$$ is called a luxurious number if it is divisible by $$${\lfloor \sqrt{x} \rfloor}$$$.

Here $$$\lfloor r \rfloor$$$ denotes the "floor" of a real number $$$r$$$. In other words, it's the largest integer not greater than $$$r$$$.

For example: $$$8$$$, $$$56$$$, $$$100$$$ are luxurious numbers, since $$$8$$$ is divisible by $$$\lfloor \sqrt{8} \rfloor = \lfloor 2.8284 \rfloor = 2$$$, $$$56$$$ is divisible $$$\lfloor \sqrt{56} \rfloor = \lfloor 7.4833 \rfloor = 7$$$, and $$$100$$$ is divisible by $$$\lfloor \sqrt{100} \rfloor = \lfloor 10 \rfloor = 10$$$, respectively. On the other hand $$$5$$$, $$$40$$$ are not, since $$$5$$$ are not divisible by $$$\lfloor \sqrt{5} \rfloor = \lfloor 2.2361 \rfloor = 2$$$, and $$$40$$$ are not divisible by $$$\lfloor \sqrt{40} \rfloor = \lfloor 6.3246 \rfloor = 6$$$.

Being a friend of Ela, you want to engage in these fitness activities with her to keep her and yourself accompanied (and have fun together, of course). Between day $$$l$$$ and day $$$r$$$, you want to know how many times she changes the activities.

Input format:
Each test contains multiple test cases. The first line has the number of test cases $$$t$$$ ($$$1 \le t \le 10\ 000$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) — the intervals at which you want to know how many times Ela changes her sports.

Output format:
For each test case, output an integer that denotes the answer.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$5$$$ luxury numbers in range $$$[8, 19]$$$ are: $$$8, 9, 12, 15, 16$$$.

Example input:
5
8 19
8 20
119 121
1 100000000000000000
1234567891011 1000000000000000000

Example output:
5
6
2
948683296
2996666667

Editorial:
We shift the perspective to see the pattern from $$$\lfloor \sqrt{x} \rfloor$$$, instead of $$$x$$$, to see what kind of patterns are needed so $$$x$$$ can be luxurious.
Note that: $$${(a + 1)}^2 - 1 = a * (a + 2)$$$.
Therefore, every half-closed segment $$$[a^2, (a + 1) ^ 2)$$$ contains exactly $$$3$$$ luxurious number: $$$a^2$$$, $$$a * (a + 1)$$$ and $$$a * (a + 2)$$$.
Also note that, since large numbers can cause inaccuracies in floating point computation, we should use binary search to find the floor-value of a square root, instead of using the sqrt function in any language.
Ela and Prime GCD
Contest: Dytechlab Cup 2022
Difficulty rating: 3300
Tags: constructive algorithms, math, number theory

After a long, tough, but fruitful day at DTL, Ela goes home happily. She entertains herself by solving Competitive Programming problems. She prefers short statements, because she already read too many long papers and documentation at work. The problem of the day reads:

You are given an integer $$$c$$$. Suppose that $$$c$$$ has $$$n$$$ divisors. You have to find a sequence with $$$n - 1$$$ integers $$$[a_1, a_2, ... a_{n - 1}]$$$, which satisfies the following conditions:

- Each element is strictly greater than $$$1$$$.
- Each element is a divisor of $$$c$$$.
- All elements are distinct.
- For all $$$1 \le i < n - 1$$$, $$$\gcd(a_i, a_{i + 1})$$$ is a prime number.

In this problem, because $$$c$$$ can be too big, the result of prime factorization of $$$c$$$ is given instead. Note that $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$ and a prime number is a positive integer which has exactly $$$2$$$ divisors.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) - the number of test cases.

The first line of each test case contains one integer $$$m$$$ ($$$1 \le m \le 16$$$) - the number of prime factor of $$$c$$$.

The second line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i < 2^{20}$$$) — exponents of corresponding prime factors of $$$c$$$, so that $$$c = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_m^{b_m}$$$ and $$$n = (b_1 + 1)(b_2 + 1) \ldots (b_m + 1)$$$ hold. $$$p_i$$$ is the $$$i$$$-th smallest prime number.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2^{20}$$$.

Output format:
Print the answer for each test case, one per line. If there is no sequence for the given $$$c$$$, print $$$-1$$$.

Otherwise, print $$$n - 1$$$ lines. In $$$i$$$-th line, print $$$m$$$ space-separated integers. The $$$j$$$-th integer of $$$i$$$-th line is equal to the exponent of $$$j$$$-th prime number from $$$a_i$$$.

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In each test case, the values of $$$c$$$ are $$$6$$$, $$$2$$$, $$$30$$$, $$$16$$$, and $$$12$$$ in that order.

In the first test case, $$$1$$$, $$$2$$$, $$$3$$$, $$$6$$$ are divisors of $$$6$$$. Here, sequences $$$[2, 6, 3]$$$ and $$$[3, 6, 2]$$$ can be answer. Permutation $$$[3, 2, 6]$$$ is invalid because $$$\gcd(a_1, a_2) = 1$$$ is not a prime number.

In the forth test case, $$$1$$$, $$$2$$$, $$$4$$$, $$$8$$$, $$$16$$$ are divisors of $$$16$$$. Among the permutation of sequence $$$[2, 4, 8, 16]$$$, no valid answer exist.

Example input:
5
2
1 1
1
1
3
1 1 1
1
4
2
2 1

Example output:
0 1 
1 1 
1 0 
1 
0 1 1 
0 0 1 
1 0 1 
1 1 0 
0 1 0 
1 1 1 
1 0 0 
-1
2 0 
1 1 
0 1 
2 1 
1 0

Editorial:
Mysterious numbers - 1
Contest: April Fools Day Contest
Difficulty rating: 1200
Tags: *special, constructive algorithms

Input format:
The input contains two integers a1, a2 (0 ≤ ai ≤ 109), separated by a single space.

Output format:
Output a single integer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 14

Example output:
44

Example input:
27 12

Example output:
48

Editorial:
Star
Contest: April Fools Day Contest
Difficulty rating: 1300
Tags: *special, combinatorics

Input format:
The input contains a single integer a (1 ≤ a ≤ 18257).

Output format:
Print a single integer output (1 ≤ output ≤ 2·109).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2

Example output:
13

Editorial:
A Piece of Cake
Contest: April Fools Day Contest
Difficulty rating: 2000
Tags: *special, implementation

How to make a cake you'll never eat.

Ingredients.

- 2 carrots
- 0 calories
- 100 g chocolate spread
- 1 pack of flour
- 1 egg

Method.

1. Put calories into the mixing bowl.
2. Take carrots from refrigerator.
3. Chop carrots.
4. Take chocolate spread from refrigerator.
5. Put chocolate spread into the mixing bowl.
6. Combine pack of flour into the mixing bowl.
7. Fold chocolate spread into the mixing bowl.
8. Add chocolate spread into the mixing bowl.
9. Put pack of flour into the mixing bowl.
10. Add egg into the mixing bowl.
11. Fold pack of flour into the mixing bowl.
12. Chop carrots until choped.
13. Pour contents of the mixing bowl into the baking dish.

Serves 1.

Input format:
The only line of input contains a sequence of integers a0, a1, ... (1 ≤ a0 ≤ 100, 0 ≤ ai ≤ 1000 for i ≥ 1).

Output format:
Output a single integer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4 1 2 3 4

Example output:
30

Editorial:
Broken checker
Contest: April Fools Day Contest
Difficulty rating: 1300
Tags: *special, brute force

"This problem is rubbish! There is not statement, and there are only 5 test cases. The problemsetter took liberties with this problem!" — people complained in the comments to one round on Codeforces. And even more... No, wait, the checker for the problem was alright, that's a mercy.

Input format:
The only line of the input contains an integer between 1 and 5, inclusive. All tests for this problem are different. The contents of the test case doesn't need to be equal to its index.

Output format:
The only line of the output contains an integer between 1 and 3, inclusive.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
This problem has no samples, since there so few test cases.

Editorial:
MYSTERIOUS LANGUAGE
Contest: April Fools Day Contest
Difficulty rating: 2000
Tags: *special

You are given a mysterious language (codenamed "Secret") available in "Custom Test" tab. Find out what this language is and write a program which outputs its name. Note that the program must be written in this language.

Input format:
This program has only one test, and it's empty (it doesn't give your program anything to read).

Output format:
Output the name of the mysterious language.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Editorial:
ucyhf
Contest: April Fools Day Contest
Difficulty rating: 1600
Tags: *special, brute force, implementation, number theory

qd ucyhf yi q fhycu dkcruh mxeiu huluhiu yi q tyvvuhudj fhycu dkcruh. oekh jqia yi je vydt jxu djx ucyhf.

Input format:
jxu ydfkj sediyiji ev q iydwbu ydjuwuh d (1 ≤ d ≤ 11184) — jxu edu-rqiut ydtun ev jxu ucyhf je vydt.

Output format:
ekjfkj q iydwbu dkcruh.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
1

Example output:
13

Editorial:
Mysterious numbers - 2
Contest: April Fools Day Contest
Difficulty rating: 1600
Tags: *special

Input format:
The only line of input contains three integers a1, a2, a3 (1 ≤ a1, a2, a3 ≤ 20), separated by spaces.

Output format:
Output a single integer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 3 2

Example output:
5

Example input:
13 14 1

Example output:
14

Editorial:
A polyline
Contest: April Fools Day Contest
Difficulty rating: 1700
Tags: *special, implementation

Input format:
The input contains two integers a, b (1 ≤ a ≤ 10, 0 ≤ b ≤ 22·a - 1) separated by a single space.

Output format:
Output two integers separated by a single space.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
1 0

Example output:
0 0

Example input:
2 15

Example output:
3 0

Editorial:
Polycarp and Sums of Subsequences
Contest: Codeforces Round 760 (Div. 3)
Difficulty rating: 800
Tags: math, sortings

Polycarp had an array $$$a$$$ of $$$3$$$ positive integers. He wrote out the sums of all non-empty subsequences of this array, sorted them in non-decreasing order, and got an array $$$b$$$ of $$$7$$$ integers.

For example, if $$$a = \{1, 4, 3\}$$$, then Polycarp wrote out $$$1$$$, $$$4$$$, $$$3$$$, $$$1 + 4 = 5$$$, $$$1 + 3 = 4$$$, $$$4 + 3 = 7$$$, $$$1 + 4 + 3 = 8$$$. After sorting, he got an array $$$b = \{1, 3, 4, 4, 5, 7, 8\}.$$$

Unfortunately, Polycarp lost the array $$$a$$$. He only has the array $$$b$$$ left. Help him to restore the array $$$a$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

Each test case consists of one line which contains $$$7$$$ integers $$$b_1, b_2, \dots, b_7$$$ ($$$1 \le b_i \le 10^9$$$; $$$b_i \le b_{i+1}$$$).

Additional constraint on the input: there exists at least one array $$$a$$$ which yields this array $$$b$$$ as described in the statement.

Output format:
For each test case, print $$$3$$$ integers — $$$a_1$$$, $$$a_2$$$ and $$$a_3$$$. If there can be several answers, print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The subsequence of the array $$$a$$$ is a sequence that can be obtained from $$$a$$$ by removing zero or more of its elements.

Two subsequences are considered different if index sets of elements included in them are different. That is, the values of the elements don't matter in the comparison of subsequences. In particular, any array of length $$$3$$$ has exactly $$$7$$$ different non-empty subsequences.

Example input:
5
1 3 4 4 5 7 8
1 2 3 4 5 6 7
300000000 300000000 300000000 600000000 600000000 600000000 900000000
1 1 2 999999998 999999999 999999999 1000000000
1 2 2 3 3 4 5

Example output:
1 4 3
4 1 2
300000000 300000000 300000000
999999998 1 1
1 2 2

Editorial:
The order of elements in $$$a$$$ doesn't matter. If there is at least one correct array $$$a$$$, then we can sort it and get the answer in which $$$a_1 \le a_2 \le a_3$$$. Therefore, we can always find a sorted array. Suppose that $$$a_1 \le a_2 \le a_3$$$. Then $$$b_1 = a_1$$$, $$$b_2 = a_2$$$, $$$b_7 = a_1 + a_2 + a_3$$$. We can find $$$a_3$$$ as $$$b_7 - a_1 - a_2$$$.
Paint the Array
Contest: Codeforces Round 760 (Div. 3)
Difficulty rating: 1100
Tags: math

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. You have to choose a positive integer $$$d$$$ and paint all elements into two colors. All elements which are divisible by $$$d$$$ will be painted red, and all other elements will be painted blue.

The coloring is called beautiful if there are no pairs of adjacent elements with the same color in the array. Your task is to find any value of $$$d$$$ which yields a beautiful coloring, or report that it is impossible.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

The first line of each testcase contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of elements of the array.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$).

Output format:
For each testcase print a single integer. If there is no such value of $$$d$$$ that yields a beautiful coloring, print $$$0$$$. Otherwise, print any suitable value of $$$d$$$ ($$$1 \le d \le 10^{18}$$$).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5
5
1 2 3 4 5
3
10 5 15
3
100 10 200
10
9 8 2 6 6 2 8 6 5 4
2
1 3

Example output:
2
0
100
0
3

Editorial:
What does it mean that no pair of adjacent elements should have the same color? It means that either all elements on odd positions are blue and all elements on even positions are red, or vice versa. So, we need to check these two cases.
Let's try to solve a case when we have to find a number $$$d$$$ such that $$$a_1, a_3, \dots$$$ are divisible by $$$d$$$, and $$$a_2, a_4, \dots$$$ are not. What does it mean that $$$d$$$ divides all of the numbers $$$a_1, a_3, \dots$$$? It means that $$$d$$$ divides the $$$gcd(a_1, a_3, \dots)$$$, where $$$gcd$$$ represents the greatest common divisor. Let's calculate this $$$gcd$$$ using Euclidean algorithm or some built-in functions in $$$O(n + \log A)$$$.
Okay, now we need to check all divisors of the $$$gcd(a_1, a_3, \dots)$$$ and find if any of them does not divide $$$a_2, a_4, \dots$$$. So, we have to factorize $$$gcd$$$ and generate all of its divisors... or do we? In fact, if $$$gcd(a_1, a_3, \dots)$$$ divides any of the numbers $$$a_2, a_4, \dots$$$, then every divisor of $$$gcd$$$ also divides that number. So, the only two numbers we have to check as canditates for the answer are $$$gcd(a_1, a_3, \dots)$$$ and $$$gcd(a_2, a_4, \dots)$$$.
Yaroslav and Permutations
Contest: Codeforces Round 179 (Div. 2)
Difficulty rating: 1100
Tags: greedy, math

Yaroslav has an array that consists of n integers. In one second Yaroslav can swap two neighboring array elements. Now Yaroslav is wondering if he can obtain an array where any two neighboring elements would be distinct in a finite time.

Help Yaroslav.

Input format:
The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the array. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000) — the array elements.

Output format:
In the single line print "YES" (without the quotes) if Yaroslav can obtain the array he needs, and "NO" (without the quotes) otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample the initial array fits well.

In the second sample Yaroslav can get array: 1, 2, 1. He can swap the last and the second last elements to obtain it.

In the third sample Yarosav can't get the array he needs.

Example input:
1
1

Example output:
YES

Example input:
3
1 1 2

Example output:
YES

Editorial:
Yaroslav and Two Strings
Contest: Codeforces Round 179 (Div. 2)
Difficulty rating: 2000
Tags: combinatorics, dp

Yaroslav thinks that two strings s and w, consisting of digits and having length n are non-comparable if there are two numbers, i and j (1 ≤ i, j ≤ n), such that si > wi and sj < wj. Here sign si represents the i-th digit of string s, similarly, wj represents the j-th digit of string w.

A string's template is a string that consists of digits and question marks ("?").

Yaroslav has two string templates, each of them has length n. Yaroslav wants to count the number of ways to replace all question marks by some integers in both templates, so as to make the resulting strings incomparable. Note that the obtained strings can contain leading zeroes and that distinct question marks can be replaced by distinct or the same integers.

Help Yaroslav, calculate the remainder after dividing the described number of ways by 1000000007 (109 + 7).

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the length of both templates. The second line contains the first template — a string that consists of digits and characters "?". The string's length equals n. The third line contains the second template in the same format.

Output format:
In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first test contains no question marks and both strings are incomparable, so the answer is 1.

The second test has no question marks, but the given strings are comparable, so the answer is 0.

Example input:
2
90
09

Example output:
1

Example input:
2
11
55

Example output:
0

Editorial:
Uniform String
Contest: Codeforces Round 527 (Div. 3)
Difficulty rating: 800
Tags: implementation

You are given two integers $$$n$$$ and $$$k$$$.

Your task is to construct such a string $$$s$$$ of length $$$n$$$ that for each $$$i$$$ from $$$1$$$ to $$$k$$$ there is at least one $$$i$$$-th letter of the Latin alphabet in this string (the first letter is 'a', the second is 'b' and so on) and there are no other letters except these. You have to maximize the minimal frequency of some letter (the frequency of a letter is the number of occurrences of this letter in a string). If there are several possible answers, you can print any.

You have to answer $$$t$$$ independent queries.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of queries.

The next $$$t$$$ lines are contain queries, one per line. The $$$i$$$-th line contains two integers $$$n_i$$$ and $$$k_i$$$ ($$$1 \le n_i \le 100, 1 \le k_i \le min(n_i, 26)$$$) — the length of the string in the $$$i$$$-th query and the number of characters in the $$$i$$$-th query.

Output format:
Print $$$t$$$ lines. In the $$$i$$$-th line print the answer to the $$$i$$$-th query: any string $$$s_i$$$ satisfying the conditions in the problem statement with constraints from the $$$i$$$-th query.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example query the maximum possible minimal frequency is $$$2$$$, it can be easily seen that the better answer doesn't exist. Other examples of correct answers: "cbcabba", "ccbbaaa" (any permutation of given answers is also correct).

In the second example query any permutation of first four letters is acceptable (the maximum minimal frequency is $$$1$$$).

In the third example query any permutation of the given answer is acceptable (the maximum minimal frequency is $$$3$$$).

Example input:
3
7 3
4 4
6 2

Example output:
cbcacab
abcd
baabab

Editorial:
The only thing you need to do is to place letters by blocks $$$1, 2, \dots, k$$$, $$$1, 2, \dots, k$$$ and so on. The last block can contain less than $$$k$$$ letters but it is ok. It is easy to see that this letters distribution is always not worse than others.
Teams Forming
Contest: Codeforces Round 527 (Div. 3)
Difficulty rating: 800
Tags: sortings

There are $$$n$$$ students in a university. The number of students is even. The $$$i$$$-th student has programming skill equal to $$$a_i$$$.

The coach wants to form $$$\frac{n}{2}$$$ teams. Each team should consist of exactly two students, and each student should belong to exactly one team. Two students can form a team only if their skills are equal (otherwise they cannot understand each other and cannot form a team).

Students can solve problems to increase their skill. One solved problem increases the skill by one.

The coach wants to know the minimum total number of problems students should solve to form exactly $$$\frac{n}{2}$$$ teams (i.e. each pair of students should form a team). Your task is to find this number.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of students. It is guaranteed that $$$n$$$ is even.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the skill of the $$$i$$$-th student.

Output format:
Print one number — the minimum total number of problems students should solve to form exactly $$$\frac{n}{2}$$$ teams.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example the optimal teams will be: $$$(3, 4)$$$, $$$(1, 6)$$$ and $$$(2, 5)$$$, where numbers in brackets are indices of students. Then, to form the first team the third student should solve $$$1$$$ problem, to form the second team nobody needs to solve problems and to form the third team the second student should solve $$$4$$$ problems so the answer is $$$1 + 4 = 5$$$.

In the second example the first student should solve $$$99$$$ problems to form a team with the second one.

Example input:
6
5 10 2 3 14 5

Example output:
5

Example input:
2
1 100

Example output:
99

Editorial:
If we sort the students in order of non-decreasing their skill, we can see that the minimum cost of the team with the lowest skill (let's call it the first team) is equal to $$$a_2 - a_1$$$ (if $$$a$$$ is already sorted), the cost of the second team is $$$a_4 - a_3$$$ and so on.
So if we sort $$$a$$$ in non-decreasing order then the answer is $$$\sum\limits_{i = 1}^{\frac{n}{2}} a_{2i} - a_{2i - 1}$$$.
A Problem about Polyline
Contest: Codeforces Round 320 (Div. 1) [Bayan Thanks-Round]
Difficulty rating: 1700
Tags: geometry, math

There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – ....

We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such x.

Input format:
Only one line containing two positive integers a and b (1 ≤ a, b ≤ 109).

Output format:
Output the only line containing the answer. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 9. If there is no such x then output  - 1 as the answer.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
You can see following graphs for sample 1 and sample 3.

Example input:
3 1

Example output:
1.000000000000

Example input:
1 3

Example output:
-1

Editorial: