QUEST OF DIVISORS
All submissions for this problem are available.
Sagar has decided to challenge Shivam, he gives him an array of N integers and both of them have to perform a Task one by one.
Task given by Sagar is that a player has to choose any 2 numbers from the given array ai and aj (i!=j) such that ai * aj has exactly 3 positive divisors and delete those 2 elements from the array.
Both the players play alternatively. If there are no possible moves then player who played last move wins.
As the game is made by Sagar he has an advantage of playing first .
Sagar realizes that this game will take too much time, he wants to know who will win if both the players play optimally.
Since, you are a good programmer, Sagar asks for your help to determine the winner of the game.
PS : If at the start of the game, no player is able to make a move , Shivam wins .
- The first line of the input contains an integer T denoting the number of Matches played by Sagar and Shivam . The description of T matches follow :
- The first line of each Match contains a single integer N denoting the size of Array given by Sagar.
- The second line of each Match contains N space-separated integers Ai, denoting the i th element of Array.
- If Sagar wins the Match print “Sagar”.
- If Shivam wins the Match print “Shivam” (without quotes).
- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 10000
- 1 ≤ Ai ≤ 1000000
For each Match, output a single line containing the Name of Winner.
3 4 3 6 7
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions