#ЛитКод
Задача:
649. Dota2 SenateВ мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire".
Пример:Input: senate = "RD"
Output: "Radiant"
👨💻
Алгоритм:1⃣Инициализируйте две очереди для хранения индексов сенаторов от партий Radiant и Dire.
2⃣Выполните цикл, пока обе очереди не станут пустыми: Сравните индексы первых сенаторов из обеих очередей. Удалите сенатора с меньшим индексом из очереди и добавьте его с индексом, увеличенным на длину строки. Удалите сенатора с большим индексом из очереди.
3⃣Если одна из очередей опустела, объявите победу партии, чья очередь еще содержит сенаторов.
😎
Решение:
fun predictPartyVictory(senate: String): String {
val radiant = ArrayDeque<Int>()
val dire = ArrayDeque<Int>()
for (i in senate.indices) {
if (senate[i] == 'R') {
radiant.add(i)
} else {
dire.add(i)
}
}
while (radiant.isNotEmpty() && dire.isNotEmpty()) {
val r = radiant.removeFirst()
val d = dire.removeFirst()
if (r < d) {
radiant.add(r + senate.length)
} else {
dire.add(d + senate.length)
}
}
return if (radiant.isEmpty()) "Dire" else "Radiant"
}👉
Новости 👉
Платформа
