I have solved the following problem using dynamic programming: Little Deepu and his Girlfriend 1. To paraphrase,
We have two players Little Deepu and Kate and M items in the bag B, also we have a game set S with N elements, each element of game set is an integer. The game is played as follows, each player takes turn to pick an element from the game set S and removes that number of items from the bag, the player that is unable to remove the items from the bag looses the game. Little Deepu start the game ,If both Little Deepu and Kate play the game optimally, your task is to determine who wins the game.
Input: First line contains a integer T , number of test cases. Each test case contain two lines , first line contain two integer M and N and second line contain elements of S.
Output: For each test case print name of the winner of the game .
Though correct, my solution is exceeding time limit for large inputs. Please tell me where I am going wrong.
def winner(n_i, n_t, t_k): output = [False]*(n_i + 1) for j in t_k: output[j ] = True print(output) for i in range(1, n_i + 1): if not output[j]: for j in t_k: if j > i: continue val = output[i - j] if not val: output[i] = True break return 'Little Deepu' if output[n_i] else 'Kate' num_test = int(input()) for i in range(num_test): num_items,num_take_outs = map(int, input().split()) take_outs = list(map(int, input().split())) print(winner(num_items, num_take_outs, take_outs))