Ntarsis' Set (Codeforces 1852A)
Tags: Math, number theory

Ntarsis has been given a set $$$S$$$, initially containing integers $$$1, 2, 3, \ldots, 10^{1000}$$$ in sorted order. Every day, he will remove the $$$a_1$$$-th, $$$a_2$$$-th, $$$\ldots$$$, $$$a_n$$$-th smallest numbers in $$$S$$$ simultaneously.What is the smallest element in $$$S$$$ after $$$k$$$ days?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.The first line of each test case consists of two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n,k \leq 2 \cdot 10^5$$$) — the length of $$$a$$$ and the number of days.The following line of each test case consists of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of array $$$a$$$.It is guaranteed that:   The sum of $$$n$$$ over all test cases won't exceed $$$2 \cdot 10^5$$$;  The sum of $$$k$$$ over all test cases won't exceed $$$2 \cdot 10^5$$$;  $$$a_1 < a_2 < \cdots < a_n$$$ for all test cases. 

Output: For each test case, print an integer that is the smallest element in $$$S$$$ after $$$k$$$ days.

Note: For the first test case, each day the $$$1$$$-st, $$$2$$$-nd, $$$4$$$-th, $$$5$$$-th, and $$$6$$$-th smallest elements need to be removed from $$$S$$$. So after the first day, $$$S$$$ will become $$$\require{cancel}$$$ $$$\{\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots\} = \{3, 7, 8, 9, \ldots\}$$$. The smallest element is $$$3$$$.For the second case, each day the $$$1$$$-st, $$$3$$$-rd, $$$5$$$-th, $$$6$$$-th and $$$7$$$-th smallest elements need to be removed from $$$S$$$. $$$S$$$ will be changed as follows: Day$$$S$$$ before$$$S$$$ after1$$$\{\cancel 1, 2, \cancel 3, 4, \cancel 5, \cancel 6, \cancel 7, 8, 9, 10, \ldots \}$$$$$$\to$$$$$$\{2, 4, 8, 9, 10, \ldots\}$$$2$$$\{\cancel 2, 4, \cancel 8, 9, \cancel{10}, \cancel{11}, \cancel{12}, 13, 14, 15, \ldots\}$$$$$$\to$$$$$$\{4, 9, 13, 14, 15, \ldots\}$$$3$$$\{\cancel 4, 9, \cancel{13}, 14, \cancel{15}, \cancel{16}, \cancel{17}, 18, 19, 20, \ldots\}$$$$$$\to$$$$$$\{9, 14, 18, 19, 20, \ldots\}$$$ The smallest element left after $$$k = 3$$$ days is $$$9$$$.

Sample Inputs:
7
5 1
1 2 4 5 6
5 3
1 3 5 6 7
4 1000
2 3 4 5
9 1434
1 4 7 9 12 15 17 18 20
10 4
1 3 5 7 9 11 13 15 17 19
10 6
1 4 7 10 13 16 19 22 25 28
10 150000
1 3 4 5 10 11 12 13 14 15

Sample Outputs:
3
9
1
12874
16
18
1499986

Solution (Python):
import sys

def solve():
    (n, k) = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    for i in range(n):
        a[i] -= i
    if a[0] != 1:
        print(1)
        return
    a.append(2000000000.0)
    ans = 1
    inc = 1
    while inc < n:
        days = (a[inc] - ans + inc - 1) // inc
        if days >= k:
            ans += k * inc
            k = 0
            break
        ans += days * inc
        k -= days
        while a[inc] <= ans:
            inc += 1
    ans += k * n
    print(ans)
t = int(sys.stdin.readline())
for _ in range(t):
    solve()

Solution (Python):
import sys
from os import path
from collections import deque

def get_int():
    return int(sys.stdin.readline())

def get_ints():
    return map(int, sys.stdin.readline().strip().split())

def get_string():
    return sys.stdin.readline().strip()
t = get_int()
fr = []
for _ in range(t):
    (n, k) = get_ints()
    a = list(get_ints())
    p = 1
    j = 1
    for i in range(k):
        while j <= n and a[j - 1] - j < p:
            j += 1
        p = p + j - 1
    fr.append(str(p))
for item in fr:
    sys.stdout.write(item)
    sys.stdout.write('\n')

Solution (Python):
import sys
from os import path
from collections import deque

def get_int():
    return int(sys.stdin.readline())

def get_ints():
    return map(int, sys.stdin.readline().strip().split())

def get_string():
    return sys.stdin.readline().strip()

def nxt(p):
    l = 0
    r = s
    while l != r:
        mid = (l + r) // 2
        if a[ends[mid] - 1] - ends[mid] >= p:
            r = mid
        else:
            l = mid + 1
    return p + ends[l] - 1 if l != s else p + n
t = get_int()
fr = []
for _ in range(t):
    (n, k) = get_ints()
    a = list(get_ints())
    ends = [1]
    for i in range(1, n):
        if a[i] != a[i - 1] + 1:
            ends.append(i + 1)
    s = len(ends)
    ans = 1
    for i in range(k):
        ans = nxt(ans)
    fr.append(str(ans))
for item in fr:
    sys.stdout.write(item)
    sys.stdout.write('\n')