Any better algorithm possible here?
- by Cupidvogel
I am trying to solve this problem in Python. Noting that only the first kiss requires the alternation, any kiss that is not a part of the chain due to the first kiss can very well have a hug on the 2nd next person, this is the code I have come up with. This is just a simple mathematical calculation, no looping, no iteration, nothing. But still I am getting a timed-out message. Any means to optimize it?
import psyco
psyco.full()
testcase = int(raw_input())
for i in xrange(0,testcase):
n = int(raw_input())
if n%2:
m = n/2;
ans = 2 + 4*(2**m-1);
ans = ans%1000000007;
print ans
else:
m = n/2 - 1
ans = 2 + 2**(n/2) + 4*(2**m-1);
ans = ans%1000000007
print ans
