{"problem":{"name":"F. Level Generation","description":{"content":"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 th","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF818F"},"statements":[{"statement_type":"Markdown","content":"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.\n\nIvan decided that there should be exactly _n__i_ 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.\n\nSo the task Ivan gave you is: given _q_ numbers _n_1, _n_2, ..., _n__q_, for each _i_ tell the maximum number of edges in a graph with _n__i_ vertices, if at least half of the edges are _bridges_. **Note that the graphs cannot contain multiple edges or self-loops**.\n\n## Input\n\nThe first line of input file contains a positive integer _q_ (1 ≤ _q_ ≤ 100 000) — the number of graphs Ivan needs to construct.\n\nThen _q_ lines follow, _i_\\-th line contains one positive integer _n__i_ (1 ≤ _n__i_ ≤ 2·109) — the number of vertices in _i_\\-th graph.\n\n_Note that in hacks you have to use _q_ = 1._\n\n## Output\n\nOutput _q_ numbers, _i_\\-th of them must be equal to the maximum number of edges in _i_\\-th graph.\n\n[samples]\n\n## Note\n\nIn the first example it is possible to construct these graphs:\n\n1.  1 - 2, 1 - 3;\n2.  1 - 2, 1 - 3, 2 - 4;\n3.  1 - 2, 1 - 3, 2 - 3, 1 - 4, 2 - 5, 3 - 6.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Ivan 正在开发自己的电脑游戏。现在他试图为游戏创建一些关卡。但首先，他需要为每个关卡绘制一个表示关卡结构的图。\n\nIvan 决定，表示第 #cf_span[i] 个关卡的图中应恰好有 #cf_span[ni] 个顶点，且边必须是双向的。在构造图时，Ivan 对一种称为 _桥_ 的特殊边感兴趣。连接两个顶点 #cf_span[u] 和 #cf_span[v] 的边被称为 _桥_，当且仅当这条边属于 #cf_span[u] 和 #cf_span[v] 之间的每一条路径（如果我们删除这条边，这两个顶点将属于不同的连通分量）。对于每个关卡，Ivan 希望构造一个图，使得至少一半的边是 _桥_。他还希望最大化每个构造图中的边数。\n\n因此，Ivan 给你的任务是：给定 #cf_span[q] 个数 #cf_span[n1, n2, ..., nq]，对于每个 #cf_span[i]，求出在具有 #cf_span[ni] 个顶点的图中，满足至少一半的边是 _桥_ 的前提下，所能拥有的最大边数。*注意图中不能包含多重边或自环*。\n\n输入文件的第一行包含一个正整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100 000]) —— Ivan 需要构造的图的数量。\n\n接下来 #cf_span[q] 行，第 #cf_span[i] 行包含一个正整数 #cf_span[ni] (#cf_span[1 ≤ ni ≤ 2·109]) —— 第 #cf_span[i] 个图的顶点数。\n\n_注意：在 Hack 中，你必须使用 #cf_span[q = 1]_。\n\n输出 #cf_span[q] 个数，第 #cf_span[i] 个数必须等于第 #cf_span[i] 个图的最大边数。\n\n## Input\n\n输入文件的第一行包含一个正整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100 000]) —— Ivan 需要构造的图的数量。接下来 #cf_span[q] 行，第 #cf_span[i] 行包含一个正整数 #cf_span[ni] (#cf_span[1 ≤ ni ≤ 2·109]) —— 第 #cf_span[i] 个图的顶点数。_注意：在 Hack 中，你必须使用 #cf_span[q = 1]_。\n\n## Output\n\n输出 #cf_span[q] 个数，第 #cf_span[i] 个数必须等于第 #cf_span[i] 个图的最大边数。\n\n[samples]\n\n## Note\n\n在第一个例子中，可以构造以下图：  #cf_span[1 - 2], #cf_span[1 - 3];  #cf_span[1 - 2], #cf_span[1 - 3], #cf_span[2 - 4];  #cf_span[1 - 2], #cf_span[1 - 3], #cf_span[2 - 3], #cf_span[1 - 4], #cf_span[2 - 5], #cf_span[3 - 6].","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of graphs.  \nFor each $ i \\in \\{1, \\dots, q\\} $, let $ n_i \\in \\mathbb{Z}^+ $ be the number of vertices in graph $ i $.  \n\n**Constraints**  \n1. $ 1 \\le q \\le 100{,}000 $  \n2. $ 1 \\le n_i \\le 2 \\cdot 10^9 $ for all $ i \\in \\{1, \\dots, q\\} $  \n3. Graphs are simple (no self-loops, no multiple edges).  \n4. At least half of the edges must be bridges.  \n\n**Objective**  \nFor each $ n_i $, find the maximum number of edges $ e_i $ in a simple graph with $ n_i $ vertices such that at least half of the edges are bridges.  \n\nLet $ e_i $ be the total number of edges and $ b_i $ the number of bridges. Then:  \n$$\nb_i \\ge \\frac{e_i}{2}, \\quad \\text{and} \\quad e_i \\text{ is maximized}.\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF818F","tags":["binary search","math","ternary search"],"sample_group":[["3\n3\n4\n6","2\n3\n6"]],"created_at":"2026-03-03 11:00:39"}}