1196. Экзамен по истории

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

Вход. Первая строка содержит количество дат n (1 £ n £ 15000) в списке учителя. Следующие n строк содержат сами даты. Каждый год не более 10⁹. Даты отсортированы в возрастающем порядке. Следующая строка содержит число дат ученика m (1 £ m £ 100000), за которой следуют m строк с самими датами. Список дат ученика не отсортирован.

Выход. Вывести количество баллов, которое наберет ученик.

Пример входа

2

1054

1492

4

1492

65536

1492

100

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

2

РЕШЕНИЕ

бинарный поиск

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

Список дат учителя храним в отсортированном массиве mas. Подсчитываем количество дат ученика, присутствующих в массиве mas.

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

В массиве mas храним даты учителя.

int mas[15001];

Вводим даты учителя в массив mas. Каждую дату ученика number ищем в массиве mas, используя функцию бинарного поиска binary_search. В переменной res подсчитываем число дат ученика, присутствующих в списке учителя.

scanf("%d",&n);

for(i=0;i<n;i++) scanf("%d",&mas[i]);

scanf("%d",&m);

res = 0;

while(m--)

{

scanf("%d",&number);

if (binary_search(mas,mas+n,number)) res++;

}

printf("%d\n",res);