Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Пересечение множеств

(Время: 1 сек. Память: 64 Мб Сложность: 34%)

Эта задача сложна своими ограничениями. Самое ресурсоемкое, но простое решение, которое может прийти в голову - это считать данные в массивы, исключить из них повторяющиеся элементы, далее пробегая по одному из них смотреть: есть ли он во втором и если есть, то выводить в выходной файл. Здесь только исключение повторящихся элементов может при неэффективном решении иметь сложность O(n2), что для миллиона элементов может вызвать TLE (Time limit exceeded).

Рассмотрим теперь верное решение этой задачи. Здесь вовсе не нужны два массива, длина которых может быть до миллиона. В силу конечности диапазона возможных значений мы можем описать некоторый массив a[i] для i=0..105, в i-м значении будем хранить 0, если число i не содержится ни в одном из двух наборов чисел. Если число i имеется в первом наборе, то запишем туда 1, а если и в обоих наборах, то запишем туда 2. После чего пробегая по массиву нужно будет вывести все i, у которых a[i]=2. Заполнение массива a[i] происходит следующим образом: сначала все элементы обнуляются, далее при чтении элемента x первого набора можно выполнять присваивание a[x]=1. При просмотре элементов второго набора для каждого элемента y можно a[y]=2 только в том случае, когда a[y]=1.

Приведенный выше алгоритм можно формализовать к следующему виду:

int a[0..105]={0...0};

read(n,m);
for i=1..n{
  read(x);
  a[x]=1;
}
for i=1..m{
  read(y);
  if(a[y]==1) a[y]=2;
}
for i=0..105{
  if(a[i]==2) write(i,' ');
}

[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ