Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013
Ограничения:
| Время: | 0.5 секунды |
| Память | 64 Мб |
Условие
Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…
Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!
Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:
- «register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
- «login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
- «logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».
Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!
И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!
Исходные данные
В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq{n}\leq100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.
Результат
Для каждой операции выведите в отдельной строке сообщение в соответствии с форматом, описанным выше. Строго соблюдайте расстановку пробелов и знаков препинания в этих сообщениях.
Пример
| Исходные данные | Результат |
| 6
register vasya 12345 login vasya 1234 login vasya 12345 login anakin C-3PO logout vasya logout vasya |
success: new user added
fail: incorrect password success: user logged in fail: no such user success: user logged out fail: already logged out |
Решение
Для решения данной задачи нам необходимо воспользоваться структурой данных, которая хранит в себе пары вида «ключ — значение», а также структурой, которая будет хранить в себе некоторое множество. Воспользуемся структурами HashMap (Java) / map (C++) (key -> value) и HashSet (множество).
Рассмотрим операции, которые должна уметь обрабатывать наша система:
- «register username password». При регистрации нового пользователя будем помещать его в нашу «базу» зарегистрированных пользователей при условии, что он не зарегистрирован. Поиском по ключу в HashMap / map проверим существование уже зарегистрированного никнейма. Если найдётся такой пользователь, то система выдаст сообщение об ошибке.
- «login user password». Если база пользователей содержит в себе логин пользователя, пароли совпадают и пользователь не в он-лайне, то система разрешит user’у вход на форум. В противном случае, с соответствующими сообщениями об ошибках, не разрешит вход. Отслеживать пользователей, которые уже online, будем с помощью HashSet. Если пользователя нет в базе пользователей, которые сейчас на сайте, то открывая доступ, система поместит его в базу-online. Тогда новый запрос login с этого ника будет отклонён.
- «logout name». Если пользователя нет в базе пользователей, то его logout невозможен. Иначе, если его нет в базе-online, то тоже система выдаст сообщение об ошибке. Если user есть в базе пользователей и находится в онлайне, то выход возможен. Во время logouta удаляем пользователя из базы-online.
Реализация
В данном отчёте задачи будут представлены на языках Java и C++. Опишем, для начала, какие классы и методы необходимо использовать для решения этой задачи на языке Java:
Будем использовать интерфейс Map, имплементация (реализация) — HashMap. Из интерфейса Map воспользуемся следующими методами:
- containsKey(Key K) — возвращает true, если ключ найден. В противном случае — false;
- put(Key K, Value V) — записывает пару ключ-значение в структуру;
- get(Key K) — по ключу возвращает значение.
Используем интерфейс Set, реализация — HashSet. Будем использовать следующие методы:
- contains(Object o) — возвращает true, если элемент принадлежит множеству. Иначе — false;
- add(Object o) — добавляет элемент во множество;
- remove(Object o) — удаляет элемент из множества.
Теперь для С++:
В С++ воспользуемся немного другим подходом. Воспользуемся только map. Создадим структуру, которая будет содержать 2 поля: пароль и статус. Воспользуемся следующими методами:
- find (K key) — возвращает итератор элемента.
- end() — возвращает итератор за последним элементом.
set или без него?
Для данной задачи использование set’a не принципиально. Но если предположить, что, помимо запросов регистрации, входа и выхода, был бы ещё и запрос вывести пользователей, которые онлайн, преимущество использования set’a очевидно.
Код на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) { //create an DB for online and reged users Map DB = new HashMap<String, String> (); HashSet <String> DBin = new HashSet <String> (); Scanner in = new Scanner (System.in); PrintWriter out = new PrintWriter(System.out); //a number of queries int n = in.nextInt(); for (int i = 0; i < n; i++){ String s, log, pass; //command s = in.next(); if (s.equals("register")){ log = in.next(); //login pass = in.next(); //password if (DB.containsKey(log)){ //login in DB? out.println("fail: user already exists"); out.flush(); } else { DB.put(log, pass); out.println("success: new user added"); out.flush(); } } if (s.equals("login")){ log = in.next(); pass = in.next(); if (DB.containsKey(log)){ //if user is reg if (pass.equals(DB.get(log))) { //if the password is well if (!DBin.contains(log)) { //online? DBin.add(log); out.println("success: user logged in"); out.flush(); } //Errors else { out.println("fail: already logged in"); out.flush(); } } else { out.println("fail: incorrect password"); out.flush(); } } else { out.println("fail: no such user"); out.flush(); } } if (s.equals("logout")){ log = in.next(); if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately. out.println("fail: no such user"); out.flush(); } else { if (!DBin.contains(log)){ //so offline user does out.println("fail: already logged out"); out.flush(); } else { DBin.remove(log); out.println("success: user logged out"); out.flush(); } } } } } } |
Код на С++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <iostream> #include <stdio.h> #include <string> #include <iomanip> #include <stack> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <map> using namespace std; struct status { //status - password and online string password; bool online = false; }; map <string, status> database; //user database int main () { int n; cin >> n; //number of queries typedef std::map<std::string, status> db; // use this typedef for an iterator while (n--){ string com, login; //command and login status query; //for status input cin >> com; if (com == "register"){ cin >> login >> query.password; db::iterator it = database.find(login); //returning an iterator if (it != database.end()) { //each el from database is in [begin, end). it = database.end() means that there is no such element in db cout << "fail: user already exists\n"; } else { database[login].password = query.password; // register cout << "success: new user added\n"; } } //user can log in if he isn't online but he is registered if (com == "login") { cin >> login >> query.password; db::iterator it = database.find(login); if (it != database.end()){ if (query.password == database[login].password){ if(!database[login].online){ database[login].online = true; cout << "success: user logged in\n"; } else cout << "fail: already logged in\n"; } else cout << "fail: incorrect password\n"; } else cout << "fail: no such user\n"; } //logout if (com == "logout") { cin >> login; if (database.find(login) == database.end()) cout << "fail: no such user\n"; else { if (!database[login].online) cout << "fail: already logged out\n"; else { database[login].online = false; cout << "success: user logged out\n"; } } } } return 0; } |
Результаты
Обе реализации прошли все тесты на Тимусе с такими результатами:
| Язык | Время работы | Память |
| С++ | 0.015 | 412 КБ |
| Java | 0.124 | 1 804 КБ |