Hello everyone, I invented a task and now I can not solve it. Can anyone help please. The condition is very simple: Two people are playing a game. They have an array of numbers and they take the numbers from the array in some order. Each time the number is taken by the one whose sum of already selected is less. The winner is the one who, after all the numbers are chosen, will have more sum. Who will win and by how much.
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
До соревнования
Codeforces Round 977 (Div. 2, на основе COMPFEST 16 - Final Round)
22:36:45
Зарегистрироваться »
Codeforces Round 977 (Div. 2, на основе COMPFEST 16 - Final Round)
22:36:45
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 8 | ecnerwala | 3494 |
| 9 | Um_nik | 3396 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | -is-this-fft- | 162 |
| 3 | maomao90 | 159 |
| 3 | atcoder_official | 159 |
| 5 | cry | 158 |
| 5 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.10.2024 10:28:16 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Well the first thing that came to my mind is bitmasks. Let dp[Mask][Mask2] be the winner if only numbers that have 1 in Mask appear in array now and first player took numbers that have 1 in Mask2. It is O(3^n) because Mask2 is submask of Mask. But I think it is possible to solve it faster.
Well, Your account is old and you have just solved 4 problems, It's a little SUS that you're asking this problem with this account!
it's a little more sus that ur using an alt to comment this!
almost thought that sus got to LGM lol
Can you clarify what are the rules if both people have equal sum? Who gets to pick? Who starts the game is also a good question.
For instance if array is [1,2,3,4], and first person picks 3 (arbitrarily we choose first person to go first) then the second person chooses [1,2], we then have a tie where either person could choose 4. How do you resolve this tie?
In general, the cases when, with an equal amount, the move goes to the next player and when the player who has achieved equality continues the move are not very different, but for definiteness, let's say that the move goes to the next