| Submit | All submissions | Best solutions | Back to list |
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
| Added by: | Morass |
| Date: | 2017-03-14 |
| Time limit: | 0.800s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
||||||
|
2020-01-16 02:51:56 vas14
Identical code that implements O(N) with fast I/O using getchar_unlocked(): CPP 14 TLE C++ 4.3.2 WA C (Clang 8) Accepted |
||||||
|
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 =) |
||||||
|
2018-11-03 21:02:57
Hi, I solved the problem in c++ with fast io and barely got the solution in time limit. Can i maybe get a clue on improving my solution (or a push in the direction of other faster solution)? |
||||||
|
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 |
||||||
|
2018-06-07 09:15:18
you can use 10^8 as dp array size , declare it global faster i/o since n is even so n-1 is odd, f(n*(n-1))=f(n).use __builtin_ffsl use cube array to compute cubes an easy one |
||||||
|
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? |
||||||
|
2017-08-19 02:47:54
@hodobox: Oh i see ^_^ Thanx! |
||||||
|
2017-08-15 14:53:50
@morass: You added T(1) = 1, it should be T(1) = 0 :) |
||||||
|
2017-07-16 16:53:05
@hodobox: Thank you, updated it .. ^_^ |
||||||
|
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). |
||||||
RSS