http://www.spoj.com/problems/MUSKET/ hello everyone,there is a nice problem from polish olympiad,i have tried to solve it but ... can someone explain how solve it? or if have some ideas share it each other. sorry for my bad english.
http://www.spoj.com/problems/MUSKET/ hello everyone,there is a nice problem from polish olympiad,i have tried to solve it but ... can someone explain how solve it? or if have some ideas share it each other. sorry for my bad english.
| # | User | Rating |
|---|---|---|
| 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 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
To solve this problem you have to use dynamic programming to answer the question if ith and jth musketeer can be the last two fighters in the tournament. Then you just check which one wins this kind of duel and add the winner to the output. You can also have some fun simulating the tournament for x times, this kind of solution was given around 70% of points on the POI. If you have some more doubts, ask.
can't understand ;|
You can check out my AC code: http://ideone.com/nzAuoP. Sorry for formatting it is really old :(.