PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Farhan Hasin
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given two integers A and B where 1 \leq A, B \leq 99, you are allowed to swap at most one pair of digit among A and B. What is the maximum value of A+B you can get?
QUICK EXPLANATION
- Since each number can consist of at most 2 digits, we can manually check all four possible swaps and print the maximum value.
EXPLANATION
Let’s assume A \geq B. We can consider four cases.
- When A, B < 10
In this case, swapping doesn’t change the answer at all. - When A < 10 \leq B
In this case, we can try swapping A with both digits of B and calculate A+B in each case and take maximum. - When A, B \geq 10
We can consider all four swaps (first digit of A with first digit of B, first digit of A with the second digit of B and so on) and take maximum.
Bonus: Can you solve it without explicitly doing swaps and then comparing?
Solution
Assume A1 be first digit of A, A2 be second digit of A. Similarly, B1 is first digit of B and B2 is second digit of B.
So A+B = (A1+B1)*10+(A2+B2). We try to swap larger one of A2 and B2 with smaller one of A1 and B1 if it increases A+B.
TIME COMPLEXITY
The time complexity is O(1) per test case.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
//freopen("testcases.txt","r",stdin);
int t;
cin>>t;
while(t--) {
int a,b;
cin>>a>>b;
int mx=a+b;
int a1=a%10;
int a2=a/10;
int b1=b%10;
int b2=b/10;
mx=max(mx,a2*10+b1+b2*10+a1);
if(b2) mx=max(mx,a2*10+b2+a1*10+b1);
if(a2) mx=max(mx,b1*10+a1+b2*10+a2);
if(a2 && b2) mx=max(mx,b2*10+a1+a2*10+b1);
cout<<mx<<endl;
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int a,b;
cin>>a>>b;
int sumi=a+b;
int ans=0;
if(a>=10){
ans=a/10+a%10+(b%10+b/10)*10;
sumi=max(sumi,ans);
}
swap(a,b);
if(a>=10){
ans=a/10+a%10+(b%10+b/10)*10;
sumi=max(sumi,ans);
}
cout<<sumi<<endl;
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class SWPDGT{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int a = ni(), b = ni();
int ans = a+b;
if(a< 10){
if(b< 10)ans = Math.max(ans, a+b);
else{
int b1 = b/10, b2 = b%10;
ans = Math.max(ans, b1+a*10+b2);
ans = Math.max(ans, b2+b1*10+a);//Prove this is useless
}
}else{
if(b < 10){
int a1 = a/10, a2 = a%10;
ans = Math.max(ans, a1+b*10+a2);
ans = Math.max(ans, a2+a1*10+b);//Prove this is useless
}else{
int a1 = a/10, a2 = a%10;
int b1 = b/10, b2 = b%10;
ans = Math.max(ans, a1*10+b2+ b1*10+a2);//Prove this is useless
ans = Math.max(ans, b1*10+a2+ a1*10+b2);//Prove this is useless
ans = Math.max(ans, a1*10+b1 + a2*10+b2);
ans = Math.max(ans, b2*10+a2+ b1*10+a1);
}
}
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new SWPDGT().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always.