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.
|
|
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.
|
|
[Lakshman]:
2021-05-29 11:42:50
what is the limit on the number of a?
|
|
nadstratosfer:
2021-05-29 04:32:47
Enjoyed!
|
Added by: | pierre |
Date: | 2021-05-26 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |