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

hide comments
suraj: 2016-06-14 19:19:43

can't get O(1) solution,help me

top_gun007: 2016-06-12 07:38:34

collatz conjecture-all u need to know

vineetpratik: 2016-06-11 19:06:13

dont use float or double it gives WA , in some testcases. can't figure out why
sol in O(1)

amankumarjha: 2016-05-21 18:31:17

It is a slight modified form of collatz conjecture, but this problem illustrates that how a slight modification can solve a problem so easily.

chen9069: 2016-01-29 17:42:46

O(1) solution, check if n <= 1 || n & (n-1) == 0

Bijoy Rahman Arif: 2016-01-19 19:10:43

WC: O(log2(n)) : this is the best solution I guess.

nightwolf_9197: 2015-12-22 21:23:49

same algo in pyth 2.7 got AC but got RE in c++

jasbir_220b2: 2015-12-22 07:57:30

easy one....

hmp: 2015-12-11 08:14:48

simply use vector....insert all changing n...check if n repeats or not

sri: 2015-11-13 10:54:30

ac with O(logn)


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