Chat Ban (Codeforces 1612C)
Tags: Math, binary search

You are a usual chat user on the most famous streaming platform. Of course, there are some moments when you just want to chill and spam something.More precisely, you want to spam the emote triangle of size $$$k$$$. It consists of $$$2k-1$$$ messages. The first message consists of one emote, the second one — of two emotes, ..., the $$$k$$$-th one — of $$$k$$$ emotes, the $$$k+1$$$-th one — of $$$k-1$$$ emotes, ..., and the last one — of one emote.For example, the emote triangle for $$$k=3$$$ consists of $$$5$$$ messages:  Of course, most of the channels have auto moderation. Auto moderator of the current chat will ban you right after you spam at least $$$x$$$ emotes in succession (you can assume you are the only user in the chat). Now you are interested — how many messages will you write before getting banned? Or maybe you will not get banned at all (i.e. will write all $$$2k-1$$$ messages and complete your emote triangle successfully)? Note that if you get banned as a result of writing a message, this message is also counted.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The next $$$t$$$ lines describe test cases.The only line of the test case contains integers $$$k$$$ and $$$x$$$ ($$$1 \le k \le 10^9; 1 \le x \le 10^{18}$$$).

Output: For each test case, print the number of messages you will write before getting banned for the corresponding values $$$k$$$ and $$$x$$$.

Note: Let's analyze the test cases of the example.  In the first test case, you write three messages containing $$$1$$$, $$$2$$$ and $$$3$$$ emotes respectively, and since $$$1 + 2 + 3 \ge 6$$$, you get banned after that.  In the second test case, you write four messages containing $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$ emotes respectively, and since $$$1 + 2 + 3 + 4 \ge 7$$$, you get banned after that.  In the third test case, you write one message containing exactly $$$1$$$ emote. It doesn't get you banned, since $$$1 < 2$$$, but you have already finished posting your emote triangle. So you wrote one message successfully.  In the fourth test case, you write four messages containing $$$1$$$, $$$2$$$, $$$3$$$ and $$$2$$$ emotes respectively, and since $$$1 + 2 + 3 + 2 \ge 7$$$, you get banned after that.  In the fifth test case, you write three messages containing $$$1$$$, $$$2$$$ and $$$1$$$ emote respectively. It doesn't get you banned, since $$$1 + 2 + 1 < 5$$$, but you have already finished posting your emote triangle. So you wrote three messages successfully.  In the sixth test case, since $$$x = 1$$$, you get banned as soon as you send your first message.  The seventh test case is too large to analyze, so we'll skip it. 

Sample Inputs:
7
4 6
4 7
1 2
3 7
2 5
100 1
1000000000 923456789987654321

Sample Outputs:
3
4
1
4
3
1
1608737403

Solution (Python):
from math import isqrt, sqrt, ceil
for _ in range(int(input())):
    (a, b) = map(int, input().split())
    if b >= a * a:
        print(2 * a - 1)
        continue
    if b <= a * (a + 1) // 2:
        a = isqrt(2 * b)
        if 2 * b <= a * (a + 1):
            print(a)
        else:
            print(a + 1)
    else:
        b -= a * (a + 1) // 2
        exp = ceil((2 * a - 1 - sqrt((2 * a - 1) ** 2 - 8 * b)) / 2)
        print(a + exp)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
    (K, X) = map(int, input().split())
    a = K * (K + 1) // 2
    if X <= a:
        b = int((2 * X) ** 0.5)
        ans = b
        if b * (b + 1) < X * 2:
            ans += 1
        print(ans)
    elif X >= a + a - K:
        print(K + K - 1)
    else:
        X = a + a - K - X
        b = int((2 * X) ** 0.5)
        ans = K + K - 1 - b
        if b * (b + 1) > 2 * X:
            ans += 1
        print(ans)

Solution (Python):
import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        to = f(*args, **kwargs)
        if stack:
            return to
        else:
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        return to
                    to = stack[-1].send(to)
    return wrappedfunc

class Graphs:

    def __init__(self):
        self.graph = graphDict(set)

    def add_edge(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs_utility(self, nodes, visited_nodes, colors, parity, level):
        global count
        if nodes == 1:
            colors[nodes] = -1
        elif len(self.graph[nodes]) == 1 and parity % 2 == 0:
            if q == 1:
                colors[nodes] = 1
            else:
                colors[nodes] = -1
                count += 1
        elif parity % 2 == 0:
            colors[nodes] = -1
        else:
            colors[nodes] = 1
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            new_level = level + 1
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes, colors, level - 1, new_level)

    def dfs(self, node):
        Visited = set()
        color = collections.defaultdict()
        self.dfs_utility(node, Visited, color, 0, 0)
        return color

    def bfs(self, node, f_node):
        count = float('inf')
        visited = set()
        level = 0
        if node not in visited:
            queue.append([node, level])
            visited.add(node)
        flag = 0
        while queue:
            parent = queue.popleft()
            if parent[0] == f_node:
                flag = 1
                count = min(count, parent[1])
            level = parent[1] + 1
            for item in self.graph[parent[0]]:
                if item not in visited:
                    queue.append([item, level])
                    visited.add(item)
        return count if flag else -1
        return False

class Tree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder(node, lis):
    if node:
        inorder(node.left, lis)
        lis.append(node.data)
        inorder(node.right, lis)
    return lis

def leaf_node_sum(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return root.data
    return leaf_node_sum(root.left) + leaf_node_sum(root.right)

def hight(root):
    if root is None:
        return -1
    if root.left is None and root.right is None:
        return 0
    return max(hight(root.left), hight(root.right)) + 1

class UF:
    """"""

    def __init__(self, N):
        """"""
        self._id = list(range(N))
        self._count = N
        self._rank = [0] * N

    def find(self, p):
        """"""
        id = self._id
        while p != id[p]:
            p = id[p]
        return p

    def count(self):
        """"""
        return self._count

    def connected(self, p, q):
        """"""
        return self.find(p) == self.find(q)

    def union(self, p, q):
        """"""
        id = self._id
        rank = self._rank
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        self._count -= 1
        if rank[i] < rank[j]:
            id[i] = j
        elif rank[i] > rank[j]:
            id[j] = i
        else:
            id[j] = i
            rank[i] += 1

    def add_roads(self):
        return set(self._id)

    def __str__(self):
        """"""
        return ' '.join([str(x) for x in self._id])

    def __repr__(self):
        """"""
        return 'UF(' + str(self) + ')'

def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def p_sum(array):
    return list(itertools.accumulate(array))

def base_change(nn, bb):
    if nn == 0:
        return [0]
    digits = []
    while nn:
        digits.append(int(nn % bb))
        nn //= bb
    return digits[::-1]

def diophantine(a: int, b: int, c: int):
    (d, x, y) = extended_gcd(a, b)
    r = c // d
    return (r * x, r * y)

@bootstrap
def extended_gcd(a: int, b: int):
    if b == 0:
        (d, x, y) = (a, 1, 0)
    else:
        (d, p, q) = (yield extended_gcd(b, a % b))
        x = q
        y = p - q * (a // b)
    yield (d, x, y)
''
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

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

def map_inp(v_type):
    return map(v_type, inp().split())

def list_inp(v_type):
    return list(map_inp(v_type))
for _ in range(int(inp())):
    (k, x) = map_inp(int)
    temp = int((2 * x) ** 0.5)
    if temp * (temp + 1) // 2 < x:
        temp += 1
    if temp <= k:
        print(temp)
    else:
        del temp
        x -= k * (k + 1) // 2
        temp = (k - 1) * k // 2
        temp -= x
        if temp <= 0:
            print(2 * k - 1)
        else:
            l = temp
            temp = int((2 * temp) ** 0.5)
            if temp * (temp + 1) // 2 > l:
                temp -= 1
            print(k + (k - 1 - temp))