Header Ads Widget

Sum Product Segments | codechef solution

Rajnish Tripathi 21:20

Problem

A segment is a range of non-negative integers �,�+1,�+2,…,�, denoted [�,�] where �≤�.

Chef has a set � consisting of all segments [�,�] such that either �+�=� or �⋅�=�.

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

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,

  • [1,4] and [10,42] are non-intersecting
  • [1,4] and [3,10] are intersecting since they have 3 and 4 in common.
  • [1,4] and [4,6] 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≤�≤10
  • 1≤�,�≤1012

Sample 1:

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⋅6=24, so [1,3] and [4,6] are both valid segments. Clearly, they also don't intersect.

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

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

Code(C++):-

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

int main() {
    // your code goes here
    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
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(br.readLine());
        long n,m,r;
        while(t-->0)
        {
         String s[]=br.readLine().split(" ");
         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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


 

Tags:

Post a Comment

0 Comments