29491번 - Войны планет 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 13 | 9 | 6 | 60.000% |
문제
Все большую и большую популярность набирает игра <<Войны планет>>. Правила игры предельно просты. На плоскости расположены $n$ планет, каждая из которых характеризуется координатами своего место положения $x_i$, $y_i$ и скоростью производства космических кораблей $s_i$. В игру играют два игрока. Изначально каждый игрок имеет в своем распоряжении одну планету, а все остальные планеты в начале игры являются нейтральными. Также на каждой планете в начале находится некоторое число кораблей $p_i$. На нейтральных планетах --- это нейтральные войска, а на планетах игроков --- это войска соответствующих игроков.
Игра состоит из раундов. В начале каждого раунда на планетах, не являющихся нейтральными, появляются дополнительные $s_i$ кораблей. Корабли мгновенно оказываются в распоряжении игрока, владеющего соответствующей планетой.
После этого игроки начинают пересылать войска с планеты на планету, при этом игрок может посылать корабли только с планет, которые ему принадлежат, и только не больше кораблей, чем на этой планете есть. Если игрок пересылает корабли с планеты с координатами $(sx, sy)$ на планету с координатами $(dx, dy)$, то корабли прибывают к планете назначения после $\lceil \sqrt{(sx - dx)^2 + (sy-dy)^2)} \rceil$ раундов ($\lceil a\rceil$ означает минимальное целое число, не меньшее $a$).
Затем происходит прибытие войск на планеты.
В конце раунда, если на какой-то планете оказываются войска обоих игроков, то они вступают в бой. В результате сражения у каждого из игроков уничтожается $x = \min(p_1,p_2)$ кораблей, где $p_1$ --- число кораблей первого игрока на этой планете, а $p_2$ --- второго. После этого, если на планете остались войска игрока и нейтральные войска, то в бой вступают они, при этом бой происходит по тем же правилам.
После всех сражений, если на планете более нуля кораблей какого-то игрока, то он захватывает планету. Иначе владелец планеты остается неизменным. На этом раунд заканчивается.
Напишите программу, которая обрабатывала бы события игры, а также могла отвечать на запросы про $i$-ую планету, сколько на ней войск и кто ею владеет.
입력
В первой строке входного файла целое число $n$ ($2 \le n \le 100$) --- число планет. Далее следуют $n$ строк, по четыре целых числа $x$, $y$, $s$ и $p$ в каждой. Числа $x$ и $y$ ($|x|, |y| \le 20$) --- координаты соответствующей планеты, $s$ ($0 \le s \le 10$) --- скорость производства кораблей, $p$ ($0 \le p \le 100$) --- количество кораблей на планете в начале игры. В следующей строке следуют два целых числа --- номера планет первого и второго игроков. Планеты нумеруются с единицы в порядке появления во входном файле. Гарантируется, что координаты всех планет различны.
В следующей строке входного файла одно целое число $m$ ($0 \le m \le 1000$) --- количество событий и запросов, которые необходимо обработать. Каждый запрос занимает отдельную строку и начитается и с целого числа $t$, характеризующего тип события/запроса.
Если $t = 0$, то это означает конец раунда. Считается что все сражения происходят именно в момент конца раунда.
Если $t = 1$, то происходит пересылка войск. Тогда в строке далее идут три целых положительных числа $sp$, $dp$ и $ships$ --- номер планеты, с которой отправляются корабли, номер планеты, на которую отправляются корабли, и число отправляемых кораблей соответственно. Гарантируется, что на планете $sp$ будет не менее чем $ships$ кораблей, планета $sp$ не будет нейтральной и планеты $sp$ и $dp$ не совпадают.
Если $t = 2$, то далее идет целое число $planet$ --- номер планеты, о которой запрашивается информация.
출력
Для каждого запроса о планете выведите в отдельной строке ее владельца и количество войск на ней на момент запроса. Следуйте формату примера. Считается что все запросы происходят после производства кораблей и до прибытия войск на планеты.
예제 입력 1
3 0 0 1 100 1 0 10 10 2 0 0 100 1 3 26 1 1 2 60 1 3 2 50 2 1 2 2 2 3 0 2 1 2 2 2 3 0 2 1 2 2 2 3 1 1 2 1 2 1 2 2 2 3 0 0 2 1 2 2 2 3 1 3 2 31 0 0 2 2
예제 출력 1
Player1 41 Neutral 10 Player2 50 Player1 42 Neutral 10 Player2 50 Player1 43 Neutral 0 Player2 50 Player1 42 Neutral 0 Player2 50 Player1 44 Player1 11 Player2 50 Player2 20
노트
В примере войска, вылетающие в первом раунде, долетают до планеты $2$ только во конце второго раунда. При этом в конце второго дня на планете $2$ окажутся $10$ нейтральных кораблей, $60$ кораблей первого игрока и $50$ --- второго. После битвы кораблей игроков останутся $10$ нейтральных кораблей и $10$ кораблей первого игрока. После из сражения на планете $2$ не будет ни одного корабля и она останется нейтральной.
В третьем раунде первый игрок высылает один корабль на планету $2$, который в конце четвертого раунда ее захватывает.
В пятом раунде второй игрок посылает $31$ корабль на вторую планету, но когда они прибывают на планету $2$ на ней уже есть $31$ корабль первого игрока. Корабли полностью уничтожают друг друга, но планета остается под контролем первого игрока.