10443. Карабахские села

 

В Карабахе есть много сел. Некоторые села имеют одинаковые названия. Например, можно встретить много сел под названием “Абдуррахманлы”. Вам дается список названий сел Карабаха и далее следует ответить на запросы. В каждом запросе дается название одного села. Определите количество сел в Карабахе с таким названием.

Для простоты названия сел были заменены на числа.

 

Вход. В первой строке заданы два числа n (1 ≤ n ≤ 105) и q (1 ≤ q ≤ 104) – соответственно количество сел в Карабахе и количество запросов.

Во второй строке заданы n целых чисел ai (0 ≤ ai ≤ 109) – названия сел. В каждой из последующих q строк дается одно целое число x (0 ≤ x ≤ 109) – название села, количество которых следует определить.

 

Выход. На каждый запрос в отдельной строке необходимо вывести одно число – количество сел в Карабахе с данным названием.

 

Пример входа

Пример выхода

9 4

2 8 1 5 2 8 4 1 8

1

8

3

2

2

3

0

2

 

 

РЕШЕНИЕ

cтруктуры данных map

 

Анализ алгоритма

Рассмотрим структуру map<int, int> m, где m[x] содержит количество сел с названием x. Прочитаем села в Карабахе, построим отображение m. Далее для каждого села x выведем число раз m[x], которое оно встречается.

 

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

Объявим структуру данных m.

 

map<int, int> m;

 

Читаем входные данные. Заносим села Карабаха в отображение m.

 

scanf("%d %d", &n, &q);

for (i = 0; i < n; i++)

{

  scanf("%d", &x);

  m[x]++;

}

 

Обрабатываем q запросов. Для каждого села x выведем число раз m[x], которое оно встречается.

 

for (i = 0; i < q; i++)

{

  scanf("%d", &x);

  printf("%d\n", m[x]);

}

 

Python реализация

Читаем входные данные.

 

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

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

 

Объявим словарь m.

 

m = {}

 

Заносим информацию о селах Карабаха в словарь m.

 

for x in lst:

  if x in m:

    m[x] += 1

  else:

    m[x] = 1

 

Обрабатываем q запросов. Для каждого села x выведем число раз m[x], которое оно встречается. Если село x не встречается в словаре, выводим 0.

 

for _ in range(q):

  x = int(input())

  print(m.get(x, 0))