Wesley's Anger Contest 1 Problem 1 - Simply a Simple Simplex Problem

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem types

Wesley is taking a course on the network simplex algorithm. Unfortunately, a term that comes up often in class is simple graph. When the professor asked him what the minimum number of vertices a simple, undirected graph with $M$ $M$ edges can have, he was unable to answer. Please help Wesley with this very simple task!

A graph is simple if it contains no self loops (an edge from a vertex to itself) and no multiple edges between any two vertices. Note that an edge between vertices $u$ $u$ and $v$ $v$ is the same as an edge between $v$ $v$ and $u$ $u$ .

Since solving this problem once is easy, you will be asked to solve it $T$ $T$ times!

Constraints

For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

Subtask	Points	$T, M$ $T, M$
$1$ $1$	$10\%$ $10 %$	$1 \le T \le 10$ $1 \leq T \leq 10$ $1 \le M \le 10$ $1 \leq M \leq 10$
$2$ $2$	$40\%$ $40 %$	$1 \le T \le 1\,000$ $1 \leq T \leq 1 000$ $1 \le M \le 1\,000$ $1 \leq M \leq 1 000$
$3$ $3$	$50\%$ $50 %$	$1 \le T \le 1\,000$ $1 \leq T \leq 1 000$ $1 \le M \le 10^{18}$ $1 \leq M \leq 10^{18}$

Input Specification

There will be multiple test cases.

The first line contains a single integer $T$ $T$ , the number of test cases.

Each test case consists of a single integer $M$ $M$ on its own line, the number of edges in the graph.

Note that a 64-bit integer may need to be used to store $M$ $M$ . In C++, this can be done with long long. In Java, this can be done with long. In Python, the standard int will suffice.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

For each test case, output a single integer on its own line, the minimum number of vertices a simple, undirected graph with $M$ $M$ edges can have.

Sample Input

Copy

2
1
4

Sample Output

Copy

2
4

Sample Explanation

One possible graph for the first test case is shown below.

$\text{[math]}$

One possible graph for the second test case is shown below.

$\text{[math]}$

Comments

0

iNeedOnions commented on April 28, 2024, 6:56 a.m.

Did you figure out how to fix it? I am having the same problem

7

Togohogo1 commented on Dec. 3, 2019, 2:18 a.m. ← edited →

I don't understand how print(int(math.ceil((1+(math.sqrt(1+8*x)))/2))) is wrong. I keep on getting WA for Batch 4 Case 5.

7

skyflaren commented on Dec. 3, 2019, 2:47 a.m.

there's some rounding inaccuracies, ~~found that out the hard way XD (sorry)~~

try finding a way around using decimals