SPOJ.com - Problem WILLITST

WILLITST - Will it ever stop

#ad-hoc-1

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	imsrvstv: 2020-06-28 19:55:07 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: 2022-08-09 22:11:46
	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.
	shifalitayal: 2020-03-19 09:10:17 very easy...bit manipulation can also be used...

Submit solution!

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