Сложность: medium
В мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire".
Пример:
Input: senate = "RD"
Output: "Radiant"
👨💻 Алгоритм:
1⃣Инициализируйте две очереди для хранения индексов сенаторов от партий Radiant и Dire.
2⃣Выполните цикл, пока обе очереди не станут пустыми: Сравните индексы первых сенаторов из обеих очередей. Удалите сенатора с меньшим индексом из очереди и добавьте его с индексом, увеличенным на длину строки. Удалите сенатора с большим индексом из очереди.
3⃣Если одна из очередей опустела, объявите победу партии, чья очередь еще содержит сенаторов.
😎 Решение:
from collections import deque
def predictPartyVictory(senate):
radiant = deque()
dire = deque()
for i, s in enumerate(senate):
if s == 'R':
radiant.append(i)
else:
dire.append(i)
while radiant and dire:
r = radiant.popleft()
d = dire.popleft()
if r < d:
radiant.append(r + len(senate))
else:
dire.append(d + len(senate))
return "Radiant" if radiant else "Dire"
Ставь 👍 и забирай 📚 Базу знаний