SPOJ.com - Problem ADAROBOT

ADAROBOT - Ada and CAPTCHA

#sorting #dynamic-programming #sweep

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))³ + 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 ≤ 10⁶ , number of queries.

The next Q lines contains an even integer: 2 ≤ N ≤ 2*10⁸

Output

For each query, print T(N)

Example Input

Example Output

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

Submit solution!

hide comments

< Previous 1 2 3 Next >

	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 EDIT: I did it without fast i/o Last edit: 2017-05-04 22:51:58
	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 :'( Have nice day
	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: A) The solution have lesser time - what you see is the summation of times for each test-file B) O(N) per test-case is not enough Good Luck!
	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: Firstly: It "runs" so it is not getting in cycle anywhere - it is "just slow" (and I guess it is not "very slow" - just a bit slower) Secondly: I can say that slowest part of algorithm is this line "k=((ll)log2(k)) + 1;" Even thought it is not intended nor optimal solution, it shall pass with a few optimizations :) Good Luck ~/Morass
	KD : 2017-03-28 13:15:18 @morass can you Plzzzz check my solution .getting TLE ...... @morass Thanks for help..... Learn a lot about optimization AC :) after so many TLE's....... for loop giving TLE and while loop is getting accepted -_- (Seriously)...... fast I/O is required....... Last edit: 2017-03-28 17:10:10
	morass: 2017-03-28 12:24:13 @raj_rajvir: Hello Consider following examples: 2: 10 (least significant bit on position 2, so 2 is returned) 3: 11 (least significant bit on position 1, so 1 is returned) 4: 100 (least significant bit on position 3, so 3 is returned) 5: 101 (least significant bit on position 1, so 1 is returned) 6: 110 (least significant bit on position 2, so 2 is returned) Good Luck ~/Morass

Submit solution!

Added by:	Morass
Date:	2017-03-14
Time limit:	0.800s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All