9704. Муравьи

 

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

Программа Чарльза работает следующим образом. Сначала он сканирует всю колонию, составляя список меток распознаваемых муравьев. Затем он присваивает новым муравьям свежие метки. Для этого программа просто выбирает первое натуральное число (то есть неотрицательное целое число), которое в настоящее время не присвоено ни одному муравью, и так далее.

Из-за некоторых сбоев в устройстве распознавания изображений и в программе в списке ввода иногда появляются отрицательные или очень большие числа. Программа Чарльза просто игнорирует их.

Ваша задача – заново реализовать часть программы Чарльза, которая находит новый тег для назначения новому муравью.

 

Вход. Состоит из следующих строк:

·        в первой строке: целое число n (0 ≤ n ≤ 106);

·        в следующих n строках: целые числа x1, ..., xn, по одному в строке. Каждое число xi содержит не более 100 цифр.

 

Выход. Выведите наименьшее  неотрицательное целое  число, не принадлежащее множеству {x1, ..., xn}.

 

Пример входа

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

5

1

-1

0

3

10

2

 

 

РЕШЕНИЕ

сортировка подсчетом

 

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

Поскольку всего имеется n ≤ 106 чисел, то ответом будет число, не большее 106. Объявим массив m длины 106 такой что m[i] будет содержать 1, если число i имеется во входной последовательности (m[i] = 0 иначе). Если входное число меньше 0 или больше 106, то его не рассматриваем.

После обработки входных данных (сортировки подсчетом) ищем наименьшее неотрицательное целое  число i, для которого m[i] = 0. Для этого перебираем значение i в пределах от 0 до 106.

 

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

Объявим константу MAX.

 

#define MAX 1000001

 

Читаем количество чисел n.

 

cin >> n;

 

Последовательно обрабатываем n чисел.

 

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

{

 

Читаем число. Оно может быть большим, поэтому читаем его в строку.

 

  cin >> s;

 

Если число имеет более 7 цифр, то оно больше 106 и его можно не рассматривать.

 

  if (s.size() > 7) continue;

 

Преобразовываем строку s в число x. Если оно меньше 0 или больше 106, то его не рассматриваем.

 

  x = stoi(s);

  if (x < 0 || x >= MAX) continue;

 

Отмечаем, что число x имеется среди входных чисел.

 

  m[x] = 1;

}

 

Ищем наименьшее неотрицательное целое число, которое не встречается среди входных чисел. Перебираем числа от 0 до 106.

 

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

 

Если число i отсутствует во входной последовательности, то выводим его.

 

  if (m[i] == 0)

  {

    cout << i << endl;

    break;

  }