ADAGAME4 - Ada and Game of Divisors
Ada the Ladybug is playing Game of Divisors against her friend Velvet Mite Vinit. The game has following rules. There is a pile of N stones between them. The player who's on move can pick at least 1 and at most σ(N) stones (where σ(N) stands for the number of positive divisors of N). Obviously, N changes after each move. The one who won't get any stones (N == 0) loses.
As Ada the Ladybug is a lady, so she moves first. Can you decide who will be the winner? Assume that both players play optimally.
Input
The first line of input will contain 1 ≤ T ≤ 105, the number of test-cases.
The next T lines will contain 1 ≤ N ≤ 2*107, the number of stones which are initially in pile.
Output
Output the name of winner, so either "Ada" or "Vinit".
Example Input
8 1 3 5 6 11 1000001 1000000 29
Example Output
Ada Vinit Ada Ada Vinit Vinit Ada Ada
hide comments
|
dictator97:
2017-12-18 17:27:25
how 29 gives vidit i dont get it can someone please help |
|
manya_cod4:
2017-12-16 06:05:28
@morass. Thanks. i was able to find the divisors in the much more efficient.
|
|
|
manya_cod4:
2017-12-15 14:17:59
Can someone provide with some good testCases? Thanks in advance.
|
|
morass:
2017-12-15 08:42:50
@manya_cod4: Good day to you. Imho it shall require better complexity. Even though some solutions might be slower, it could be done in linear time.
|
|
|
manya_cod4:
2017-12-15 07:57:15
Beside using DP, my algorithm need to find number of divisors for every number in the range 2 * 10000000 + 1, which takes sqrt(n) for each n. Therefore O(n) comes out to be O(n * sqrt(n)) which is giving me TLE. Can anybody confirm if this solution needs complexity lesser than that?
|
|
|
morass:
2017-12-14 02:36:17
@barishnamazov: positive |
|
barishnamazov:
2017-12-13 18:30:47
Is sigma(N) is count of *all* divisors of N or count of *positive* divisors of N? |
| Added by: | Morass |
| Date: | 2017-12-08 |
| Time limit: | 2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS