Missing Numbers Codechef Solution
Alice (uniformly and independently) randomly picks two integers a,b from the range [1,104], and writes down the values of a+b, a−b, a⋅b and ⌊ab⌋ (integer division) in some random order. Unfortunately, she forgot the values of a and b. You need to help her to find out if there exists two integers a,b such that 1≤a,b≤104 and a+b, a−b, a⋅b, ⌊ab⌋ are the numbers she has written down.
If a solution exists, it is guaranteed to be unique.
Input Format
- The first line of input contains a single integer T, denoting the number of testcases. The description of T testcases follows.
- Each testcase consists of a single line of input, containing four space-separated integers A,B,C,D — the values written down by Alice. It is guaranteed that at most one of the four numbers A,B,C,D will be negative.
Output Format
For each testcase, output in a single line, separated by a space, the two numbers Alice has chosen in order (i.e, if the solution is a=1 and b=2, print 1 2 and not 2 1). If there does not exist any such choice of integers, print −1 twice, separated by a space, instead.
Constraints
- 1≤T≤105
- −109≤A,B,C,D≤109
- At most one of A,B,C,D is negative.
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
2
-1 72 0 17
1 4 5 6
Sample Output 1
8 9
-1 -1
Explanation
- Test case 1: With a=8,b=9 we obtain 8+9=17,8−9=−1,8⋅9=72,⌊89⌋=0 which are exactly the 4 numbers written down by Alice.
- Test case 2: It can be shown that no choice of integers a,b can produce the given 4 numbers.
SOLUTION
Program: Missing Numbers Codechef Solution in Python
for _ in range(int(input())):
s1, s2, l1, l2 = sorted(list(map(int, input().split())))
pos_comb, l, found = set(), [s1, s2, l1, l2], False
for num1 in [l1, l2]:
for num2 in [s1, s2]:
if (num1+num2)%2==0:
a = (num1+num2)//2
b = (num1-num2)//2
if 0 < a <= 10000 and 0 < b <= 10000 and l == sorted([a+b, a-b, a*b, a//b]):
print(a, b)
found = True
break
if found:
break
if not found:
print(-1, -1)Program: Missing Numbers Codechef Solution in C++
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long int arr[4];
for(int i=0; i<4; i++)
{
cin>>arr[i];
}
sort(arr, arr+4);
long long int add, sub, mul, dvi;
if(arr[0]<0){
sub = arr[0];
dvi = arr[1];
if(arr[3]-arr[2]==1){
if(arr[2]==5 && arr[3]==6 && arr[0]==-1 && arr[1]==0)
{
mul = arr[3];
add = arr[2];
}
else
{
mul = arr[2];
add = arr[3];
}
}
else
{
mul = arr[3];
add = arr[2];
}
}
else if(arr[0]>0)
{
if(arr[3]-arr[2]==1)
{
if(arr[2]==5 && arr[3]==6 && arr[1]==1 && arr[0]==1)
{
mul = arr[3];
add = arr[2];
}
else
{
mul = arr[2];
add = arr[3];
}
sub = arr[0];
dvi = arr[1];
}
else
{
dvi = arr[0];
sub = arr[1];
add = arr[2];
mul = arr[3];
}
}
else if(arr[0]==0)
{
if(arr[3]-arr[2]==1 && arr[1]==1 && arr[2]==1)
{
add = arr[3];
mul = arr[2];
}
else
{
add = arr[2];
mul = arr[3];
}
sub = arr[0];
dvi = arr[1];
}
long long int n1, n2;
n1 = (add + sub)/2;
n2 = (add - sub)/2;
if(n1<=10000 && n2<=10000 && n1>0 && n2>0 && ((n1*n2) == mul) && ((n1/n2) == dvi))
{
cout<<n1<<" "<<n2<<endl;
}
else
{
cout<<"-1 -1"<<endl;
}
}
return 0;
}Program: Missing Numbers Codechef Solution in Java
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
InputReader in = new InputReader(inputStream);
int T = in.nextInt();
while (T-- > 0) {
int[] arr = new int[4];
for(int i=0;i<4;i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
boolean found = false;
for(int b=0;b<3;b++) {
if(found)
break;
for(int a=b+1;a<4;a++) {
if(found)
break;
for(int c=0;c<4;c++) {
if(found)
break;
if(c==a || c==b) {
continue;
}
for(int d=0;d<4;d++) {
if(found)
break;
if(d==a || d==b || d==c){
continue;
}
if(arr[c]<arr[d]) {
int temp = arr[c];
arr[c] = arr[d];
arr[d] = temp;
}
if(arr[c] == 0 || arr[d] < 0) {
break;
}
if((((long)arr[a]+arr[b]) * (long)(arr[a]-arr[b]))/arr[c] == 4) {
int aa = (int)(((long)arr[a] + (long)arr[b])/2);
int bb = arr[a] - aa;
if(aa>=1 && bb>=1 && aa<=10000 && bb<=10000 && (aa/bb == arr[d])){
found = true;
System.out.println(aa + " " + bb);
}
}
}
}
}
}
if(!found) {
System.out.println("-1 -1");
}
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}Related:
- Perfect Imperfections 2 Codechef Solution
- Kostomuksha and AESC MSU Codechef Solution
- Minimum Longest Substring Codechef Solution
- Same Parity Swaps in Binary Strings Codechef Solution
- Missing Numbers Codechef Solution
- The Rating Dilemma Codechef Solution
- Chef and Races Codechef Solution
- The Three Topics Codechef Solution
- Increase IQ Codechef Solution
