ADAGAME - Ada and Game

Ada the Ladybug is playing Game of Digits against her friend Velvet Mite Vinit. The game is played in following manner: At first, there is a four-digit number and a number of moves. Both Ada and Vinit take turns alternately (beginning with Ada). Both of them must increase ANY digit of the number, but if the digit was 9 it will become 0.

For example number 3590 can be expanded to: 4590,3690,3500 or 3591. If after all turns the number is greater than the original number, Ada wins - otherwise Vinit is the winner. Both of them play optimaly - can you decide who is the winner?

PS: It is possible, that Ada will have one more turn (if number of turns is odd)


First line of input will consist T ≤ 200 number of test-cases. Each testcase will consist of four digit number 0 ≤ N < 104 [the original number] and 0 ≤ M ≤ 100 [the number of turns].


For each test-case, print the name of winner ("Ada" or "Vinit").

Example Input

0000 0
5566 3
3333 10
9999 9
1234 30

Example Output


hide comments
tojra: 2020-11-07 06:33:55

@morass, help me, I am getting WA at test 8. I tried some test cases you mentioned in comments but still WA

Last edit: 2020-11-07 06:35:22
nadstratosfer: 2020-04-27 19:43:16

I've never been to any algorithms course, but when I can't make the TL of 4.5s while the top times are under 0.10s, I tend to consider studying redundancy or bugs in my code. Morass' problems often feature large inputs that make every stupidity in the program stand out and every optimization yield tangible improvement; this prolongs the fun way past getting the AC, for those that find fun in efficient coding. Anyway, speed of printf vs cin is a moot point here as the I/O is < 2KB in worst case.

rising_stark: 2020-04-27 01:43:05

This has been an utter shameful thing on this judge here that cin and cout are TLE while printf and scanf are AC.
Also, I used a c++ STLs pow() function to convert a given string say "4669" to its next iteration since I didn't know manipulation with strings but that was giving TLE everytime. I wasted 1 day thinking that dp states were not being returned properly and it is going exponential.
It has been a disappointment that such petty extra times are also creating problems in-spite of when we are always taught and stressed about only asymptotic complexities in each and every algorithms course that exists on earth.
Well @morass, in that case would you also state any bitwise algorithm's problem here to be O(32n) or only O(n).

Last edit: 2020-04-27 01:43:57
sandeepd: 2019-12-15 06:05:48

Very nice problem. It's important to attempt these types of problems (2-player optimisation kind).

haiderbaig: 2019-09-04 17:59:57

seemed impossible at first glance but then i took out a paper and a pencil and doodled a little.
DP is all about reducing a problem to sub-problems

ankityadav: 2019-07-01 06:58:30

just take care of cases when ada won and ada lose
2-d dp is enough
and take care of even odd turns

senseichrollon: 2019-04-10 00:17:12

Can someone give me a hint on approaching this? For example, is it better to solve this top-down, or bottom up?

Last edit: 2019-04-10 00:23:49
clarkfric_200: 2019-03-06 22:28:54

DP problems are so simple , yet so beautiful .

zurister: 2018-10-02 13:19:10

@morass can you provide me a testcase where my solution 22427308 fails?

code_aim: 2018-06-04 21:43:01

Can anyone provide me a test case as my code is failing at test case 8?

Added by:Morass
Time limit:4.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU