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
vas14:
2020-01-16 02:51:56
Identical code that implements O(N) with fast I/O using getchar_unlocked():
|
|
nadstratosfer:
2019-01-19 10:31:35
I got 4.00s simply following the tags; appreciate psetter for guidance as this approach is far more elegant than bruting it with 1.5GB mem usage. That being said, a better solution exists, also input is massive so *everything* that goes on in your program matters. Thanks to Morass for designing problems that provide multiple layers of fun =) |
|
dominikwis:
2018-11-03 21:02:57
Hi, I solved the problem in c++ with fast io and barely got the solution in time limit.
|
|
kshubham02:
2018-07-04 12:17:52
@Morass O(N+Q) with fast IO is giving TLE... Can you please check it.. submission id is 21939386 Last edit: 2018-07-04 14:11:29 |
|
s_a_k_s_h_a_m:
2018-06-07 09:15:18
you can use 10^8 as dp array size , declare it global
|
|
totallynotan:
2018-04-17 17:44:28
Again, :( O(N + QlogQ) doesn't pass under java even with fast I/O. Is switching to another language the only fix? |
|
morass:
2017-08-19 02:47:54
@hodobox: Oh i see ^_^ Thanx! |
|
hodobox:
2017-08-15 14:53:50
@morass: You added T(1) = 1, it should be T(1) = 0 :) |
|
morass:
2017-07-16 16:53:05
@hodobox: Thank you, updated it .. ^_^ |
|
hodobox:
2017-07-16 13:48:57
Hm, I think it could be mentioned that T(1) = 0. As far as I can tell you can't find it from the definition as it would require knowing T(-1). |
Added by: | Morass |
Date: | 2017-03-14 |
Time limit: | 0.800s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |