Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There are two types of vaccines available: Covaxin and Covishield.

A black marketeer has X coins and wants to buy as many vaccines as possible. Due to the black marketing concerns, government has enforced the following policy:

i^{th} dose of Covaxin costs a + (i - 1)\cdot b coins for every i ≥ 1. 

i^{th} dose of Covishield costs c + (i - 1)\cdot d coins for every i ≥ 1.

The values of the four parameters a, b, c and d, however isn't constant and might vary from query to query. In general the value of these four parameters for i^{th} query will be A_{i}, B_{i}, C_{i} and D_{i} respectively. 
Let ans_{i} be the maximum total quantity of vaccines the black marketeer can buy corresponding to the i^{th} query. For each query, you have to find the value of ans_{i}. 
 
You will be given integers A_{1}, B_{1}, C_{1}, D_{1}, P, Q, R, S, T and M which will define the queries to be followed. 

For i ≥ 1 and i ≤ I - 1:
A_{i+1} = (A_{i} + ans_{i}\cdot T) \bmod M + P
B_{i+1} = (B_{i} + ans_{i}\cdot T) \bmod M + Q 
C_{i+1} = (C_{i} + ans_{i}\cdot T) \bmod M + R 
D_{i+1} = (D_{i} + ans_{i}\cdot T) \bmod M + S .

Note: Since the output is large, prefer using fast input-output methods.

------ Input Format ------ 

- First line contains of input contains an integer I denoting the number of queries.
- Second line of input contains five integers X, A_{1}, B_{1}, C_{1}, D_{1}.
- Third line of input contains six integers P, Q, R, S, T, M.

------ Output Format ------ 

For each query output the maximum quantity of vaccines the black marketeer can buy.

------ Constraints ------ 

$1 ≤ I ≤ 5 \cdot 10^{5}$
$1 ≤ X,A_{1},B_{1},C_{1},D_{1} ≤ 10^{18}$
$1 ≤ P,Q,R,S,M ≤ 10^{18}$
$1 ≤ T ≤ 10^{9}$

------ subtasks ------ 

Subtask #1 (10 points): 
$1 ≤ I ≤ 10^{3}$
$1 ≤ X ≤ 10^{9}$
Time limit: $1$ sec 

Subtask #2 (30 points): 
$1 ≤ I ≤ 10^{3}$
$1 ≤ X ≤ 10^{15}$
$10^{9} ≤ A_{1} ≤ 10^{18}$
$10^{9} ≤ B_{1} ≤ 10^{18}$
$10^{9} ≤ P ≤ 10^{18}$
$10^{9} ≤ Q ≤ 10^{18}$
Time limit: $1$ sec 

Subtask #3 (60 points): 
Original constraints
Time limit: $3$ sec 

----- Sample Input 1 ------ 
3
20 2 3 4 1
3 7 8 4 11 20

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

----- explanation 1 ------ 

Test case $1$: 
- For the first query, $[a, b, c, d] = [A_{1}, B_{1}, C_{1}, D_{1}] = [2, 3, 4, 1]$. It is optimal to buy $2$ doses of Covaxin $(2+5=7)$ and $2$ doses of Covishield $(4+5=9)$. So the total money spent is $7+9=16$ and now the black marketeer cannot buy any more doses. So the answer is 4.

- For the second query, $[a, b, c, d] = [A_{2}, B_{2}, C_{2}, D_{2}] = [(2 + 11\cdot 4)\bmod 20 + 3, (3 + 11\cdot 4) \bmod 20 + 7, (4 + 11\cdot 4) \bmod 20 + 8, (1 + 11\cdot 4) \bmod 20 + 4]=[9, 14, 16, 9]$. 

- For the third and the last query, $[a, b, c, d] = [A_{3}, B_{3}, C_{3}, D_{3}] = [3, 12, 15, 4]$.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Mathematics

Complete search


Solutions:
import cmath

def find_total(x, y):
	return B * x * x / 2 + j * x + D * y * y / 2 + k * y

def find_root(a, b, c):
	dis = b ** 2 - 4 * a * c
	r1 = (-b - cmath.sqrt(dis)) / (2 * a)
	r2 = (-b + cmath.sqrt(dis)) / (2 * a)
	return max(r1.real, r2.real)
q = int(input())
(X, A, B, C, D) = map(int, input().split())
(P, Q, R, S, T, M) = map(int, input().split())
for _ in range(q):
	i = (2 * (A - C) + D - B) / (2 * D)
	j = A - B / 2
	k = C - D / 2
	a = B / 2 * (B / D + 1)
	b = j + B * k / D + B * i
	c = i * k + D * i * i / 2 - X
	r = find_root(a, b, c)
	y = r * B / D + i
	(r, y) = (int(r), int(y))
	arr = [(r + i, y + j) for i in range(2) for j in range(2)]
	cx = int(find_root(B / 2, j, -X))
	remain = X - find_total(cx, 0)
	arr.append((cx, int(find_root(D / 2, k, -remain))))
	csd = int(find_root(D / 2, k, -X))
	remain = X - find_total(0, csd)
	arr.append((int(find_root(B / 2, j, -remain)), csd))
	ans = max(map(lambda y: y[0] + y[1], filter(lambda x: x[0] >= 0 and x[1] >= 0 and (find_total(x[0], x[1]) <= X), arr)))
	print(ans)
	A = (A + ans * T) % M + P
	B = (B + ans * T) % M + Q
	C = (C + ans * T) % M + R
	D = (D + ans * T) % M + S


import sys
import time
start_time = time.time()
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass
input = sys.stdin.readline
I = int(input())

def check(a, b, c, d, t, x):
	l = 0
	r = t
	while r >= l:
		m = (l + r) // 2
		n = t - m
		p = 2 * a * m + b * m * (m - 1)
		q = 2 * c * n + d * n * (n - 1)
		u = a + (m - 1) * b
		v = c + (n - 1) * d
		if p + q <= 2 * x:
			return True
		elif u == v:
			return False
		elif u > v:
			r = m - 1
		else:
			l = m + 1
	return False
(x, a, b, c, d) = map(int, input().split())
(p, q, f, s, t, m) = map(int, input().split())
mp = {}
for i in range(I):
	w = (a, b, c, d)
	if w in mp:
		ans = mp[w]
	else:
		ans = 0
		r = x // min(a, c)
		l = 0
		while r >= l:
			e = (l + r) // 2
			if check(a, b, c, d, e, x):
				l = e + 1
				ans = e
			else:
				r = e - 1
		mp[w] = ans
	print(ans)
	k = ans * t
	a += k
	a %= m
	a += p
	b += k
	b %= m
	b += q
	c += k
	c %= m
	c += f
	d += k
	d %= m
	d += s
end_time = time.time()
sys.stderr.write('Time: ' + str(end_time - start_time))


from math import sqrt
N = int(input())
[X, a, b, c, d] = [int(k) for k in input().split()]
[P, Q, R, S, T, M] = [int(k) for k in input().split()]
for i in range(N):
	A1 = b / 2
	B1 = a - b / 2
	C1 = B1 ** 2 / (4 * A1)
	A2 = d / 2
	B2 = c - d / 2
	C2 = B2 ** 2 / (4 * A2)
	aa = sqrt(2 * (X + C1 + C2) / b)
	bb = sqrt(2 * (X + C1 + C2) / d)
	cc = sqrt(aa ** 2 + bb ** 2)
	h = B1 / (2 * A1)
	k = B2 / (2 * A2)
	xp = aa ** 2 / cc
	yp = bb ** 2 / cc
	v = xp + yp - h - k
	w = int(v)
	if w != v:
		while w != 0:
			Ax = b / 2 + d / 2
			Bx = a - b / 2 - d * w - c + d / 2
			Cx = d * w * w / 2 + (c - d / 2) * w - X
			px1 = (-Bx + sqrt(Bx ** 2 - 4 * Ax * Cx)) / (2 * Ax)
			px2 = (-Bx - sqrt(Bx ** 2 - 4 * Ax * Cx)) / (2 * Ax)
			py1 = w - px1
			py2 = w - px2
			if (py1 >= 0 or py2 >= 0) and (px1 >= 0 or px2 >= 0) and (int(px1) != int(px2) or int(py1) != int(py2)):
				break
			w = w - 1
	ans = w
	print(ans)
	a = (a + ans * T) % M + P
	b = (b + ans * T) % M + Q
	c = (c + ans * T) % M + R
	d = (d + ans * T) % M + S


from sys import stdin
from math import sqrt, floor
inp = stdin.readline

def buy(x, a, b, c, d):
	money = x
	count1 = max(floor((sqrt(max(a ** 2 * b * d + a ** 2 * d ** 2 - b ** 3 * d + b ** 2 * c ** 2 + 2 * b ** 2 * d ** 2 + 2 * b ** 2 * d * x + b * c ** 2 * d - b * d ** 3 + 2 * b * d ** 2 * x, 0)) - a * b - a * d + b ** 2 - b * d) / (b * (b + d))), 0)
	count2 = max(floor((sqrt(max(a ** 2 * b * d + a ** 2 * d ** 2 - b ** 3 * d + b ** 2 * c ** 2 + 2 * b ** 2 * d ** 2 + 2 * b ** 2 * d * x + b * c ** 2 * d - b * d ** 3 + 2 * b * d ** 2 * x, 0)) - b * c - b * d - c * d + d ** 2) / (d * (b + d))), 0)
	money -= a * count1 + b * count1 * (count1 - 1) / 2
	money -= c * count2 + d * count2 * (count2 - 1) / 2
	if money < 0:
		while money < 0:
			do = x
			count1 = max(count1 - 1, 0)
			count2 = max(count2 - 1, 0)
			do -= a * count1 + b * count1 * (count1 - 1) / 2
			do -= c * count2 + d * count2 * (count2 - 1) / 2
			money = do
	while money >= 0:
		if a + count1 * b <= c + count2 * d:
			count1 += 1
			money -= a + (count1 - 1) * b
		else:
			count2 += 1
			money -= c + (count2 - 1) * d
	return count1 + count2 - 1
i = int(inp())
(x, a, b, c, d) = map(int, inp().split())
(p, q, r, s, t, m) = map(int, inp().split())
for j in range(i):
	ans = buy(x, a, b, c, d)
	print(ans)
	if j != i:
		a = (a + ans * t) % m + p
		b = (b + ans * t) % m + q
		c = (c + ans * t) % m + r
		d = (d + ans * t) % m + s


I = int(input())
(x, a, b, c, d) = map(int, input().split())
(p, q, r, s, t, m) = map(int, input().split())

def cost_vaccine(a, b, i):
	return a * i + b * i * (i - 1) / 2
for _ in range(I):
	k = (2 * (a - c) + (d - b)) / (2 * d)
	a1 = b ** 2 / d + b
	a2 = 2 * a + 2 * b * c / d - 2 * b + 2 * k * b
	a3 = d * k ** 2 + 2 * k * c - k * d - 2 * x
	i = (-a2 + (a2 ** 2 - 4 * a1 * a3) ** 0.5) / (2 * a1)
	j = k + b / d * i
	i = max(int(i), 0)
	j = max(int(j), 0)
	cost_i = cost_vaccine(a, b, i)
	cost_j = cost_vaccine(c, d, j)
	while cost_i > x and i > 0:
		i -= 1
		cost_i = cost_vaccine(a, b, i)
	while cost_j > x and j > 0:
		j -= 1
		cost_j = cost_vaccine(c, d, j)
	cost_i = cost_vaccine(a, b, i)
	cost_j = cost_vaccine(c, d, j)
	money_left = x - cost_i - cost_j
	while min(a + i * b, c + j * d) <= money_left:
		money_left -= min(a + i * b, c + j * d)
		if a + i * b < c + j * d:
			i += 1
		elif c + j * d < a + i * b:
			j += 1
		elif d < b:
			j += 1
		else:
			i += 1
	ans = i + j
	print(ans)
	a = (a + ans * t) % m + p
	b = (b + ans * t) % m + q
	c = (c + ans * t) % m + r
	d = (d + ans * t) % m + s