TRIMOD2 - The triangle of Pascal modulo 2


Consider Pascal’s triangle modulo 2. The first nine rows are given below:

        1 
       1 1 
      1 0 1 
     1 1 1 1 
    1 0 0 0 1 
   1 1 0 0 1 1 
  1 0 1 0 1 0 1 
 1 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 0 1 

Let F(n) be the number of 1 in the first n rows. So that F(0) = 0, F(1) = 1, F(2) = 3, etc.

Given a, find the smallest integer n such that F(n) ≥ a. Let N(a) denote this integer.

Input

A list of integers a1, ..., al, between 0 and 1018, one per line.

Output

The integers N(a1), ..., N(al), one per line.

Example

input:
0
1
4
15

output:
0
1
3
6

hide comments
pragma2: 2023-05-11 08:09:24

How do we know how many input there are?

Francky: 2021-06-08 11:55:28

You can also consider this problem : https://www.spoj.com/problems/DUKKAR2/

Simes: 2021-05-29 22:35:02

There must be a typo "A list of integers a1, ..., al, between 1 and 10^18, one per line." But the first integer in the example is 0.

[pierre: thanks, I fix it]

Last edit: 2021-05-30 08:49:07
wisfaq: 2021-05-29 21:26:04

Nice problem!

[Lakshman]: 2021-05-29 15:35:45

Not sure, why I am getting the wrong answer, can you give me a test case where my algorithm fails.

[pierre: 100. you're not far, keep trying!]

Last edit: 2021-05-29 17:02:41
[Lakshman]: 2021-05-29 11:42:50

what is the limit on the number of a?

[pierre: not much]

Last edit: 2021-05-29 17:02:09
nadstratosfer: 2021-05-29 04:32:47

Enjoyed!

<em>pierre: Thanks! You are my first solver on SPOJ</em>

Last edit: 2021-05-29 11:20:27

Added by:pierre
Date:2021-05-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All