Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Адаптивный поиск

Знаменитая компания Gold&Silver Soft решила занять ведущее место в области разработки реляционных баз данных. Руководство компании понимает, что для этого необходимо удивить потребителей быстродействием своего программного продукта.

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

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

Вашей задачей является написать программу, которая для каждого из M последовательно заданных поисковых запросов будет определять количество просмотренных записей при поиске заданной. Для простоты обозначения будем считать, что имеется таблица с N записями, где запись – это число от 1 до N.  В начале все записи в таблице расположены в порядке возрастания, то есть на i-м месте в таблице находится число i. Для приведенного ниже примера  при M = 2, N = 6 и запросах на поиск чисел  «5» и «3» потребуется 5 и 4 просмотра записей соответственно.


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

Первая строка входного файла содержит два целых числа N и (1 ≤ N, M ≤ 65535) — количество записей в таблице и количество запросов на поиск соответственно.  Числа разделены одиночным пробелом.

Вторая строка содержит M натуральных чисел Ai (1 ≤ AiN), разделенных одиночными пробелами, где Ai  — запрос на поиск числа Ai в таблице. Запросы на поиск выполняются последовательно в порядке их ввода.

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

Единственная строка выходного файла должна содержать M натуральных чисел, разделенных одиночными пробелами, i-е число – это количество просмотренных записей при поиске числа Ai.


Примеры:
input.txt output.txt
1 6 2
5 3
5 4
2 10 10
10 9 8 7 6 5 4 3 2 1
10 10 10 10 10 10 10 10 10 10
3 3 14
3 2 3 3 1 1 2 2 1 1 1 1 2 1
3 3 2 1 3 1 3 1 2 1 1 1 2 2

Сложность задачи: 50%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 21, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]