Read problem statements in [Russian]

Chef is having a candlelit dinner with his girlfriend at his place. Currently, it is time $0$, Chef just managed to light a candle, but he is out of matchsticks.

Since Chef has an infinite supply of (unlit) candles, he can use the following strategy: each second (starting at time $0$), he takes one lit candle and lights up $X$ other candles using it. This process takes $1$ unit of time to complete, i.e. if Chef starts lighting up $X$ candles at a time $t_{1}$, he is able to finish at the time $t_{1} + 1$.

However, since candle wax is limited, a candle can only burn for $Y$ units of time and then it is extinguished.

Chef's girlfriend arrives at a time $A$ — specifically, after all the candles that were supposed to get extinguished at time $A$ have been extinguished and after Chef lights up all the candles that he was lighting up since time $A-1$. Now Chef wants to know the maximum number of candles which can be lit at the time $A$ to impress his girlfriend.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $A$, $Y$ and $X$.

------  Output ------
For each test case, print a single line containing one integer — the maximum number of lit candles Chef can impress his girlfriend with.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ A, Y, X ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (40 points): $A ≥ Y$

Subtask #2 (60 points): original constraints

----- Sample Input 1 ------ 
3

1 1 1

1 2 1

2 2 1
----- Sample Output 1 ------ 
1

2

2
----- explanation 1 ------ 
Example case 1: At the time $0$, there is one lit candle, using which we light $1$ more candle. At the time $1$, the starting candle gets extinguished and the candle which we started lighting up at the time $0$ is lit, so we have only $1$ candle lit up when Chef's girlfriend arrives.

Example case 2: At the time $0$, there is one lit candle, using which we light $1$ more candle. At the time $1$, the candle which we started lighting up at the time $0$ and the starting candle are both lit.

Example case 3: At the time $0$, there is one lit candle, using which we light $1$ more candle. At the time $1$, the candle which we started lighting up at time $0$ is lit, and we start lighting up one more candle. At the time $2$, the starting candle gets extinguished and the candle which we started lighting up at the time $1$ is lit. In total, we have $2$ lit candles when Chef's girlfriend arrives.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
from collections import deque

def soln(a: int, y: int, x: int) -> int:
	if y > a:
		return a * x + 1
	return y * x
for _ in range(int(input())):
	(a, y, x) = map(int, input().split())
	print(soln(a, y, x))


for _ in range(int(input())):
	(a, y, x) = map(int, input().split())
	if a >= y:
		print(y * x)
	else:
		print(x * a + 1)


mod = 1000000007

def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
import sys
from collections import Counter
from decimal import Decimal

def main():
	if y > a:
		print(a * x + 1)
	else:
		print(a * x + 1 - ((a - y) * x + 1))
t = int(input())
for _ in range(t):
	(a, y, x) = integer_list()
	main()


t = int(input())
for i in range(t):
	(a, y, x) = map(int, input().split())
	if y > a:
		print(a * x + 1)
	else:
		print(a * x + 1 - ((a - y) * x + 1))


try:
	for _ in range(int(input())):
		(t, y, x) = list(map(int, input().split()))
		if y > t:
			print(t * x + 1)
		else:
			print(t * x - (t - y) * x)
except:
	pass


tc = int(input())
for i in range(tc):
	(a, y, x) = map(int, input().split())
	m = a * x + 1
	if a >= y:
		m = y * x
	print(m)


queries = int(input())
while queries > 0:
	queries -= 1
	(a, y, x) = map(int, input().split())
	if a >= y:
		print(y * x)
	else:
		print(1 + a * x)


import sys
MOD = 1000000007
inp = sys.stdin.readline

def ii():
	return int(inp())

def iis():
	return [int(i) for i in inp().split()]
for t in range(ii()):
	(a, y, x) = iis()
	if a >= y:
		print(y * x)
	else:
		print(a * x + 1)


t = int(input())
for _ in range(t):
	(a, y, x) = map(int, input().split())
	maxi = a * x + 1
	if a >= y:
		maxi = y * x
	print(maxi)


T = int(input())
for i in range(T):
	(A, Y, X) = map(int, input().split())
	if Y > A:
		print(1 + X * A)
	else:
		print(X * Y)


try:
	for _ in range(int(input())):
		A = [int(x) for x in input().split()]
		x = min(A[0], A[1])
		res = x * A[2]
		if A[0] < A[1]:
			res += 1
		print(res)
except:
	pass


T = int(input())
for i in range(0, T):
	(A, Y, X) = map(int, input().split())
	c = A - Y + 1
	if c >= 1:
		lit = 1 + (A - max(c - 1, 0)) * X - min(1, c) * 1
		print(lit)
	else:
		print(1 + A * X)


for i in range(int(input())):
	(afgdfg, y, x) = map(int, input().split())
	if afgdfg >= y:
		print(y * x)
	else:
		print(afgdfg * x + 1)


for _ in range(int(input())):
	(A, Y, X) = list(map(int, input().split()))
	if A < Y:
		print(1 + A * X)
	elif A >= Y:
		print(Y * X)


t = int(input())
for _ in range(t):
	(a, y, x) = map(int, input().split())
	ans = 0
	if a >= y:
		print(y * x)
	else:
		ans = a * x
		print(ans + 1)


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)
	elif t == y:
		print(x * t)
	else:
		print(x * t + 1)


for i in range(int(input())):
	(a, y, x) = map(int, input().split())
	print((1 + a * x) * (a < y) + y * x * (a >= y))


def prog_name():
	(arrival, duration, number) = map(int, input().split())
	if arrival >= duration:
		print(duration * number)
	else:
		print(number * arrival + 1)
t = int(input())
for unique in range(t):
	prog_name()


for _ in range(int(input())):
	(a, y, x) = map(int, input().split())
	res = 0
	if y - a > 0:
		res += 1
	res += min(a, y) * x
	print(res)


t = int(input())
for _ in range(0, t):
	(A, Y, X) = [int(x) for x in input().split()]
	if A >= Y:
		count = X * Y
	else:
		count = X * A + 1
	print(count)


t = int(input())
for _ in range(t):
	(a, y, x) = [int(i) for i in input().split(' ')]
	t = min(y, a)
	first = 0
	if y > a:
		first = 1
	print(t * x + first)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	t = a * c
	t += 1
	temp = a - b
	if a < b:
		final = t
	else:
		final = t - temp * c
		final -= 1
	print(final)


try:
	t = int(input())
	for i in range(0, t):
		(a, y, x) = map(int, input().split(' '))
		gh = 1 + a * x
		if a >= y:
			gh -= 1 + (a - y) * x
		print(gh)
except:
	pass


for i in range(int(input())):
	(a, y, x) = [int(x) for x in input().split()]
	to = a * x + 1
	ans = to
	if a >= y:
		ans -= 1 + (a - y) * x
	print(ans)


def solve():
	(a, y, x) = map(int, input().split())
	if a < y:
		print(a * x + 1)
	elif a >= y:
		print(y * x)
for _ in range(int(input())):
	solve()


t = int(input())
while t:
	(a, y, x) = map(int, input().split())
	s = 1 + a * x
	if a == y:
		s -= 1
	elif a > y:
		s -= (a - y) * x + 1
	print(s)
	t -= 1


import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 4)
from math import sqrt, ceil
t = int(input())
for _ in range(t):
	(A, Y, X) = map(int, input().split())
	if A >= Y:
		print(X * Y)
	else:
		print(1 + X * A)


for _ in range(int(input())):
	(A, Y, X) = map(int, input().split())
	(t, c) = (0, 0)
	if Y <= A:
		c = Y * X
	else:
		c = 1 + X * A
	print(c)


def glc(g, l, c) -> int:
	if g < l and c > 1:
		return g * c + 1
	lightCandles = g * c
	extinguished = (g - l) * c
	return lightCandles - extinguished
for _ in range(int(input())):
	(gfTime, lightDur, candlesAble2Light) = map(int, input().strip().split())
	print(glc(gfTime, lightDur, candlesAble2Light))


for _ in range(int(input())):
	(a, y, k) = map(int, input().split())
	if a < y:
		candles = a * k + 1
	else:
		candles = y * k
	print(candles)


try:
	for _ in range(int(input())):
		(a, y, x) = map(int, input().split())
		if a >= y:
			print(y * x)
		else:
			value = a * x + 1
			print(value - a // y)
except:
	pass


t = int(input())
for i in range(t):
	(a, y, x) = map(int, input().split())
	lit = 1
	if a < y:
		number = 1 + a * x
	if a >= y:
		number = y * x
	print(number)


import math
t = int(input())
while t:
	(a, y, x) = map(int, input().split())
	c = 1 + x * a
	if a < y:
		print(c)
	else:
		c = c - ((a - y) * x + 1)
		print(c)
	t -= 1


for _ in range(int(input())):
	(a, y, x) = map(int, input().split())
	ans = 1
	if y > a:
		print(a * x + 1)
		continue
	yyy = a - y
	ans -= yyy * x
	ans += a * x
	print(ans - 1)


t = int(input())
while t:
	(a, y, x) = map(int, input().split())
	tol = a * x + 1
	unl = 0
	if a < y:
		unl = tol
	else:
		unl = tol - (a - y) * x - 1
	print(unl)
	t = t - 1


t = int(input())
while t:
	(a, y, x) = map(int, input().split())
	if a < y:
		print(a * x + 1)
	else:
		print(y * x)
	t = t - 1


for i in range(int(input())):
	l1 = list(map(int, input().split()))
	A = l1[0]
	Y = l1[1]
	X = l1[2]
	if A >= Y:
		c = X * Y
	elif A < Y:
		c = A * X + 1
	print(c)


for _ in range(int(input())):
	(A, Y, X) = map(int, input().split())
	if A >= Y:
		print(Y * X)
	else:
		print(A * X + 1)