PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Divyam Singal
Editorialist: Taranpreet Singh
DIFFICULTY
Medium-Hard
PREREQUISITES
Triangle Inequality, Congruences, Creativity, and Case-based analysis.
PROBLEM
You have to find triplet of positive integers (A, B, C) such that
- S(A+B) = X
- S(B+C) = Y
-
S(A+C) = Z
where X, Y and Z are given.
We want to find triplet minimizing $S(A+B+C), and the triplet maximizing S(A+B+C).
S(N) denotes the sum of digits of N.
QUICK EXPLANATION
- If P = A+B. Q = B+C and R = C+A, P, Q and R must satisfy triangle inequality, since A, B and C are positive integers.
- For maximum case, the sum 2*(A+B+C) shall look like 211\ldots10, initial 2 appears only to satisfy the triangle inequality. The maximum sum of digits generated is 5*(X+Y+Z-2) +1
- For minimum case, ignoring triangle inequality, we try to make 2*(A+B+C) = 2000\ldots0 to obtain S(A+B+C) = 1, which can happen only if (X+Y+Z) \bmod 9 = 2. So for (X+Y+Z) \bmod 9 = r, we can leave the remaining r to obtain S(A+B+C) = 1+r/2 \pmod 9
- Due to triangle inequality, the case (X+Y+Z) = 2 \pmod 9 is affected, since we do not have any extra 1 for carrying forward. In this case, if we have min(X+Y, Y+Z, Z+X) \geq 11, we can choose the first digit of P, Q, and R so that there’s a carry off of 2 to the first digit in A+B+C. Otherwise we’d get digit sum of S(A+B+C) = 10
EXPLANATION
Let’s assume P = A+B, Q = B+C, R = C+A. Now, P+Q+R = 2*(A+B+C). Now, since A, B and C are positive integers P, Q and R must satisfy triangle inequality.
Proof
WLOG assume P < Q < R. Assuming R > P+Q \implies A+C > A+B+B+C \implies 0 > 2*B, but B is a positive integer, so we get contradiction.
How Sum of digit works with addition
Let’s see how addition works. When a sum of digits at a place exceeds 9, it is carried forward to the next significant place. See how it impacts the digit sum.
Adding 52 and 35 gives 87. Here, since there was no carry forward, S(85) = S(52)+S(35) holds. But adding 42 and 48 gives 90. S(42)+S(48) = 6+12 = 18, but S(90) = 9. This happened because we removed digits summing to 10 from unit’s place and added 1 to ten’s place, reducing digit sum by 9.
Generalizing, The digit sum of the total of two integers is the total digit sum of both integers, less 9 times carry forward occurs. Example: S(42)+S(48) = S(90)-9*1
For maximizing S(A+B+C)
Let’s try to construct P, Q and R such that digit sum of S(A+B+C) = S((P+Q+R)/2) is maximum possible. Ignore triangle inequality for now. Since S(x+y) \leq S(x)+S(y), we would like to avoid carry forwards in P+Q+R at all.
We know S(P+Q+R) \leq S(P)+S(Q)+S(R) = X+Y+Z. We need to look for construction with S(P+Q+R) = X+Y+Z since we are trying to maximize.
One way would be to make integers like, for x = 2, y = 5 and z = 4 as follows
P = 110000000000
Q = 001111100000
R = 000000011110
P+Q+R = 111111111110
(Added extra zero at the end, since P+Q+R would be divided by 2)
In above example, we get A+B+C = 111111111110/2 = 55555555555, leading to digit sum 5*(X+Y+Z) = 55.
But these choices of P, Q, and R don’t satisfy the triangle inequality. Fortunately, we can alter the above construction a bit, only the leading position has two ones in the same place, and R being the largest possible, so that P, Q, and R satisfy the triangle inequality.
P = 10000100000
Q = 10000011110
R = 011110000000
P+Q+R = 21111111110
This gives A+B+C = 1555555555. Since we two occurrences of 5 and gained one occurrence of 1, the maximum digit sum becomes 5*(X+Y+Z)-10+1 = 5*(X+Y+Z-2)+1.
Reason why we chose to repeat 1 instead of any other construction
Try each digit d one by one, and see the impact on the number of forms ddddd0divided by 2.
For example, if we divide 33330 by 2, we get 16665, leading to digit sum 4*6 = 24. So by using up 12 digit sum in constructing 33330, we obtain 24 digit sum in A+B+C, leading to digit sum of A+B+C being bounded by (X+Y+Z)*24/12 = 2*(X+Y+Z)
Choosing to repeat digit 1 gives this upper bound to be 5*(X+Y+Z), since 1110/2 = 555, using digit sum 3 out of X+Y+Z to get 15 digit sum in A+B+C
So we acted greedily.
Now, we need to extract values of A, B, and C from these P, Q, and R, which needs implementing addition and subtraction, which can be done as taught in schools, using carryforwards. Hint: A = (P+Q+R)/2-Q.
For minimizing S(A+B+C)
Since S(x+y) = S(x)+S(y)-9*C where C denotes the sum of carryforwards, we aim to maximize C here. The best case would be where we have A+B+C of the form 100\ldots0, meaning P+Q+R of the form 200\ldots0. This can happen if and only if S(P)+S(Q)+S(R) = 2 \pmod 9 \implies X+Y+Z = 2 \pmod 9.
Generalizing, the best case achievable for S(P+Q+R) would be ((X+Y+Z-2) \bmod 9) +2, since we can simply append remaining digits to satisfy digit sums, but we cannot manage any carry off from them.
But we need to minimize S(A+B+C), not S(P+Q+R). Let’s see how it behaves with X+Y+Z. Let’s write X+Y+Z in the form 9*k+2+2*r where r is a non-negative integer and k is the maximum possible. We can see that 0 \leq r < 9
We shall form P+Q+R of the form 20000(2*r). So the digit sum of A+B+C to be 1+r
Considering all relations below \pmod 9
- X+Y+Z = 2 = 9*k+2+0, we can obtain S(A+B+C) = 1
- X+Y+Z = 4 = 9*k+2+2*1, we can obtain S(A+B+C) = 1+1 = 2
- X+Y+Z = 6 = 9*k+2+2*2, we can obtain S(A+B+C) = 1+2 = 3
- X+Y+Z = 8 = 9*k+2+2*3, we can obtain S(A+B+C) = 1+3 = 4
- X+Y+Z = 1 = 9*k+2+2*4, we can obtain S(A+B+C) = 1+4 = 5
- X+Y+Z = 3 = 9*k+2+2*5, we can obtain S(A+B+C) = 1+5 = 6
- X+Y+Z = 5 = 9*k+2+2*6, we can obtain S(A+B+C) = 1+6 = 7
- X+Y+Z = 7 = 9*k+2+2*7, we can obtain S(A+B+C) = 1+7 = 8
- X+Y+Z = 0 = 9*k+2+2*8, we can obtain S(A+B+C) = 1+8 = 9
We can achieve the above if we manage to carry forward k times.
For example, X = 5, Y = 6 and Z = 7, we get (X+Y+Z) \bmod 9 = 0, so the minimum possible digit sum of A+B+C is 9.
P = 10310
Q = 10320
R = 01420
P+Q+R = 22050
A+B+C = 11025
But we completely disregarded triangle inequality here. Let’s try again the technique we did for the maximum case.i.e. Starting P and Q with 10, and Z with 01.
Now, in order for carryforwards to happen, we need some position p to have digit sum 10 and all significant positions to have digit sums of 9 each.
What we are doing here is to subtract 1 from tens place, and adding 10 to unit’s place, distributing over P, Q and R such that no digit exceeds 9.
Example
We started with P = 100, Q = 100, R = 020 (adding leading 0 for clarity)., so we have P+Q+R = 220. We’ll reduce 1 from ten’s place and add 10 to units place, so P+Q+R remains unaffected. Assuming X, Y and Z are sufficient, we may get P = 102, Q = 105 and R = 013, P+Q+R = 220 holds, and one carry forward has happened.
Issues to be handled
Now, there are two problems. See if you can spot those. Any assumptions involved.
We assumed X, Y, and Z are sufficient, but it’ll never be the case. At every step, we are first increasing X+Y+Z by 1 and then reducing by 10, effectively reducing by 9. But what if X = 10, Y = 0 and Z = 0. We cannot manage to carry forward, since each digit can be at most 9. So every time we select a triplet summing 10, we aim to maximize min(X, Y, Z), then maximizing the second smallest among X, Y, and Z. It is intuitive to prove why triplet (X, Y, Z) = (6,6,6) can achieve whatever (X,Y,Z) = (9,6,3) can.
The second issue is that when we have X+Y+Z = 2 \pmod 9, and we need to follow triangle inequality, we cannot make P, Q and R starting with 10, 10 and 0x respectively. This case needs to be handled specifically.
If we can manage to find a triplet (x, y, z) such that 0 \leq x \leq min(X, 9), 0 \leq y \leq min(9, Y), 0 \leq z \leq min(9, Z) and x+y+z = 20 and (x+y+z) follows triangle inequality. This triplet exists if and only if min(X+Y, Y+Z, Z+X) \geq 11, and can be brute-forced.
If there is any triplet, we can use x as the leading digit of P, y as the leading digit of Q, and z as the leading digit of R, and obtain S(A+B+C) = 1
If there’s no triplet, we cannot make a triplet due to triangle inequality, so the best S(A+B+C) we can achieve is 1+9 = 10.
The implementation of the above can be referred to below.
TIME COMPLEXITY
The time complexity is O(X+Y+Z) per test case.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define ll long long
#define vll vector<ll>
#define ld long double
#define pll pair<ll,ll>
#define PB push_back
#define MP make_pair
#define F first
#define S second
// #define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
// #define osetll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
// #define ook order_of_key
// #define fbo find_by_order
const int MOD=1000000007; //998244353
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
vll sub(vll x,vll y)
{
assert(x.size()==y.size());
vll a=x,b=y,ans;
//a-b
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
ll carry=0;
for(int i=0;i<a.size();i++)
{
ll sub=a[i]-b[i]-carry;
if(sub<0)
{
sub+=10;
carry=1;
}
else
{
carry=0;
}
ans.PB(sub);
}
reverse(ans.begin(),ans.end());
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// ifstream fin;
// ofstream fout;
// fin.open("C:\\Users\\Admin\\OneDrive\\Desktop\\SUMDIGIT\\input.txt",ios::in);
// fout.open("C:\\Users\\Admin\\OneDrive\\Desktop\\SUMDIGIT\\output.txt",ios::out);
ll t;
cin>>t;
for(int i=0;i<t;i++)
{
ll x,y,z,p;
cin>>x>>y>>z>>p;
vll xv,yv,zv,sum;
ll ans;
if(p==0)
{
ans=5*(x+y+z-2)+1;
x--;
y--;
z--;
xv.PB(1);
xv.PB(0);
yv.PB(1);
yv.PB(0);
zv.PB(0);
zv.PB(1);
sum.PB(1);
sum.PB(0);
for(int i=0;i<x;i++)
{
xv.PB(1);
yv.PB(0);
zv.PB(0);
sum.PB(5);
}
for(int i=0;i<y;i++)
{
xv.PB(0);
yv.PB(1);
zv.PB(0);
sum.PB(5);
}
for(int i=0;i<z;i++)
{
xv.PB(0);
yv.PB(0);
zv.PB(1);
sum.PB(5);
}
xv.PB(0);
yv.PB(0);
zv.PB(0);
sum.PB(5);
}
else if(p==1)
{
ll md=(x+y+z)%9;
ll total=(x+y+z);
if(md==2) ans=1;
else if(md==4) ans=2;
else if(md==6) ans=3;
else if(md==8) ans=4;
else if(md==1) ans=5;
else if(md==3) ans=6;
else if(md==5) ans=7;
else if(md==7) ans=8;
else if(md==0) ans=9;
md-=2;
if(md<0) md+=9; // here md is the amount remaining
if(md>2 || (md==0 && min({x+y,y+z,z+x})<11))
{
if(md==0 && min({x+y,y+z,z+x})<11)
{
ans=10;
md=9;
}
x--; y--; z--;
xv.PB(0);
yv.PB(0);
zv.PB(0);
ll first=1;
while(x+y+z>md-3)
{
ll rem=9,temp;
if(first)
{
rem=10;
first=0;
}
temp=min(x,9ll);
xv.PB(temp);
x-=temp;
rem-=temp;
temp=min({y,rem,9ll});
yv.PB(temp);
y-=temp;
rem-=temp;
temp=min({z,rem,9ll});
z-=temp;
zv.PB(temp);
}
if(x>0)
{
xv[xv.size()-1]+=x;
}
if(y>0)
{
yv[yv.size()]+=y;
}
if(z>0)
{
zv[zv.size()]+=z;
}
ll mx=xv[xv.size()-1];
ll j=0;
if(mx<yv[yv.size()-1])
{
mx=yv[yv.size()-1];
j=1;
}
if(mx<zv[zv.size()-1])
{
mx=zv[zv.size()-1];
j=2;
}
if(j==0)
{
xv[xv.size()-1]++;
xv.PB(0);
yv.PB(1);
zv.PB(1);
}
else if(j==1)
{
yv[yv.size()-1]++;
xv.PB(1);
yv.PB(0);
zv.PB(1);
}
else
{
zv[zv.size()-1]++;
xv.PB(1);
yv.PB(1);
zv.PB(0);
}
reverse(xv.begin(),xv.end());
reverse(yv.begin(),yv.end());
reverse(zv.begin(),zv.end());
sum.PB(1);
if(md%2==0)
{
sum.PB(ans-1);
sum.PB(0);
}
else
{
sum.PB(ans-6);
sum.PB(5);
}
for(int i=3;i<xv.size();i++)
{
sum.PB(0);
}
}
else if(md==0)
{
xv.PB(0);
yv.PB(0);
zv.PB(0);
ll rem=19,temp;
x--;
temp=min(x,9ll);
rem-=temp;
xv.PB(temp);
x-=temp;
temp=min({y,9ll,rem});
y-=temp;
rem-=temp;
yv.PB(temp);
temp=min({z,9ll,rem});
z-=temp;
rem-=temp;
zv.PB(temp);
while(x+y+z>0)
{
ll rem=9,temp;
temp=min(x,9ll);
xv.PB(temp);
x-=temp;
rem-=temp;
temp=min({y,rem,9ll});
yv.PB(temp);
y-=temp;
rem-=temp;
temp=min({z,rem,9ll});
z-=temp;
zv.PB(temp);
}
xv[xv.size()-1]++;
sum.PB(1);
for(int i=1;i<xv.size();i++)
{
sum.PB(0);
}
}
else if(md==2)
{
x--; y--; z--;
xv.PB(0);
yv.PB(0);
zv.PB(0);
ll first=1;
while(x+y+z>0)
{
ll rem=9,temp;
if(first)
{
rem=10;
first=0;
}
temp=min(x,9ll);
xv.PB(temp);
x-=temp;
rem-=temp;
temp=min({y,rem,9ll});
yv.PB(temp);
y-=temp;
rem-=temp;
temp=min({z,rem,9ll});
z-=temp;
zv.PB(temp);
}
xv.PB(1);
yv.PB(0);
zv.PB(0);
xv.PB(0);
yv.PB(1);
zv.PB(1);
reverse(xv.begin(),xv.end());
reverse(yv.begin(),yv.end());
reverse(zv.begin(),zv.end());
sum.PB(1);
sum.PB(1);
for(int i=2;i<xv.size();i++)
{
sum.PB(0);
}
}
else
{
assert(md==1);
x--; y--; z--;
xv.PB(0);
yv.PB(0);
zv.PB(0);
ll first=1;
while(x+y+z>0)
{
ll rem=9,temp;
if(first)
{
rem=10;
first=0;
}
temp=min(x,9ll);
xv.PB(temp);
x-=temp;
rem-=temp;
temp=min({y,rem,9ll});
yv.PB(temp);
y-=temp;
rem-=temp;
temp=min({z,rem,9ll});
z-=temp;
zv.PB(temp);
}
ll mx=xv[xv.size()-1];
ll j=0;
if(mx<yv[yv.size()-1])
{
mx=yv[yv.size()-1];
j=1;
}
if(mx<zv[zv.size()-1])
{
mx=zv[zv.size()-1];
j=2;
}
if(j==0)
{
xv[xv.size()-1]++;
xv.PB(0);
yv.PB(1);
zv.PB(1);
}
else if(j==1)
{
yv[yv.size()-1]++;
xv.PB(1);
yv.PB(0);
zv.PB(1);
}
else
{
zv[zv.size()-1]++;
xv.PB(1);
yv.PB(1);
zv.PB(0);
}
sum.PB(1);
sum.PB(5);
for(int i=2;i<xv.size();i++)
{
sum.PB(0);
}
reverse(xv.begin(),xv.end());
reverse(yv.begin(),yv.end());
reverse(zv.begin(),zv.end());
}
}
// for(int i=0;i<xv.size();i++)
// {
// cout<<xv[i];
// }
// cout<<" ";
// for(int i=0;i<yv.size();i++)
// {
// cout<<yv[i];
// }
// cout<<" ";
// for(int i=0;i<zv.size();i++)
// {
// cout<<zv[i];
// }
// cout<<" ";
// for(int i=0;i<sum.size();i++)
// {
// cout<<sum[i];
// }
// cout<<" ";
vll a,b,c;
c=sub(sum,xv);
a=sub(sum,yv);
b=sub(sum,zv);
cout<<ans<<" ";
for(int i=0;i<a.size();i++)
{
cout<<a[i];
}
cout<<" ";
for(int i=0;i<b.size();i++)
{
cout<<b[i];
}
cout<<" ";
for(int i=0;i<c.size();i++)
{
cout<<c[i];
}
cout<<"\n";
}
// in.close();
// fout.close();
}
Tester's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 300300;
int a[N], b[N], c[N];
int s[N];
void printNum(int* a, int L) {
while(L > 1 && a[L - 1] == 0) L--;
for (int i = L - 1; i >= 0; i--)
printf("%d", a[i]);
}
void calcDiff(int* a, int* s, int L) {
int d = 0;
for (int i = 0; i < L; i++) {
d = d + s[i] - a[i];
int z = d % 10;
if (z < 0) z += 10;
a[i] = z;
d = (d - z) / 10;
}
assert(d == 0);
}
void printAns(int L) {
for (int i = 0; i < L; i++)
s[i] = a[i] + b[i] + c[i];
for (int i = 0; i < L - 1; i++) {
s[i + 1] += s[i] / 10;
s[i] %= 10;
}
assert(s[L - 1] < 10);
int d = 0;
for (int i = L - 1; i >= 0; i--) {
d = 10 * d + s[i];
s[i] = d / 2;
d %= 2;
}
assert(d == 0);
calcDiff(a, s, L);
calcDiff(b, s, L);
calcDiff(c, s, L);
printf(" ");
printNum(b, L);
printf(" ");
printNum(c, L);
printf(" ");
printNum(a, L);
printf("\n");
}
void solveMax(int X, int Y, int Z) {
printf("%d", 5 * (X + Y + Z - 2) + 1);
int L = X + Y + Z + 1;
for (int i = 0; i < L; i++)
a[i] = b[i] = c[i] = 0;
a[L - 1] = b[L - 1] = 1;
X--;Y--;
c[L - 2] = 1;
Z--;
for (int i = L - 3; i > 0; i--) {
if (X > 0) {
a[i] = 1;
X--;
} else if (Y > 0) {
b[i] = 1;
Y--;
} else if (Z > 0) {
c[i] = 1;
Z--;
}
}
assert(X + Y + Z == 0);
printAns(L);
}
void choose(int &x, int &y, int &z, int sum) {
int xx = x, yy = y, zz = z;
sum = x + y + z - sum;
xx = min(xx, sum);
yy = min(yy, sum);
zz = min(zz, sum);
assert(xx + yy + zz >= sum);
while(xx + yy + zz > sum) {
if (xx >= yy && xx >= zz) {
xx--;
} else if (yy >= zz) {
yy--;
} else {
zz--;
}
}
x -= xx;
y -= yy;
z -= zz;
}
void solveMin(int X, int Y, int Z) {
int L = max(X, max(Y, Z)) + 3;
for (int i = 0; i < L; i++)
a[i] = b[i] = c[i] = 0;
int S = (X + Y + Z) % 9;
if (S & 1) S += 9;
S /= 2;
if (S == 0) S += 9;
if (S == 1 && min(X + Y, min(X + Z, Y + Z)) < 11) S += 9;
printf("%d", S);
if (S == 1) {
int x = -1, y = -1, z = -1;
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++) {
int q = 20 - i - j;
if (q >= 10) continue;
if (i > X || j > Y || q > Z) continue;
x = i;
y = j;
z = q;
}
assert(x != -1);
a[L - 2] = x;
b[L - 2] = y;
c[L - 2] = z;
X -= x;
Y -= y;
Z -= z;
if (X + Y + Z > 0) {
int p = L - 2;
assert(a[p] > 0 && b[p] > 0 && c[p] > 0);
if (Y == 0) {
b[p]--;
Y++;
} else {
a[p]--;
X++;
}
while(X + Y + Z > 10) {
p--;
a[p] = X;
b[p] = Y;
c[p] = Z;
choose(a[p], b[p], c[p], 9);
X -= a[p];
Y -= b[p];
Z -= c[p];
}
assert(X + Y + Z == 10);
assert(X < 10 && Y < 10 && Z < 10);
p--;
a[p] = X;
b[p] = Y;
c[p] = Z;
}
} else {
a[L - 1] = b[L - 1] = 1;
X--; Y--;
c[L - 2] = 2;
Z -= 2;
int p = L - 2;
while(X + Y + Z >= 9) {
if (Y == 0 && b[p] > 0) {
b[p]--;
Y++;
} else if (a[p] > 0) {
a[p]--;
X++;
} else if (b[p] > 0) {
b[p]--;
Y++;
} else if (c[p] > 0) {
c[p]--;
Z++;
} else throw;
p--;
a[p] = min(9, X - 1);
b[p] = min(9, Y - 1);
c[p] = min(9, Z);
int tot = a[p] + b[p] + c[p];
if (tot < 10) {
if (a[p] < 9 && tot < 10) {
a[p]++;
tot++;
}
if (b[p] < 9 && tot < 10) {
b[p]++;
tot++;
}
} else {
while(a[p] > 0 && tot > 10) {
a[p]--;
tot--;
}
while(b[p] > 0 && tot > 10) {
b[p]--;
tot--;
}
while(c[p] > 0 && tot > 10) {
c[p]--;
tot--;
}
}
assert(tot == 10);
X -= a[p];
Y -= b[p];
Z -= c[p];
}
p--;
a[p] = X;
b[p] = Y;
c[p] = Z;
}
printAns(L);
}
void solve() {
int x, y, z, p;
scanf("%d%d%d%d", &x, &y, &z, &p);
//eprintf("%d %d %d %d\n", x, y, z, p);
if (p == 0)
solveMax(x, y, z);
else
solveMin(x, y, z);
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class SUMDIGIT{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int X = ni(), Y = ni(), Z = ni(), P = ni();
if(P == 0)printAns(solveMax(X, Y, Z), X, Y, Z);
else printAns(solveMin(X, Y, Z), X, Y, Z);
}
int[][] solveMax(int X, int Y, int Z){
int ans = 5*(X+Y+Z-2)+1;
int length = X+Y+Z;
int[] A = new int[length], B = new int[length], C = new int[length];
A[0] = 1;X--;
B[0] = 1;Y--;
for(int i = 1; i< length; i++){
if(Z > 0){C[i]++;Z--;}
else if(X > 0){A[i]++;X--;}
else if(Y > 0){B[i]++;Y--;}
}
return new int[][]{{length, ans}, A, B, C};
}
int[][] solveMin(int X, int Y, int Z){
int ans = (X+Y+Z)%9;
if(ans%2 == 1)ans += 9;
ans /= 2;
if(ans == 0)ans += 9;
if(ans == 1 && X+Y+Z-Math.max(X, Math.max(Y, Z)) < 11)ans += 9;
int length = Math.max(X, Math.max(Y, Z))+4;
int[] A = new int[length], B = new int[length], C = new int[length];
if(ans == 1){
//Finding triplet with digit sum 20 and satisfying triangle inequality.
int pos = 1;
outer:for(int p = 0; p < 10; p++){
for(int q = 0; q< 10; q++){
int r = 20-p-q;
if(r >= 10)continue;
//max(p, q, r) < 10, p+q+r = 20, so triangle inequality holds
if(p > X || q > Y || r > Z)continue;
A[pos] = p;
B[pos] = q;
C[pos] = r;
X -= p;
Y -= q;
Z -= r;
break outer;
}
}
assert(A[pos]+B[pos]+C[pos] > 0);//Found triplet
assert((X+Y+Z)%9 == 0);//Since 9|(X+Y+Z-20) must hold.
while(X+Y+Z > 0){
//Subtracting 1 from previous position
int mn = Integer.MAX_VALUE;
if(A[pos] > 0)mn = Math.min(mn, X);
if(B[pos] > 0)mn = Math.min(mn, Y);
if(C[pos] > 0)mn = Math.min(mn, Z);
assert(mn != Integer.MAX_VALUE);
if(X == mn && A[pos] > 0){
X++;
A[pos]--;
}else if(Y == mn && B[pos] > 0){
Y++;
B[pos]--;
}else if(Z == mn && C[pos] > 0){
Z++;
C[pos]--;
}else assert(false);
//finding triplet (xx, yy, zz) such that xx+yy+zz is 10
pos++;
int xx = Math.min(X, 9), yy = Math.min(Y, 9), zz = Math.min(Z, 9);
int total = xx+yy+zz;
assert(total >= 10);
while(total > 10){
int max = Math.max(xx, Math.max(yy, zz));
if(max == xx){
xx--;
total--;
}else if(max == yy){
yy--;
total--;
}else{
zz--;
total--;
}
}
//Assigning current triplet
A[pos] = xx;
B[pos] = yy;
C[pos] = zz;
X -= xx;
Y -= yy;
Z -= zz;
}
return new int[][]{{length, ans}, A, B, C};
}
A[0] = 1;
B[0] = 1;
C[1] = 2;
X--;Y--;Z -= 2;
int pos = 1;
while(X+Y+Z >= 9){
//Subtracting 1 from previous position, aiming to maximizing min(X, Y, Z), and then second smallest among X, Y and Z
int mn = Integer.MAX_VALUE;
if(A[pos] > 0)mn = Math.min(mn, X);
if(B[pos] > 0)mn = Math.min(mn, Y);
if(C[pos] > 0)mn = Math.min(mn, Z);
assert(mn != Integer.MAX_VALUE);
if(X == mn && A[pos] > 0){
X++;
A[pos]--;
}else if(Y == mn && B[pos] > 0){
Y++;
B[pos]--;
}else if(Z == mn && C[pos] > 0){
Z++;
C[pos]--;
}else assert(false);
//finding triplet (xx, yy, zz) such that xx+yy+zz is 10
pos++;
int xx = Math.min(X, 9), yy = Math.min(Y, 9), zz = Math.min(Z, 9);
int total = xx+yy+zz;
assert(total >= 10);
while(total > 10){
int max = Math.max(xx, Math.max(yy, zz));
if(max == xx){
xx--;
total--;
}else if(max == yy){
yy--;
total--;
}else{
zz--;
total--;
}
}
assert(total == 10);//xx+yy+zz = 10 holds
//assigining
A[pos] = xx;
B[pos] = yy;
C[pos] = zz;
X -= xx;
Y -= yy;
Z -= zz;
}
pos++;
//X+Y+Z < 9, so no carry forward here.
A[pos] = X;
B[pos] = Y;
C[pos] = Z;
return new int[][]{{length, ans}, A, B, C};
}
int[] add(int[] a, int[] b){
//Do not reuse this, assumptions for current problem involved
assert(a.length == b.length);
int[] sum = new int[a.length];
for(int i = a.length-1; i>= 0;i--){
sum[i] += a[i]+b[i];
while(sum[i] >= 10){
sum[i] -= 10;
sum[i-1]++;
}
}
return sum;
}
//Works only if a >= b, may have leading zeros
int[] subtract(int[] a, int[] b){
assert(a.length == b.length);
int[] c = new int[a.length];
int d = 0;
for(int i = c.length-1; i>= 0; i--){
c[i] = a[i]-b[i]-d;
d = 0;
while(c[i] < 0){
c[i] += 10;
d++;
}
}
assert(d == 0);
return c;
}
//Affects array a directly
void divideBy2(int[] a){
int rem = 0;
for(int i = 0; i< a.length; i++){
int q = (rem*10+a[i])/2;
rem = (rem*10+a[i])-q*2;
a[i] = q;
}
assert(rem == 0);
}
int digitSum(int[] a){
int tot = 0;
for(int x:a)tot += x;
return tot;
}
//Converts number to string without leading zeros
String toString(int[] num){
StringBuilder ans = new StringBuilder("");
for(int i = 0; i< num.length; i++){
if(num[i] > 0 || ans.length() > 0)
ans.append(num[i]);
}
if(ans.length()== 0)ans.append('0');
return ans.toString();
}
void printAns(int[][] ans, int X, int Y, int Z){
int[] sum = add(add(ans[1], ans[2]), ans[3]);
divideBy2(sum);
int[] a = subtract(sum, ans[2]), b = subtract(sum, ans[3]), c = subtract(sum, ans[1]);
assert(digitSum(add(a, b)) == X);
assert(digitSum(add(c, b)) == Y);
assert(digitSum(add(a, c)) == Z);
assert(digitSum(add(a, add(b, c))) == ans[0][1]);
pn(ans[0][1]+" "+toString(a)+" "+toString(b)+" "+toString(c));
}
void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
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 SUMDIGIT().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. 
