PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N people in ChefLand. A disease has spread such that at the end of day 0, a single person is infected. Until everyone is infected,
- The number of infected people doubles during the next 10 days.
- The number of infected people triples from day 11 onwards.
Find the number of infected people at the end of day D.
EXPLANATION:
Subtask 1: D \leq 20
Initially, the number of infected people equals 1. We run a loop for days 1 to D. For each day, if the day number is less than or equal to 10, we double the number of infected people, else, we triple the number of infected people.
Finally, since the number of infected people cannot exceed N (the total population), we print the minimum value out of the current number of infected people and N.
Subtask 2: D \leq 10^8
Since the number of testcases can go upto 300 and for each test case, we run a loop with complexity O(D), the solution described for Subtask 1 would not pass for the given time limit.
A simple observation is to note that the maximum value of N is 10^8. Since the number of infected people is increasing exponentially, it will be equal to 10^8 in ~ 21 days only.
Thus, we can keep a check on the number of infected people at the end of each day. Once it exceeds the total population N, we know that the answer cannot change and we can break the loop to print the answer.
Additionally the maximum value calculated will be at most 3 \times N \leq 3 \cdot 10^8, which is well within the maximum limit of a 32 bit integer (2^{31} - 1 \approx 2 \cdot 10^9) and thus no overflow occurs.
Many participants, correctly identified that the answer is \mathsf{min}(N, 2^{\mathsf{min}(X, 10)} \cdot 3^{\mathsf{max}(0, X - 10)}), but still received only 30 pts, since they used math functions (such as the pow() function from mathlib.h library in C++) which was incorrect since the pow() function can only return values upto 10^{308} ( the long double data type). Moreover, 3^{10^8} = 10^{\log_{10}{3} \cdot 10^8} \approx 10^{4.7 \cdot 10^7} is so large that it is very difficult to obtain its digits (there are around 4.7 \cdot 10^7 digits) within the time limit (in any language including Python).
TIME COMPLEXITY:
The time complexity is O(\mathsf{min}(D, \log{N})) per test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = readInt(1, 300, '\n');
while(t--){
ll n, x;
n = readInt(1, 100000000, ' ');
x = readInt(0, 100000000, '\n');
ll tot = 1;
ll temp;
for(int i = 0; i < x; i++){
temp = tot;
if(i < 10){
temp *= 2;
}else{
temp *= 3;
}
if(temp > n){
tot = n;
break;
}
tot = temp;
}
cout<<tot<<"\n";
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007
int n, x;
void solve()
{
cin>>n>>x;
int infected = 1;
for(int i = 1; i<=x; i++){
if(i<=10){
infected *= 2;
}
else{
infected *= 3;
}
if(infected>=n){
break;
}
}
cout<<min(n, infected);
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
sync;
int t = 1;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}