WILLITST - Will it ever stop

When Bob was in library in University of Warsaw he saw on one of facades caption :"Will it ever stop?" and below some mysterious code:

while n > 1
  if n mod 2 = 0 then
    n := n / 2
  else
    n := 3 * n + 3

Help him finding it out !

Input

In first line one number n ≤ 1014.

Output

Print "TAK" if program will stop, otherwise print "NIE"

Example

Input:
4

Output:
TAK

Added by:Krzysztof Lewko
Date:2011-11-09
Time limit:0.906s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:AMPPZ 2011

hide comments
2017-01-29 17:42:45
No fancy things required, just try to find out pattern for few starting numbers using pen and paper
2016-12-27 14:54:26 ~~diva~~
no need of bit maipulation , just check if the number is becoming 3,6 or 12 at any time within the while loop .if yes, only then it's forming an infinite loop!

Last edit: 2016-12-27 15:07:49
2016-12-21 18:11:49
https://www.hackerearth.com/practice/notes/bit-manipulation/
wanna learn something new from this question go through above link :)
in o(1) time......ac
2016-12-20 14:41:20
easy problem,,just if condition and bit manipulation

Last edit: 2016-12-24 13:27:44
2016-12-19 17:02:38
use your pen :p
2016-12-09 07:53:15
AC in one go. Bits manipulation is the key. Although you can do it using log2 but try Bits Manipulation, you will learn something new. :)
2016-11-30 07:07:47
HINT: if n is a power of 2, it gets reduced to 1. and if n is not a power of 2, then if n is even, it becomes odd. Think what happens to odd integers and you'll get theta(1) solution :-)
2016-11-28 18:29:04
HINT : you may want to use double instead of float if using log2
2016-11-17 10:21:02
Donot use that log function. It will give you wa... find another way to get power of 2. umm... how about bit manipulation ;)
2016-11-03 18:01:28
ez as brainf##ck
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.