Submit | All submissions | Best solutions | Back to list |
VECTAR11 - Game of Squares |
Changu and Mangu are playing a game. They are given a number n. They make moves in turn, Changu playing first. Each move consists of subtracting a perfect square(not less than 1) from the number, the player who faces 0 loses. You are given a number n, you have to find out whether Changu can win the game, if both Changu and Mangu play optimally.
Input
The first line contains T (not more than 10^5), the number of test cases. The next T lines contain a number n (not more than 10^6).
Output
For each test case output "Win" if Changu can win the game, if he plays optimally or else print "Lose"
Example
Input: 3 1 2 3 Output: Win Lose Win
Added by: | Piyush Kumar |
Date: | 2016-07-12 |
Time limit: | 0.5s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
hide comments
|
|||||
2022-05-25 03:13:00 vas14
Misleading problem. There doesn't seem do be a better algo than O(n * sqrt(n)) with pre-computation, yet such solution won't work for the specified range of n. |
|||||
2019-12-14 20:06:53
Precomputation;) Using a break statement differs the time by 3.1s!! |
|||||
2017-08-01 19:54:07
Grundy number knowledge , came in handy :) |
|||||
2017-07-08 05:00:05
check my solution pls..id 19754600. can u give me some tricky case? thx before :) |
|||||
2016-08-20 17:45:03
AC in one go but a disastrous time of 1.52 seconds. Mixed Feelings. :/ |
|||||
2016-07-20 19:33:08
O(n*sqrt(n)) not passing ID 17323557 Re: You have to make some optimizations. Please consider pre computation and other ways to reduce operations. Thanks , forgot to enter the break condition Last edit: 2016-07-20 22:36:58 |
|||||
2016-07-17 22:06:53
N*sqrt(N) precomputation wont pass..?? Re: It should pass. @author : thanku. ..finally accepted..i think or operator was increasing the time..I might be wrong..is there any better approach for this question..? Last edit: 2016-07-18 15:51:14 |
|||||
2016-07-17 18:36:20
@author Please check my solution. Re: Your solution has WA even for very small test cases. Try them out on paper and check. Last edit: 2016-07-18 05:00:08 |
|||||
2016-07-17 01:40:34
Please check my solution. Re: Check for corner cases. Solution is correct. wano : got it. thanks :) Last edit: 2016-07-17 08:40:18 |
|||||
2016-07-14 17:42:24 Umesh Malhotra
Piyush please look at my solution. I am getting WA. |