PROBLEM LINK:
Division 1
Division 2
Video Editorial
Author: Aryan Agarwala
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta
DIFFICULTY:
Simple
PREREQUISITES:
Number Theory
PROBLEM:
You are given two numbers A and B. We define the power of a number as the sum of its digits. Let’s suppose X and Y are those numbers for which their power is A and B respectively. If A has more digits than B then print “1 ” and number of digits in A else print “0 “ and number of digits in B.
QUICK EXPLANATION:
For a number P, we can say that the minimum number of digits used to found the number X whose power is equal P, is equal to:
minimum number of digits required = (P + 8)/9
EXPLANATION:
We know that there are 10 digits possible i.e. from 0 to 9, As we want to create the number with the use of a minimum number of digits, we should use digit 9 as much possible which means for any power P, if we want to find out the number for which P is the power with a minimum number of digits then all the digits are 9 except 1. If the P is divisible by 9 then all the digits are 9 only.
Now to construct the number, we should use 9 as it is the highest possible digit. Hence we can say that:
- 1 \le sum \le 9 => at least 1 digit
- 10 \le sum \le 18 => at least 2 digit
- 19 \le sum \le 27 => at least 3 digit
- and so on.
Hence by dividing the (final power + 8) from 9, will tell the minimum number of digits that can be needed to form the final power. By this, we can easily answer the question.
COMPLEXITY ANALYSIS:
TIME: O(1)
SPACE: O(1)
SOLUTIONS:
Setter's Solution
Tester's Solution
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(a) ((int)(a.size()))
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
int main()
{
int T;
cin >> T;
assert(1 <= T && T <= 1000000);
while(T--)
{
int pc, pr;
cin >> pc >> pr;
assert(1 <= pc && pc <= 1000000);
assert(1 <= pr && pr <= 1000000);
int cnt1 = (pc + 8) / 9;
int cnt2 = (pr + 8) / 9;
cout << (cnt2 <= cnt1) << " " << min(cnt1 , cnt2) << endl;
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int a,b;
cin >> a >> b;
a += 8;
a /= 9;
b += 8;
b /= 9;
cout << (a >= b) << " " << min(a,b) << endl;
}
}