Гра (Розбір)

Будемо моделювати гру за допомогою структури даних — множини (set). Множина буде зберігати всі числа, записані на папері.

Кожного разу, коли Фідан називає число, Фуад перевіряє, чи міститься воно в множині:

• якщо міститься — він видаляє це число з множини (стирає його з паперу);

• якщо не міститься — він додає число в множину (записує на папір).

Кількість чисел, що залишилися на папері до кінця гри, збігається з кількістю елементів у множині.

Приклад

Промоделюємо роботу множини для першого та другого прикладів.

В кінці гри:

• Перша множина містить $2$ елементи;

• Друга множина порожня (містить $0$ елементів);

Реалізація алгоритму

Читаємо кількість чисел $n$.

scanf("%d", &n);

Послідовно обробляємо $n$ чисел, названих Фіданом.

for (i = 0; i < n; i++)
{
  scanf("%d", &x);

Кожного разу, коли Фідан називає число $x$:

• Якщо числа $x$ немає у множині, додаємо його.

• Якщо число $x$ вже присутнє у множині, видаляємо його.

  if (s.find(x) == s.end())
    s.insert(x);
  else
    s.erase(x);
}

Виводимо відповідь — розмір множини $s$.

printf("%d\n", s.size());

Python реалізація

Читаємо вхідні дані.

n = int(input())
lst = map(int,input().split())

Оголошуємо множину.

s = set()

Послідовно обробляємо числа, названі Фіданом.

for x in lst:

Кожного разу, коли Фідан називає число $x$:

• Якщо число $x$ вже присутнє у множині, видаляємо його.

• Якщо числа $x$ немає у множині, додаємо його.

  if x in s:
    s.remove(x)
  else:
    s.add(x)

Виводимо відповідь — розмір множини $s$.

print(len(s))