[Solution] Sum Product Segments solution codechef

Sum Product Segments solution codechef – A segment is a range of non-negative integers L, L + 1, L + 2, \ldots, R, denoted [L, R] where L \leq R.

Table of Contents

[Solution] Sum Product Segments solution codechef

Chef has a set S consisting of all segments [L, R] such that either L + R = X or L\cdot R = Y.

For example, if X = 5 and Y = 6, then Chef’s set is S = \{[0, 5], [1, 4], [1, 6], [2, 3]\}.

Given the integers X and Y, can you help Chef find two non-intersecting segments from his set S? If it is not possible to find two such non-intersecting segments, print -1. If there are multiple possible answers, you may output any of them.

Note: Two segments are said to be non-intersecting if they have no number in common. For example, [1, 4] and [10, 42] are non-intersecting, while [1, 4] and [4, 6] are not since they have 4 in common.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of a single line containing two space separated integers X and Y.

Sum Product Segments solution codechef

  • If there are non-intersecting segments, then output two lines:
    • In the first line, output two space-separated integers L_1, R_1 denoting the first segment.
    • In the second line, output two space-separated integers L_2, R_2 denoting the second segment.
  • If there are no such segments, print -1 on a single line.

Constraints

  • 1 \leq T \leq 10
  • 1 \leq X, Y \leq 10^{12}

Sample 1:

Input

Output

3
4 24
1 1
3 30
1 3
4 6
-1
5 6
0 3

Sum Product Segments solution codechef Explanation

Test case 1: 1+3 = 4 and 4 \cdot 6 = 24, so [1, 3] and [4, 6] are both valid segments. Clearly, they also don’t intersect.

Test case 2: When X = Y = 1, we have S = \{[0, 1], [1, 1]\}. The only two segments intersect with each other, so there is no answer.

For Solution

Click Here

Leave a Comment