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<=10^14.

Output

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

Example

Input:
4

Output:
TAK

hide comments
crawler_123: 2020-08-04 14:22:48

Don't use __builtin_popcount here. I repeat don't use it.

imsrvstv: 2020-06-28 19:55:07

I have a tiny penis. Btw I got 4 wrong answers because I was printing "NIL" instead of "NIE" keep in mind to not do that mistake too.

Last edit: 2020-06-28 20:32:56
sarveshjain967: 2020-06-24 21:22:23

Barely took me 4 mins
Others: using map to check repeating digits
Me: if it doesn't stop in 150 loops, it will never stop

AC in one go

agrawaladitya: 2020-06-13 13:33:18

So I was printing "YAK" instead of "TAK" and it cost me 6 WAs.
Press F for me pls

amar_shukla1: 2020-05-12 18:33:53

Those people who have used map and are getting WA in 20th case:
Use unsigned long long instead of long long.

sakibmalik: 2020-05-12 08:13:55

__builtin_popcount(n) betrayed me

tatai_c012: 2020-05-11 13:06:01

it is very simple,all numbers which are power of 2 i.e. 4,8,16,64,32,...... will only come to an end as they all end at 1.
but other any number will never end. take 3 or 6 or 62 such numbers and u will find they never end.

Varun Goyal: 2020-04-25 10:21:45

Rather than following patterns, I think attempting to write proofs is a better technique to learn problem solving.

This proof is taken from user "meooow" on codechef:
https://discuss.codechef.com/t/problem-with-will-it-ever-stop-spoj-question/18320

The only step available to reduce a number is n->n/2 when n is even. Clearly if n = 2^k
then n is repeatedly halved by this step until it equals 1. However the other step is n->3*(n + 1)So if this step is carried out even once the new value is a multiple of 3. From there it can take either step but a it remains a multiple of 3. Thus it can never reach the form 2^k, which means it will never reduce to 1.

Last edit: 2020-04-25 10:26:49
akash_arelli7: 2020-04-24 19:06:31


Last edit: 2020-04-24 19:06:46
roshansalian: 2020-04-13 16:59:28

The constraint is a joke. Normal long long works.


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