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
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | nor | 155 |
| 5 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 02.06.2024 05:19:24 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
Try and work through a few examples...
Maybe there are some ranges in which only one person wins
Go by powers of 9
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?
If p >= n i lost. Else if 9*p >= n then i win.
Am i correct?
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.