# Sum Product Segments | codechef solution

Problem

segment is a range of non-negative integers $�,�+1,�+2,\dots ,�$, denoted $\left[�,�\right]$ where $�\le �$.

Chef has a set $�$ consisting of all segments $\left[�,�\right]$ such that either $�+�=�$ or $�\cdot �=�$.

For example, if $�=5$ and $�=6$, then Chef's set is $�=\left\{\left[0,5\right],\left[1,4\right],\left[1,6\right],\left[2,3\right]\right\}$.

Given the integers $�$ and $�$, can you help Chef find two non-intersecting segments from his set $�$? 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,

• $\left[1,4\right]$ and $\left[10,42\right]$ are non-intersecting
• $\left[1,4\right]$ and $\left[3,10\right]$ are intersecting since they have $3$ and $4$ in common.
• $\left[1,4\right]$ and $\left[4,6\right]$ are intersecting since they have $4$ in common.

### Input Format

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

### Output Format

• If there are non-intersecting segments, then output two lines:
• In the first line, output two space-separated integers ${�}_{1},{�}_{1}$ denoting the first segment.
• In the second line, output two space-separated integers ${�}_{2},{�}_{2}$ denoting the second segment.
• If there are no such segments, print $-1$ on a single line.

### Constraints

• $1\le �\le 10$
• $1\le �,�\le 1{0}^{12}$

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

### Explanation:

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

Test case $2$: When $�=�=1$, we have $�=\left\{\left[0,1\right],\left[1,1\right]\right\}$

. The only two segments intersect with each other, so there is no answer.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
long long int x,y;
cin>>x>>y;
long long int l1,l2,r1,r2;
if(x%2==0){
l1=x/2;
r1=x/2;

}
else {
l1=x/2;
r1=(x/2)+1;

}
bool flag=false;
for(long long int b=1; b<=sqrt(y); b++){
if(y%b==0){
long long int a=y/b;
if(r1<b){
l2=b;
r2=a;
flag=true;
break;
}
if(l1>a){
l2=b;
r2=a;
flag=true;
break;
}
}
}
if(flag){
cout<<l1<<" "<<r1<<endl;
cout<<l2<<" "<<r2<<endl;
}else cout<<"-1"<<endl;
}
return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
long n,m,r;
while(t-->0)
{
n=Long.parseLong(s[0]);m=Long.parseLong(s[1]);r=1;
for(long i=(long)Math.sqrt(m);i>1;i--)
if(m%i==0)
{
r=i;
break;
}
if(2*(r-1)>=n)
{
if(r<=n)
System.out.println((n-r+1)+" "+(r-1)+"\n"+(r)+" "+(m/r));
else
System.out.println(0+" "+n+"\n"+(r)+" "+(m/r));
}
else if((m/r+1)*2<=n)
System.out.println((m/r+1)+" "+(n-m/r-1)+"\n"+(r)+" "+(m/r));
else
System.out.println(-1);
}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-