| Submit | All submissions | Best solutions | Back to list |
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
|
||||||||||||||
|
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. |
||||||||||||||
|
2020-05-12 08:13:55
__builtin_popcount(n) betrayed me |
||||||||||||||
|
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. |
||||||||||||||
|
2020-04-25 10:21:45 Varun Goyal
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 |
||||||||||||||
|
2020-04-13 16:59:28
The constraint is a joke. Normal long long works. |
||||||||||||||
|
2020-03-19 09:10:17
very easy...bit manipulation can also be used... |
||||||||||||||
|
2020-03-16 12:46:44
sooo simple |
||||||||||||||
|
2020-01-26 04:28:22
if n==1 then its NIE got a wrong answer for this |
||||||||||||||
|
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 |
||||||||||||||
|
2019-12-20 09:19:55
use bitwise |
||||||||||||||
RSS