https://codeforces.net/contest/456/problem/D "Fedor wants to know who wins the game if both players will play optimally" They play optiomally each game, or maybe one of them deliberately lose to win the final game ? Thanks very much.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/05/2024 08:45:28 (k3).
Desktop version, switch to mobile version.
Supported by
In each game, they will either compete to win or compete to lose depending on what's favorable. So first compute who will succeed in both cases. This can be done putting all the strings in a trie and then using DP to determine the results at each state (node in the trie).
Now there are four cases for results while competing to win and competing to lose
In case 1, First wins (he has complete control of all games)
In case 2, Second wins (he has complete control of all games)
In case 3, Second wins (he always wins and becomes second player in the next match and repeats..)
In case 4, the result depends on k being odd or even.
See this for implementation.
Here you don't need the dp, as a node, is being visited only one time, not multiple times in each
funcall.