SEQ7 - Yet Another Sequence Problem

no tags 

We have an infinite non-decreasing sequence A which is created as follows:

  • A[1] = 1 and A[2] = 2.
  • A number i occurs A[i] times in the sequence.

First few terms in the sequence are: { 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7... }. Note that 3 occurs 2 times in the sequence, (because A[3] = 2).

Your task is to find the term A[n] for any given n, where 0 < n <= 1e13.

Input

First line contains t, the number of test cases. Each of the next t lines contains a number n.

Output

For every case, print the nth term of the sequence.

Example

Input:
2
5
12

Output:
3
6

hide comments
Soma: 2015-06-24 03:17:12

@sivanatarajan : write a brute force program in python and cross check with your output(from one which implements your algorithm).

sivanatarajan: 2014-10-21 19:08:57

anyone tell some more test cases..

Pranjal Successena: 2013-04-22 21:28:21

can u chk my code?
I jst don't know y its gving "run time error"..
91440088

(Tjandra Satria Gunawan)(曾毅昆): 2013-01-05 12:30:38

what is this? just use approximation and got AC in 0.00s (without fast I/O) I haven't optimize my code, but seems that my algo is fastest compared to other ;-) plus I only use 1,7MB of memory...

sandeep pandey: 2012-03-16 08:40:45

Binary Search will be okay :|

Last edit: 2012-09-18 17:53:56
Ashish Sahay: 2011-12-18 11:04:42

is the answer for 1e13-130097223???

:D: 2011-06-23 11:51:09

No, basic arithmetic's is enough.

uevoliinilas: 2011-05-12 10:55:02

Is this same as http://acm.mipt.ru/judge/problems.pl?problem=047&CGISESSID=12027e31a8c0844fbf3fadfa731bbb29
or here we have to use any advanced matrix exponentiation ?

Piotr KÄ…kol: 2011-05-10 11:46:27

Is the answer for 1e13 - 130097224?

Edit : No.

Last edit: 2011-05-10 12:23:01
Gabriel: 2011-05-09 18:44:54

My Python code gets the correct answer for n up to 10^13 (I checked it with Mathematica), but still I'm getting wrong answer here...

Edit: Did you try with a brute force checker ? The formula you are using has an error term associated with it.

Last edit: 2011-05-10 05:04:55

Added by:Paranoid Android
Date:2011-05-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64