Chy_Chy's blog

Asking for hint of Uva 847

By Chy_Chy, history, 5 years ago, In English

Is there anyone who can can help me on Uva 847. This is a problem of game theory.I have been stuck in this problem for a while. Thanks in advance. https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=788

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hint 1
Hint 2
Hint 3
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually the naive recursive "dp" works really fast even on the largest value of n. This is because there are less than $$$\log_2(n) \cdot \log_3(n) \cdot \dots \cdot \log_9(n) = 2164612996$$$ states. There are actually much less than this because the numbers 2-9 share many prime factors so this estimate overcounted many states. I got AC with it. Just try to answer the question: If the current number is p and it is my turn, do I win?

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

    If p >= n i lost. Else if 9*p >= n then i win.
    Am i correct?

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

      Maybe I should say try to write a formula for the function win(p) := does the current player win if the current number is p. The base case would be win(p) = false if p >= n. The answer would be win(1) ? P1 : P2.

      → Reply