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¹⁴.

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 >

	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*
	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...
	abhiaps: 2020-03-16 12:46:44 sooo simple
	nishabila: 2020-01-26 04:28:22 if n==1 then its NIE got a wrong answer for this
	abhijitburman: 2020-01-09 21:45:22 my first AC in one go. do not see comment box for this problem. just observe the problem and u will get the logic
	mrdevesh_00: 2019-12-20 09:19:55 use bitwise

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