Borjianamin's blog

By Borjianamin, history, 5 weeks ago, In English,

I need help to solve a problem. I couldn't solve this problem.
The problem description:
Memory: 256MB
Time limit: 2 seconds
Jack and Harry play a game. There is n stones on ground. in each turn, each of them can pick 1 to 6 stone(s) from ground. there is some rules:
1) first player can't pick 3 or 6 stones 2) if Jack picks x stone(s), then Harry picks y stone(s), x + y % 3 must not be zero
3) if Harry picks x stone(s), then Jack picks y stone(s), x + y % 3 must not be zero
4) always Jack start game if someone couldn't pick any stone (because there is no more stone or there is no more legal move), he will lose. if both of them, play well, who will win?!
in input, n is given.
Input: 8
Output: Jack
Input: 5
Output: Jack
Input: 6
Output: Jack
Input: 7
Output: Harry

I couldn't solve this problem. I saw same problem long ago and I couldn't solve it. Can someone give me a way for solving problem which say two or more than two player, plays well?! I don't know what is idea of this kind of problem? Is it only a relation and I have to write for example until n = 20 and find a relation?!
Is it possible to help me?
I'm sorry for bad English.

  • Vote: I like it  
  • -5
  • Vote: I do not like it  

5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

This is very confusing. Can you provide the exact wording? For example, when n=6, I would expect that Jack would win — He would pick 5 stones, then Harry can't pick anything up at all!

I'm general, if you wanted to solve this for yourself, I would think that it would be a nim variant after the first player's first move.

  • »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    first one:
    Jack pick 1 stone -> 7 remaining stone
    Harry pick x -> 7 — x remaining stone (Harry can only pick 1, 3, 4, 6)
    Jack can pick remaining stone and some of them is 7 so there is no limit.
    Jack win game.

    second one:
    Jack pick 5 stone and win

    I edit something. If there is no more stone, player will lost. If player can't do any legal move, he will lost.

  • »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I fix input and output too. I'm sorry.