олимпиада по информатике 5. Agar.io

Ограничение времени 1 секунда

Ограничение памяти 512Mb

Ввод стандартный ввод или input.txt

Вывод стандартный вывод или output.txt

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом поле одна.

В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат ввода

Программа получает на вход целое число n, 1≤ n≤ 105 — количество игроков. Следующие n строк содержат по одному числу ai — размеры бактерий, 1≤ ai≤ 109. Числа ai заданы в порядке неубывания.

Формат вывода

Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен ai) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Пример

Ввод Вывод

4

1

1

3

4

0

0

1

1

Примечания

В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. ответ: 0, 0, 1, 1.

|

Решение, правильно работающее только для случаев, когда n≤ 100 и все ai≤ 106, будет оцениваться в

Для решения данной задачи нам необходимо определить, какие игроки имеют возможность выиграть в игре Agar.io. Для этого мы должны проверить каждую бактерию на возможность съесть других игроков.

Для начала, давайте определимся с подходом к решению. Мы должны проверить каждую бактерию по порядку и определить, сможет ли она съесть других игроков. Для этого нам нужно знать, каким размером является каждая бактерия и их порядок.

Мы можем использовать следующий подход:

1. Получить количество игроков (n) и создать массив, чтобы хранить их размеры.

2. Считать размеры бактерий игроков и сохранить их в массив.

3. Создать еще один массив такого же размера, чтобы хранить флаги - победил игрок (1) или нет (0).

4. Пройти по всем бактериям (игрокам) в порядке возрастания и определить, сможет ли игрок победить.

5. Для каждой бактерии проверить, может ли она поглотить другую бактерию. Если размер текущей бактерии больше следующей, помечаем следующую бактерию как поглощенную, добавляем ее размер к текущей бактерии и устанавливаем флаг победы этого игрока.

6. Пройти по всем поглощенным игрокам и проверить, смогут ли они поглотить других игроков. Если поглощенный игрок имеет размер больше текущего игрока, он становится его частью, и флаг победы текущего игрока устанавливается.

7. После завершения всех итераций, вывести флаги каждого игрока в отдельные строки.

Теперь давайте перейдем к реализации этого подхода на языке программирования Python:

```python
# Шаг 1
n = int(input())
sizes = []

# Шаг 2
for _ in range(n):
sizes.append(int(input()))

# Шаг 3
flags = [0] * n

# Шаг 4
for i in range(n):
# Шаг 5
for j in range(i + 1, n):
if sizes[i] > sizes[j]:
sizes[i] += sizes[j]
flags[j] = 1

# Шаг 6
for j in range(i + 1, n):
if flags[j] == 1 and sizes[i] < sizes[j]:
sizes[i] += sizes[j]
flags[i] = 1

# Шаг 7
for flag in flags:
print(flag)
```

Теперь мы можем запустить нашу программу и получить ответ на задачу.

Примечание:
Это решение работает только для случаев, когда n ≤ 100 и все ai ≤ 10^6. Если условие задачи требует решения для больших значений n и ai, то нужно использовать оптимизированный подход или алгоритм.