10443. Karabakh villages
There are many villages in Karabakh. Some
villages have the same name. For instance, several villages are named “Abdurrahmanli”.
You are given a list of village names in Karabakh and need to respond to a
series of queries. Each query asks for the number of villages with a specific
name.
To simplify, the village names have been
replaced with numbers.
Input. The first line contains two numbers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 104) – the number of villages in Karabakh and
the number of queries respectively.
The second line contains n integers ai (0 ≤
ai ≤ 109) – the names of the villages. Each of the
following q lines contains one integer x (0 ≤
x ≤
109) – the name of the village for which
the count is to be determined.
Output. For each query, print the number of villages in
Karabakh with the given name on a separate line.
|
Sample
input |
Sample
output |
|
9 4 2 8 1 5 2 8 4 1 8 1 8 3 2 |
2 3 0 2 |
map data structure
Let’s consider the structure map<int, int> m, where m[x] contains the number of
villages with the name x. We’ll read the villages in Karabakh and
build the map m. Then, for each village x, we’ll print the number of
times m[x] occurs.
Algorithm realization
Declare the
data structure m.
map<int, int> m;
Read the input data. Store the villages of
Karabakh in the map m.
scanf("%d %d", &n,
&q);
for (i = 0; i < n; i++)
{
scanf("%d", &x);
m[x]++;
}
Process q queries. For each village x, print
the number of times m[x] occurs.
for (i = 0; i < q; i++)
{
scanf("%d", &x);
printf("%d\n", m[x]);
}
Python realization
Read the input data.
n, q = map(int, input().split())
lst = list(map(int, input().split()))
Declare the vocabulary m.
m = {}
Store the information about the villages of Karabakh in the vocabulary
m.
for x in lst:
if x in m:
m[x] += 1
else:
m[x] = 1
Process q queries. For each village x, print the number
of times m[x] occurs. If the village x is not found in the vocabulary,
print 0.
for _ in range(q):
x = int(input())
print(m.get(x, 0))