ADAROBOT - Ada and CAPTCHA
Ada the Ladybug just got an innovative idea (which might be a rival of captcha): She made following function - F(a)=least significant 1-bit of a (indexed from 1). She also made following recursive function T(N) = F(N*(N-1))3 + T(N-2), where T(0) = 0, T(1) = 0.
Her idea is following- Instead of asking for captcha, she uses an opposite method: She gives you even N and you have to answer T(N) - if your answer is correct, then you are definitely a robot and you won't be let in.
As her good friend she asked you to program a checker for her.
Input
The input begins with an integer 1 ≤ Q ≤ 106 , number of queries.
The next Q lines contains an even integer: 2 ≤ N ≤ 2*108
Output
For each query, print T(N)
Example Input
5 8 4 2 20 1000
Example Output
107 35 8 310 23988
Little explanation
F(2)=2 F(12)=3 F(30)=2 F(56)=4 F(90)=2 F(132)=3 F(182)=2 F(240)=5 F(306)=2 F(380)=3
hide comments
karthik_vg:
2017-07-06 18:27:31
learn about __builtin_ffsl easy one :P |
|
ks1999:
2017-05-03 11:52:58
Ok thanks man anyway
|
|
morass:
2017-05-02 23:34:15
@ks1999: No clue :/ Seems the first part runs in 0.1 (and is independent of input) and the second part is "constant" - so unless there's mistake then it must be "IO" ... anyway I know nothing about pascal so it is hard for me to decide - sorry :'(
|
|
ks1999:
2017-05-02 17:09:37
i did a fast io and i think i have linear time. Don't know why am i getting TLE. Last edit: 2017-05-02 18:45:54 |
|
morass:
2017-04-07 13:46:12
@sandip_coder:
|
|
sandip_coder:
2017-04-07 06:37:38
@morass why am i getting tle with O(n) solution as per test case? |
|
sandip_coder:
2017-04-06 20:59:30
@morass you have given time limit as 0.8s but most of the accepted code having time more than 0.8s...why?? |
|
morass:
2017-03-28 13:26:55
@KD:
|
|
KD :
2017-03-28 13:15:18
@morass can you Plzzzz check my solution .getting TLE ......
|
|
morass:
2017-03-28 12:24:13
@raj_rajvir: Hello
|
Added by: | Morass |
Date: | 2017-03-14 |
Time limit: | 0.800s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |