PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Srikkanth R and Daanish Mahajan
Tester: Miten Shah
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Maths, Observation
PROBLEM:
Let f(n, B) be the sum of digits of the integer n when written in base B.
More formally, if n = \sum\limits_{i=0}^{\infty} a_i B^i where a_i is an integer in the range [0, B-1], then f(n, B) = \sum\limits_{i=0}^{\infty} a_i.
Given Q queries, each consisting of three integers n, l and r. Find the value of B corresponding to which f(n, B) is minimum for all l \leq B \leq r. If there are multiple such values, you can print any of them.
EXPLANATION:
Our goal is to decide the base B which lies in the range [l, r] such that the sum of digits of the integer N when written in base B is minimum possible among all the choices of B.
The first basic observation that we can draw from the problem is that if we choose any Base B which is greater than \sqrt{N}, then there are only 2 non-zero digits in the base B representation. Hence, in this case, our number can be represented as:
Since our goal is to minimize the digit sum i.e. (a+b). Our x is greater than \sqrt{N}, hence our a will carry from \sqrt{N} -1 to 1. Hence for all the possible values of a we can simply found out the maximum value of x and then take out the minimum value of (a+b). We can easily found out the values of x and b in O(1) time.
For every possible value of a, we have:
and
It takes us O(\sqrt{N}) time to traverse all the possible values of a.
Now we are only left with such bases whose values are less than \sqrt{N}. For that, we can easily brute force all the possible bases from l to \sqrt{N}.
Finally, we will output the bases B which gives us the minimum possible sum of digits among all the choices of B.
TIME COMPLEXITY:
O(\sqrt{N} * C),
where C is constant for finding the base representation of number N.
SOLUTIONS:
Author's
#include <bits/stdc++.h>
#define LL long long
using namespace std;
clock_t start = clock();
LL readInt(LL l, LL r, char endd) {
LL x = 0;
char ch = getchar();
bool first = true, neg = false;
while (true) {
if (ch == endd) {
break;
} else if (ch == '-') {
assert(first);
neg = true;
} else if (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - '0';
} else {
assert(false);
}
first = false;
ch = getchar();
}
if (neg) x = -x;
if (x < l || x > r) {
cerr << l << " " << r << " " << x << " failed\n";
}
assert(l <= x && x <= r);
return x;
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert (g != -1);
if (g == endd) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
LL readIntSp(LL l, LL r) {
return readInt(l, r, ' ');
}
LL readIntLn(LL l, LL r) {
return readInt(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
void solve() {
int n = readIntSp(2, (int)1e9), l = readIntSp(2, (int)1e9), r = readIntLn(l, (int)1e9);
int i, have = -1, go = (int)1e9;
for (i=l;i*i<=n&&i<=r;++i) {
int ans = 0, m = n;
while (m > 0) {
ans += m % i;
m /= i;
}
if (ans < go) {
go = ans;
have = i;
}
}
for (;i<=r;++i) {
int nxt = min(r, n / (n / i));
int ans = n % nxt + n / nxt;
if (ans < go) {
go = ans;
have = nxt;
}
i = nxt + 1;
}
assert(have >= l && have <= r);
cout << have << '\n';
}
int main() {
// Start solution here use readIntLn, readIntSp and readStringSp and readStringLn
// for reading input
int T = readIntLn(1, 1000);
while (T--) {
solve();
}
// End solution here
assert(getchar() == EOF);
cerr << fixed << setprecision(10);
cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
return 0;
}
Tester
#include <bits/stdc++.h>
#define LL long long
using namespace std;
clock_t start = clock();
LL readInt(LL l, LL r, char endd) {
LL x = 0;
char ch = getchar();
bool first = true, neg = false;
while (true) {
if (ch == endd) {
break;
} else if (ch == '-') {
assert(first);
neg = true;
} else if (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - '0';
} else {
assert(false);
}
first = false;
ch = getchar();
}
if (neg) x = -x;
if (x < l || x > r) {
cerr << l << " " << r << " " << x << " failed\n";
}
assert(l <= x && x <= r);
return x;
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert (g != -1);
if (g == endd) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
LL readIntSp(LL l, LL r) {
return readInt(l, r, ' ');
}
LL readIntLn(LL l, LL r) {
return readInt(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
void solve() {
int n = readIntSp(2, (int)1e9), l = readIntSp(2, (int)1e9), r = readIntLn(l, (int)1e9);
int i, have = -1, go = (int)1e9;
for (i=l;i*i<=n&&i<=r;++i) {
int ans = 0, m = n;
while (m > 0) {
ans += m % i;
m /= i;
}
if (ans < go) {
go = ans;
have = i;
}
}
for (;i<=r;++i) {
int nxt = min(r, n / (n / i));
int ans = n % nxt + n / nxt;
if (ans < go) {
go = ans;
have = nxt;
}
i = nxt + 1;
}
assert(have >= l && have <= r);
cout << have << '\n';
}
int main() {
// Start solution here use readIntLn, readIntSp and readStringSp and readStringLn
// for reading input
int T = readIntLn(1, 1000);
while (T--) {
solve();
}
// End solution here
assert(getchar() == EOF);
cerr << fixed << setprecision(10);
cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
return 0;
}