SPOJ.com - Problem SHAKTI

SHAKTI - SHAKTIMAN AND KILWISH

Since very long time shaktiman and kilwish have been fighting with each other but the fight never came to end . So finally I came to rescue . I decided that the result of the fight will be decided by a mathematical game, in which I will write a number (N) . Kilwish and shaktiman will play the game alternatively and each of them would subtract a number(n) [n is less than N] such that N modulo n gives zero. The game is repeted turn by turn until the one, who now cannot make a further move looses the game

Shaktiman being weak at mathematics asks you for help, whether or not he can win in that particular case. If Shaktimaan wins that game then print "Thankyou Shaktiman" otherwise print "Sorry Shaktiman".The game begins with shaktimaan playing first move.It is well understood that both of them will make moves in optimal way.

INPUT

Input contains test cases t (< 10^5) and followed by t numbers (1 <= N <= 10^6 ).

OUTPUT

If Shaktimaan wins that game then print "Thankyou Shaktiman" otherwise print "Sorry Shaktiman".

Sample Input:
2
212
424

Sample Output:
Thankyou Shaktiman
Thankyou Shaktiman

Submit solution!

Added by:	aqfaridi
Date:	2014-01-24
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64

hide comments

2017-03-18 13:59:53
Think Simple. No Game Theory, No factorization :D

2017-03-03 18:37:25
I implemented fast, sive-based factorization and generation of all divisors, DP and got AC in 0.12; then I looked at the top times and printed out the winner for 1..1000; now I feel dumb :-p.

HINT: An odd number will never have even divisors, while every number has 1 as a divisor.

Last edit: 2017-03-03 18:39:39

2016-12-30 07:09:29
always remember your endl's xD

2016-10-17 09:18:33
even /odd problem.. :)

2016-09-22 19:12:07
lol

2016-08-20 20:44:08
easiest on spoj !!!! XD

2016-06-14 00:13:04
Easy One Ac in 1st Go... :D

2016-03-06 05:50:41
think a solution with bitwise operator:-) ac in one go

2016-01-28 20:11:54
easy one,think u will get.my 22 nd :)

2015-12-22 18:17:01
//PLEASE READ ONLY IF YOU DIDN'T UNDERSTAND THE PROBLEM. WARNING- SPOILER!//

case N=212.
shaktiman plays first. he chooses 'n' and subtracts it from 212. we shall assume he begins with 1. now N=211.
Kilwish subtracts 1 again, now N=210.
this goes on until N=1, after which subtraction from N is impossible(remember, n<N).
So the one who reaches N=1 first wins.

sample-
if N=6
move 1: N=5 (By Shakti)
move 2: N=4(By Kilwish)
move 3: N=3 (By Shakti)
move 4: N=2(By Kilwish)
move 5: N=1 (By Shakti)

Shaktiman reached N=1 first. So he wins.

Work out another sample and you'll crack the logic :)