023. Похожие массивы

(Время - 1 сек., память - 16 Мб)

Два массива называются похожими, если совпадают множества чисел, встречающихся в этих массивах.

Требуется написать программу, которая определит: похожи ли два заданных массива.

Входные данные

В первой строке входного файла input.txt записаны два числа M и N - длины массивов (1 ≤ M, N ≤ 16000). Во второй строке записаны M чисел – элементы первого массива. В третьей строке записаны N чисел – элементы второго массива. Числа в строках разделены пробелами, элементы массивов не превышают по абсолютной величине 32000.

Выходные данные

В единственную строку выходного файла output.txt нужно вывести 1, если массивы похожи и 0 иначе.

Примеры

input.txt

output.txt

1

4 3
1 2 3 2
1 2 3

1

2

2 3
1 2
2 3 1

0

Разбор

Отсортируем массивы по возрастанию. В нижеприведенной программе это сделано методом «пузырька». Для решения, удовлетворяющего поставленным в задаче временным ограничениям, требуется более быстрый метод, например, быстрая сортировка Хоара. Далее одновременно просматриваем отсортированные массивы и они не будут похожими в двух случаях: либо найдутся различные элементы, либо один из массивов останется не просмотренным.

Программа на Паскале

var

  m, n, i, j, s : integer;

  a, b : array [1..16000] of integer;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(m,n);

  for i:=1 to m do read(a[i]);

  for j:=1 to n do read(b[j]);

  for i:=1 to m-1 do

    for j:=1 to m-i do

      if a[j]>a[j+1] then begin s:=a[j]; a[j]:=a[j+1]; a[j+1]:=s end;

  for i:=1 to n-1 do

    for j:=1 to n-i do

      if b[j]>b[j+1] then begin s:=b[j]; b[j]:=b[j+1]; b[j+1]:=s end;

  i:=1; j:=1;

  while (i<=m) and (j<=n) and (a[i]=b[j]) do

  begin

    s:=a[i];

    while (i<=m) and (a[i]=s) do i:=i+1;

    while (j<=n) and (b[j]=s) do j:=j+1;

  end;

  if (i>m) and (j>n) then write(1) else write(0)

end.

Программа на С

 

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2008-2009 уч. год, 5-й тур

Тематика

Сортировка и последовательности

Примерная сложность

30%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=522

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 24.05.2012