Задание 26. Информатика. ЕГЭ. Шастин. 19.01.2025
- Просмотры: 232
- Изменено: 1 февраля 2025
(Л. Шастин, Д. Бахтиев) В волшебном мире гладиаторов начался крупнейший турнир силы и стратегии. Участие принимают \(n\) гладиаторов, каждый из которых обладает определённым уровнем начальной силы. Каждый гладиатор хочет проявить себя на арене, но при этом стремится укрепить своего союзника и, конечно же, устранить соперников. Каждый гладиатор должен выбрать четыре цели: первая — другой гладиатор, которого он считает своим союзником: его гладиатор будет усилять с помощью волшебного дубликата силы. Вторая, третья и четвёртая цели — враги, с которыми гладиатор хочет сразиться поочерёдно в указанном им порядке. Перед началом турнира гладиаторы тянули карточки с уникальными числами от \(1\) до \(n.\) Эти числа и определяют порядок, в котором гладиаторы будут делать свои ходы.
Порядок хода очередного гладиатора следующий: сначала осуществляется помощь союзнику, в случае, если союзник ещё жив: уровень силы союзника увеличивается на уровень силы гладиатора, делающего ход. Затем идёт фаза сражений: гладиатор бросает вызов своим трём соперникам из списка, по одному за раз. Важно отметить, что если соперник уже мёртв, сражение пропускается. В бою побеждает тот, у кого уровень силы больше: Победитель теряет треть своей силы (оставшаяся сила округляется вверх до ближайшего целого в случае дробного числа), а проигравший погибает. Если же силы сражающихся гладиаторов равны, гладиаторы пронзают друг друга лучами добра и погибают вместе, держась за руки. Погибшие гладиаторы свой ход осуществлять уже не будут. К концу турнира нужно определить: сколько гладиаторов выбыли с арены и какой наибольший уровень силы остался у выживших гладиаторов.
Входные данные
В первой строке подаётся натуральное число \(n\) — количество гладиаторов (не более \(10~000\)). Далее в \(n\) строках записаны шесть чисел: Первое — уникальный номер гладиатора в соответствии с вытянутой карточкой, второе — начальный уровень силы гладиатора, третье — номер гладиатора, который был выбран в качестве союзника, остальные три числа — номера противников, с которыми желает сразиться гладиатор.
Выходные данные
Выведите два числа: общее количество павших гладиаторов, а затем конечный уровень силы, которую имеет сильнейший из оставшихся в живых гладиаторов (или \(0,\) если все выбыли).
Пример входных данных:
\(5\)
\(3 \, 50 \, 2 \, 1 \, 4 \, 5\)
\(5 \, 40 \, 1 \, 2 \, 3 \, 4\)
\(1 \, 37 \, 3 \, 2 \, 4 \, 5\)
\(4 \, 25 \, 5 \, 3 \, 1 \, 2\)
\(2 \, 50 \, 1 \, 5 \, 4 \, 3\)
При таких исходных данных выживет только гладиатор под номером \(3\) и у него останется \(39\) силы на конец турнира.
Ответ: \(4 \,\, 39\)
Решение:
Python
from math import ceil
base = ''
fd = open(base + '26.txt')
N = int(fd.readline())
glad = {}
for line in fd:
m = list(map(int, line.split()))
glad[m[0]] = m[1:]
for i in range(1, N+1):
if glad[i][0]:
glad[glad[i][1]][0] += glad[i][0] if glad[glad[i][1]][0] else 0
for g in glad[i][2:]:
if glad[g][0]:
if glad[g][0] < glad[i][0]:
glad[g][0] = 0
glad[i][0] = ceil(2 * glad[i][0] / 3)
elif glad[g][0] > glad[i][0]:
glad[i][0] = 0
glad[g][0] = ceil(2 * glad[g][0] / 3)
break
else:
glad[i][0] = glad[g][0] = 0
break
q, mx = 0, 0
for i in range(1, N + 1):
if glad[i][0]:
mx = max(mx, glad[i][0])
else:
q += 1
print(q, mx)
Ответ: \(4228 \,\, 5962\)