PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Daanish Mahajan
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Chef has 1 lit candle, and infinitely many unlit candles. Each second, he can take one lit candle and use it to light x unlit ones. y seconds after a candle is lit, it runs out of wax and is extinguished. What is the maximum number of candles which can be lit at time t?
QUICK EXPLANATION
The answer is x\cdot y if t\geq y and x\cdot t+1 otherwise
EXPLANATION:
Subtask 1
When t\geq y, the only active candles at time t are the ones which lit up time t, t-1, t-2, \dotsc, t-y+1; y seconds of time in total. Any candle which was lit before that will also be extinguished before time t. In particular, because t\geq y, t-y+1 \geq 1; which means that the candle Chef started out with at time 0 will also be extinguished. Thus, we have y seconds, in each of which x candles are lit. This gives us x\cdot y candles in total.
Subtask 2
t\geq y can be solved as above. Now we also have to worry about the case when t < y. However, t < y just means that no candle which is lit up will extinguish before time t - so all we need to do is count the number of candles which are lit.
x candles light up at each of the seconds 1, 2, \dotsc, t; and the candle Chef starts out with isn’t extinguished either.
This gives us x\cdot t + 1 candles at time t.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
SOLUTIONS:
Setter's Solution (C++)
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
const int maxt = 1e5, minv = 1, maxv = 1e9;
int main()
{
int t; cin >> t;
while(t--){
ll time, y, x; cin >> time >> y >> x;
ll ans = 0, cnt = 0;
if(time - y + 1 <= 0){
cnt = cnt + 1;
ans = 1 + time * x;
}else{
ans = x + (y - 1) * x;
}
cout << ans << endl;
}
}
Tester's Solution (C++)
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main(){
fastio;
int tests;
cin>>tests;
while(tests--){
long long int t, y, x;
cin>>t>>y>>x;
if(t >= y){
cout<<x*y<<endl;
}
else{
cout<<1+x*t<<endl;
}
}
return 0;
}
Editorialist's Solution (Python)
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
t, y, x = map(int, input().split())
if t >= y:
print(x*y)
else:
print(x*t+1)
NIce explanation. I should have given more time for this.