MCOINS - Coins Game


Asen and Boyan are playing the following game. They choose two different positive integers K and L, and start the game with a tower of N coins. Asen always plays first, Boyan – second, after that – Asen again, then Boyan, and so on. The boy in turn can take 1, K or L coins from the tower. The winner is the boy, who takes the last coin (or coins). After a long, long playing, Asen realizes that there are cases in which he could win, no matter how Boyan plays. And in all other cases Boyan being careful can win, no matter how Asen plays.

So, before the start of the game Asen is eager to know what game case they have. Write a program coins which help Asen to predict the game result for given K, L and N.

INPUT

The input describes m games.

The first line of the standard input contains the integers K, L and m, 1 < K < L < 10, 3 < m < 50. The second line contains m integers N1, N2, …, Nm, 1 ≤ Ni ≤ 1 000 000, i = 1, 2, …., m, representing the number of coins in each of the m towers

SAMPLE INPUT
2 3 5
3 12 113 25714 88888

OUTPUT

The standard output contains a string of length m composed of letters A and B. If Asen wins the ith game (no matter how the opponent plays), the ith letter of the string has to be A. When Boyan wins the ith game (no matter how Asen plays), the ith letter of the string has to be B.

SAMPLE OUTPUT
ABAAB

Problem for kid - Please, think like kid.


hide comments
manishjoshi394: 2018-11-25 06:56:44

If you can't figure out what to do, try reading Topcoder tutorial on 'Algorithm games'. Here is the link, https://www.topcoder.com/community/competitive-programming/tutorials/algorithm-games/

manishjoshi394: 2018-11-25 06:55:46

Even my memoization solution passed easily in first go. If you are getting RTE with Memoization, check if you are handling function calls with negative and zero values.

masterchef2209: 2018-10-13 11:17:59

good one
but i suck at dp...

jmr99: 2018-10-04 19:56:54

AC!!.
what you have to do is just check the places i-1, i-k, i-l for loosing player(B) .if from these places after moving 1 or L or K (means now at i ) moves player A manages reach given coins[m].. then this is the scenario where player A will win . and base case is when there is no coin then B will always win bcz there is no way player A will make move .

slinky: 2018-07-08 16:50:02

for somebody stuck on case 10, if no. of coins are less than l, you can only pick 1 or k coins and if coins less than k only 1 coin.

ameyanator: 2018-02-03 17:03:29

Initially I got a WA on test case 10. Couldn't find what's wrong with my code so looked through the comments. Seems like no one had a problem with test case 10 :/. Coded the same logic that I had again a bit more clearer this time and AC! :)

dunjen_master: 2017-12-28 21:03:57

so weak in dp that solving this problem gave me pleasure...btw think that you can win only if u bring the other player in a situation from where he looses

chetan4060: 2017-12-20 18:11:21

make a table up to some numbers and see repetitions
and make dp:)

lazyfellow: 2017-10-16 06:18:04

ac in one go!
Don't miss the base case

rohit9934: 2017-09-04 08:57:12

beginner dp+game theory. For a given set {1,L,K}, A will win anyway at 1,L,K and loses at K+1.If at any point n>K, if A can jump to any losing position then n is the winning position or vice versa.
Another test case
2 3 11
0 1 2 3 4 5 6 7 8 9 10
Output
BAAABAAABAA


Added by:~!(*(@*!@^&
Date:2009-02-17
Time limit:0.216s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:BOI For Kid 08