acm.timus.ru №2002. Тестовое задание

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время: 0.5 секунды
Память 64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…
Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!
Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:
  1. «register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
  2. «login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
  3. «logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».
Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!
И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq n\leq 100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

Исходные данные Результат
6register vasya 12345

login vasya 1234

login vasya 12345

login anakin C-3PO

logout vasya

logout vasya

success: new user addedfail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Код

Данная программа представляет собой типичный пример использования таблицы символов, согласно терминологии Coursera. Для доступа к учетным записям используется интерфейс Map, а для реализации самой базы данных учетных записей — объект типа TreeMap. Учетная запись пользователей реализована в виде одного элемента типа Map.entry, где имя пользователя — это ключ, а атрибуты учетной записи — пароль и флаг подключен/отключен — реализованы в виде отдельной структуры AccountInfo, которая является значением этого ключа.

Время работы Выделено памяти
0.124 1 928 КБ
 Ссылка на Ideone: https://ideone.com/3Y2W4z

А1042

Условие:

В данной последовательности действительных чисел [latex]a_{1},…,a_{20}[/latex] выбрать возрастающую подпоследовательность наибольшей длинны.

Тесты:

Число элементов в заданной последовательности Заданная последовательность Найденная подпоследовательность
20 1 44 3 66 2 6 55 2 4 9 50 3 4 12 45 8 15 5 18 48 3 6 9 12 15 18
20 1 9 17 25 90 91 92 13 18 23 28 100 75 50 45 44 43 42 41 40 1 9 17 25
20 155 100 80 83 86 89 -60 -40 -20 0 20 40 60 33 33 33 0 0 0 0 -60 -40 -20 0 20 40 60

Код:

План

План программы:

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

  1. Находим все возможные приращения, как все возможные разности между входными значениями
  2. Выполняем цикл по всем входным значениям, для каждого входного значения пытаемся найти остальные значения, имеющие монотонно возрастающее приращение. Это выполняется для каждого найденного приращения. Для этого организуется вложенный цикл по всем приращениям. Он состоит из двух подциклов – движение влево от начального значения – ищем предыдущие члены последовательности с меньшим приращением, и движение вправо – ищем следующие значения последовательности с большим приращением
  3. Найденные последовательности сохраняем для последующего выбора самой длинной. Последовательности короче трёх элементов, а также с отрицательным приращением(т.е. убывающие) – игнорируем
  4. Выполняем слияние найденных последовательностей, если они покрывают друг – друга
  5. Находим последовательность наибольшей длины

Программа реализована с использованием шаблонных классов стандартной библиотеки vector и map. Vector используется для хранения всех используемых последовательностей, включая разности. Map используется, как временный объект для сортировки и слияния приращений, которые в ходе поиска встречаются с часто повторяющимися значениями.

Программа тестировалась с учётом случаев когда могут встречаться убывающие последовательности, которые должны игнорироваться.

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

Программа позволяет работать не только с фиксированными 20-ю числами. Длинна входной последовательности задаётся. Ввод содржит первым элементом длину последовательности, а затем следуют числа самой последовательности.

Ссылка на ideone.com :  http://ideone.com/kf13Zv

А709

Условие:

Дана квадратная матрица [latex]A[/latex], порядка [latex]m[/latex], натуральное число [latex]n[/latex], действительные числа  [latex]p_{n},p_{n-1},\ldots,p_{0}[/latex]. Получить матрицу [latex]p_{n}A^{n}+p_{n-1}A^{n-1}+\ldots p_{1}A+p_{0}E[/latex], где [latex]E[/latex]- единичная матрица порядка [latex]m[/latex].

Тесты:

Ввод количества p Ввод размерности матрицы А и одновременно Е
6 3

 

Ввод коэффициентов 5 4 3 2 1 0

Матрица А:

1 2 3
3 2 1
2 1 3

Результат:

544308 445319 692718
544281 445354 692710
544277 445315 692753

Код:

Программа базируется на классе Matrix. Этот класс необходим для представления алгоритма вычисления полинома в естественной математической форме. Класс реализует следующие операции:

  1. Создание матрицы заданного размера заполненной заданным числом
  2. Умножение матрицы на число
  3. Сложение матриц
  4. Произведение матриц
  5. Возведение матрицы в степень
  6. Вывод содержимого матрицы на консоль

Класс Matrix содержит 3 члена – число строк, колонок и двумерный массив, который создается на куче. Главный модуль содержит две вспомогательный функции для ввода данных.

Основная часть программы состоит из следующих этапов:

  1. Ввод данных: число итераций, размерности матрицы , списка коэфф. P и самой матрицы А
  2. Создание единичной матрицы Е и далее – начального значения суммы E*P_0
  3. Вывод исходных данных: E, A и P
  4. Цикл суммирования, где вычисляется i-й элемент суммы
  5. Вывод результата

Ссылка на ideone.com: http://ideone.com/ZWCf15

e-olimp 4847. Очередь с приоритетами

Условие: Реализуйте структуру «очередь с приоритетами», поддерживающую следующие операции:

  1. Добавление элемента в очередь.
  2. Удаление из очереди элемента с наибольшим приоритетом.
  3. Изменение приоритета для произвольного элемента, находящегося в очереди.

Тесты:

input data output data
add eight 8 <вывод не предусмотрен>
add three 3 <вывод не предусмотрен>
add eleven 11 <вывод не предусмотрен>
add one 1 <вывод не предусмотрен>
add five 5 <вывод не предусмотрен>
add neun 9 <вывод не предусмотрен>
add forteen 14 <вывод не предусмотрен>
add six 6 <вывод не предусмотрен>
add ten 10 <вывод не предусмотрен>
add twelve 12 <вывод не предусмотрен>
add fifteen 15 <вывод не предусмотрен>
add seven 7 <вывод не предусмотрен>
add thirteen 13 <вывод не предусмотрен>
change eleven 1100 <вывод не предусмотрен>
change eleven 1101 <вывод не предусмотрен>
change one 111 <вывод не предусмотрен>
pop eleven 1101
pop one 111
pop fifteen 15
pop forteen 14
pop thirteen 13
pop twelve 12
pop ten 10
pop neun 9
pop eight 8
pop seven 7
pop six 6
pop five 5
pop three 3
pop error

Код программы:

Компилировать под Gnu C++ 4.7.1

План программы:

При решении задачи учитывалась необходимость быстрого поиска по двум независимым параметрам — ид и приоритета.

Задача решалась в два этапа, сначала был написан вариант с упорядоченным списком, который позволял мгновенный pop, но add и change не удовлетворили тестам на скорость т.к. основывались на поиску путем перебора. Было приято решение использовать алгоритм поиска в двоичном дереве, учитывая, что условия задачи позволяли большой объем памяти.

 

Текущий вариант основывается шаблонном классе, реализующем двоичное дерево. Очередь содержит два объекта – дерево со строковыми ключами для хранения Id и дерево с числовыми ключами для хранения приоритетов. Каждый узел дерева Id указывает на узел дерева приоритетов. Это позволяет немедленно получить приоритет данного Id без поиска, что необходимо для операции change. В свою очередь, каждый узел дерева приоритетов указывает на узлы дерева Id с данным приоритетом. Это позволяет немедленно определить какой Id надо удалять при выполнении pop. Для обслуживания нескольких Id с равным приоритетом пришлось ввести еще один шаблонный класс – список.

 

Краткое описание операций

  • Add
    1. Находим или добавляем узел дерева Id (ситуацию если он есть игнорируем по условию задачи)
    2. Находим или добавляем узел дерева приоритетов
    3. Для узла дерева Id устанавливаем указатель на узел дерева приоритетов
    4. Для узла дерева приоритетов добавляем в его список узел дерева Id

 

  • Pop
    1. Находим узел дерева приоритетов с максимальным ключом
    2. Удаляем из списка найденного узла первый попавшийся указатель на узел дерева Id, если список
    3. Если список уже пуст, удаляем узел дерева приоритетов

 

  • Change
    1. Находим узел дерева Id (ситуацию если его нет игнорируем по условию задачи)
    2. Берем узел дерева приоритетов, на который указывает узел Id и удаляем из его списка этот узел Id (т.к. приоритет уже будет новый), если список оказался пуст, удаляем также узел приоритета
    3. Находим или добавляем узел дерева приоритетов с новым приоритетом и устанавливаем связь с узлом Id как в случае добавления.

 

Ссылка: http://ideone.com/FROADt

АА20

Условие: В заданной строке удалить последнюю пару символов «:=», которая найдется в строке.

Тесты:

Ввод Вывод
sdfsd  fdg :=sdrgs := :+:=:= sdf FUHIUh := sdfdf sdfsd  fdg :=sdrgs := :+:=:= sdf FUHIUh  sdfdf
фыпва :+вап:=аоап:=вр   := в фыпва :+вап:=аоап:=вр    в

 

Код программы:

Код программы на Java:

Ссылка на ideone.com: https://ideone.com/Z94AwR

План программы:

  1. Ввод строки из стандартного потока ввода. Здесь используется getline, чтобы можно было вводить символы-разделители
  2. Используется метод rfind класса string, позволяющий найти подстроку, начиная с конца
  3. Результат поиска — позиция символа, с которого начинается искомая построка
  4. Если позиция найдена, то используется метод replace, который заменяет все символы найденной подстроки на пустую строку

Ссылка на программу http://ideone.com/x5AtbG

А812б

Задача: Дан текст, каждый символ которого может быть малой буквой, цифрой или одним из знаков «+», «-«, «*». Группой букв будем называть такую совокупность последовательно расположенных букв, которой непосредственно не предшествует и за которой непосредственно не следует буква. Аналогично определим группу цифр и группу знаков.

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

Задача решена в двух вариантах — с использованием класса string и и с использованием массива символов, завершающихся нулём ( char[], null terminated string ).

Тесты ( для двух вариантов ):

тестовые данные количество посчитанных слов результат по условию задачи
1.  afsf1213**++  letterWordCount = 1
digitWordCount  = 1
symbolWordCount = 1
 в данном тексте одинаковое количество групп букв и групп знаков
2.  afsf1213**++asfs2434gfh21+++—dhf**++vg  letterWordCount = 5
digitWordCount  = 3
symbolWordCount = 3
 в данном тексте больше групп букв, чем групп знаков
3.  abcd+++—123efgh**++—123367++**-sdf—+754*+-bmwazs++834hello++—****  letterWordCount = 5
digitWordCount  = 4
symbolWordCount = 7
 в данном тексте групп букв меньше, чем групп знаков

Вариант 1: решение с использованием класса string

Код программы :

Код программы на Java:

Ссылка на ideone.com: http://ideone.com/MS3BKc

План программы:

  1. Объявление переменных — флаги и счетчики для всех видов слов
  2. Функция завершения чтения слова и увеличение счетчика слова на единицу
  3. Стандартный строковый объект класса string
  4. Ввод текст из стандартного потока ввода
  5. Проход по символам текста
  6. Анализ символов: к какой группе они относятся и проверка состояний
  7. Проверка принадлежности к данному типу символов ( +, — , * / цифра / буква )
  8. Финальное завершение текущего слова
  9. Вывод количества посчитанных слов
  10. Вычисление конечного результата

В программе используется переменная text типа string, которая позволяет хранить текст переменной длины. Переменная text заполняется символами из стандартного потока ввода. Подразумевается, что символ с значением «ноль» введён быть не может, по этому нулевой символ в конце текста является завершающим.

Цикл выполняется по всем символам string, вплоть до нулевого символа и анализирует принадлежность каждого символа к группе символов. Согласно условию задачи это — мал. буквы, цифры и символы + , — , * . В программе использованы 3 переменных-флага, описывающих текущие состояние чтение одного слова данной группы. Также есть переменные-счётчики для каждой группы слов. Каждый счётчик наращивается при сбрасывании флага, то есть, по завершении чтения группы.

Для проверки типа символа используются стандартные макросы isdigit и islower из библиотеки ctype .

Ссылка на ideone.com: http://ideone.com/fork/RiwQTO

Вариант 2: решене с использованием строки символов с завершающим нулём char[]

Код программы :

Код программы на Java:

Ссылка на ideone.com: http://ideone.com/uaQucV

План программы:

  1. Объявление символьного массива для загрузки текста
  2. Объявление переменных — флаги и счетчики для всех видов слов
  3. Функция завершения чтения слова и увеличение счетчика слова на единицу
  4. Загрузка текста в массив — цикл считывания одного символа текста
  5. Завершение нулевым символом
  6. Проход по символам текста загруженного в массив
  7. Анализ символов: к какой группе они относятся и проверка состояний
  8. Проверка принадлежности к данному типу символов ( +, — , * / цифра / буква )
  9. Финальное завершение текущего слова
  10. Вывод количества посчитанных слов
  11. Вычисление конечного результата

Программа читает непрерывный поток текстовых символов и загружает их в символьный массив text . По окончанию ввода добавляется нулевой символ, чтобы символьный массив выглядел, как строка, завершающаяся нулём (null terminated string). При вводе учитывается возможность появления мулевого символа, что также прекращает ввод.

Цикл выполняется по символьному массиву, вплоть до нулевого символа и анализирует принадлежность каждого символа к группе символов. Согласно условию задачи это — мал. буквы, цифры и символы + , — , * . В программе использованы 3 переменных-флага, описывающих текущие состояние чтение одного слова данной группы. Также есть переменные- счётчики для каждой группы слов. Каждый счётчик наращивается при сбрасывании флага, то есть, по завершении чтения группы.

Для проверки типа символа используются стандартные макросы isdigit и islower из библиотеки ctype .

Ссылка на ideone.com: http://ideone.com/LXiyTn