Level Generation (Codeforces 818F)
Tags: Math, ternary search

Ivan is developing his own computer game. Now he tries to create some levels for his game. But firstly for each level he needs to draw a graph representing the structure of the level.Ivan decided that there should be exactly ni vertices in the graph representing level i, and the edges have to be bidirectional. When constructing the graph, Ivan is interested in special edges called bridges. An edge between two vertices u and v is called a bridge if this edge belongs to every path between u and v (and these vertices will belong to different connected components if we delete this edge). For each level Ivan wants to construct a graph where at least half of the edges are bridges. He also wants to maximize the number of edges in each constructed graph.So the task Ivan gave you is: given q numbers n1, n2, ..., nq, for each i tell the maximum number of edges in a graph with ni vertices, if at least half of the edges are bridges. Note that the graphs cannot contain multiple edges or self-loops.

Input: The first line of input file contains a positive integer q (1 ≤ q ≤ 100 000) — the number of graphs Ivan needs to construct.Then q lines follow, i-th line contains one positive integer ni (1 ≤ ni ≤ 2·109) — the number of vertices in i-th graph.Note that in hacks you have to use q = 1.

Output: Output q numbers, i-th of them must be equal to the maximum number of edges in i-th graph.

Note: In the first example it is possible to construct these graphs:  1 - 2, 1 - 3;  1 - 2, 1 - 3, 2 - 4;  1 - 2, 1 - 3, 2 - 3, 1 - 4, 2 - 5, 3 - 6. 

Sample Inputs:
3
3
4
6

Sample Outputs:
2
3
6

Solution (Python):
import math

def solve():
    q = int(input())
    for _ in range(q):
        n = int(input())
        x = int((-1 + math.sqrt(1 + 8 * n)) // 2)
        if n - x - 1 < x * (x - 1) // 2 + 1:
            print(n - x + x * (x - 1) // 2)
        else:
            print(2 * (n - x - 1))
if __name__ == '__main__':
    solve()

Solution (Python):
def newest_approach(n):
    from math import floor, ceil, sqrt
    quad_solv = sqrt(2 * n + 1 / 4) - 1 / 2
    x = floor(quad_solv)
    y = ceil(quad_solv)
    xed = int(x * (x - 1) / 2 + n - x)
    xbr = n - x
    ybr = n - y
    yed = 2 * ybr
    if xed > yed:
        print(xed)
    else:
        print(yed)
    return

def main():
    import sys
    data = [line.rstrip() for line in sys.stdin.readlines()]
    num_graphs = data[0]
    graph_sizes = [int(x) for x in data[1:]]
    for val in graph_sizes:
        newest_approach(val)
if __name__ == '__main__':
    main()

Solution (Python):
from math import floor, ceil, sqrt

def solve(n):
    quad = sqrt(2 * n + 1 / 4) - 1 / 2
    x = floor(quad)
    y = ceil(quad)
    a = int(x * (x - 1) / 2 + n - x)
    b = n - x
    c = n - y
    d = 2 * c
    if a > d:
        print(a)
    else:
        print(d)
    return
n = int(input())
for i in range(n):
    solve(int(input()))