missed to mention here, but my new DL finally arrived. The website was broken, and DMV offices were so crowded that they could not offer helpful information or assistance. My experience renewing my DL was terrible. Anyway, I got the new one and am relieved now.
To maximize the length of the result array, we can keep incrementing the difference between two elements. For example,
l = 10, r = 20
[10]
[10, 11], 11 - 10 = 1
[10, 11, 13], 13 - 11 = 2, meeting the requirement ai - a(i-1) < a(i+1) - ai for all 2 <= i < n.
[10, 11, 13, 16], 16 - 13 = 3
...This algorithm results in the longest array.
Because the differences between any two elements increase by 1, the
sum of the increases is 1/2 * n * (n + 1), where
n is the number of pairs of adjacent elements.
The problem is to find the largest n where the sum is
smaller or equals to r - l.
# 1/2 * n * (n - 1) <= r - l
# n (n + 1) <= 2(r - l), maximize n
def binary_search(n: int) -> int:
li: int = 0
ri: int = n
prev_mi: int = -1
while True:
mi = (li + ri) // 2
if mi == prev_mi:
return mi
val: int = mi * (mi + 1)
if val == n:
return mi
elif val < n:
li = mi
else:
ri = mi
prev_mi = mi
for _ in range(int(input())):
l, r = map(int, input().split())
n: int = binary_search(2 * (r - l))
print(n + 1)Codeforces Round 970 (Div. 3) Editorial
It seems my approach was correct. I was surprised that the problem can be solved as simple as
for _ in range(int(input())):
a, b = map(int, input().split())
i = 0
while a + i <= b:
a += i
i += 1
print(i)Yogurt 300 Rice 1400 Boba 500 Protein shake 200 Protein bar 200
Total 2600 kcal
MUST:
TODO: