А290

Сабиров Ильдар
Сабиров Ильдар

Latest posts by Сабиров Ильдар (see all)

Задача. Даны действительные числа [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots,y_{n}[/latex]. Получить [latex]x’_{1},\ldots,x’_{n}[/latex],[latex]y’_{1},\ldots,y’_{n}[/latex], преобразовав для получения [latex]x’_{i},y’_{i}[/latex] члены [latex]x_{i},y_{i}[/latex] по правилу: если они оба отрицательны, то каждый из них увеличить на 0.5; если отрицательно только одно число, то отрицательное число заменить его квадратом; если оба числа неотрицательны, то каждое из них заменить на среднее арифметическое исходных значений.

Тесты

n [latex]x_{1},\ldots,x_{n}[/latex] [latex]y_{1},\ldots,y_{n}[/latex] [latex]x’_{1},\ldots,x’_{n}[/latex][latex]y’_{1},\ldots,y’_{n}[/latex] Комментарий
4 1 4 -3 8

3 -2 -4 2

2 4 -2.5 5

2 4 -3.5 5

Пройдено
5 0 -0.5 4 -9 0.35

0 -0.5 11 0.247 1.650

0 0 7.5 81 1

0 0 7.5 0.247 1

Пройдено
3 0 3 -0.14942

-3 0 793

0 1.5 0.0223263

9 1.5 793

Пройдено

Реализация (массив структур)

Алгоритм решения (массив структур)
Для выполнения данной задачи, воспользуемся массивом структур. Каждый [latex]i[/latex]-ый элемент такого массива заполняем двумя действительными числами [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. После этого мы выполняем проверку и преобразование этих чисел по заданным в условии правилам. Затем их выводим.

Реализация (класс vector)

Алгоритм решения (класс vector)
Данный способ реализации помогает решить задачу преобразования чисел [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots, y_{n}[/latex] для неизвестного значения [latex]n[/latex] — количества элементов [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. Их количество будет зависить от количества введенных элементов. Программа считывает элементы [latex]x_{i}[/latex] и [latex]y_{i}[/latex] поочередно, т.е. [latex]x_{1}\rightarrow y_{1}\rightarrow x_{2} \rightarrow y_{2} \rightarrow\ldots\rightarrow x_{n}\rightarrow y_{n}[/latex]. В остальном алгоритм такой же как с массивом структур.

Ссылка на код (массив структур)
Ссылка на код (класс vector)

e-olymp 6124. Стек неограниченного размера

Станислав Коциевский
Станислав Коциевский

Latest posts by Станислав Коциевский (see all)

Задача

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

push n

Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из стека последний элемент. Программа должна вывести его значение.

back

Программа должна вывести значение последнего элемента, не удаляя его из стека.

size

Программа должна вывести количество элементов в стеке.

clear

Программа должна очистить стек и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и popпрограмма должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.

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

Описаны в условии.

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

Описаны в условии.

Тесты:

 ввод  вывод ввод вывод
push 7
clear
push 4
back
push 1151
back
pop
back
size
exit
ok
ok
ok
4
ok
1151
1151
4
1
bye
 push 2
push 7
back
pop
pop
back
push 1
back
pop
exit
ok
ok
7
7
2
error
ok
1
1
bye
pop
push 42
back
size
pop
size
push 17
push 19
push 24
back
size
clear
size
exit
error
ok
42
1
42
0
ok
ok
ok
24
3
ok
0
bye
back
size
clear
size
back
pop
push 2
pop
push 1
size
back
exit
error
0
ok
0
error
error
ok
2
ok
1
1
bye

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

Решение

В данном решении стек состоит из объектов, далее именуемых звеньями, каждый из которых состоит из массива, переменной, отвечающей свободному месту в массиве, ссылки на следующее звено. Кроме того, у звена есть метод для его создания, методы push и pop. В этих методах, кроме их прямой функции, отслеживается количество свободного места в звене. С этим всем работает сам стек. В самом стеке есть указатель на первое звено (звено, в которое был добавлен последний элемент, который все еще есть в стеке) и переменная S, отвечающая количеству элементов в стеке. Еще есть такие методы, как создание и удаление звена, а также все методы указанные в условии.  Создается звено, если нужно что-то добавить в стек и в текущих звеньях уже нет свободного места, а удаляется, если после извлечения чего-то из стека первое звено пустое (или при методе clear). Для этого и нужна переменная отвечающая свободному месту в звене.

Теперь немного о методах, указанных в условии. Во-первых, все методы, меняющие число элементов в стеке, соответственно влияют на переменную, этому числу отвечающую, а size ее просто возвращает. Методы push и pop непосредственно для выполнения своей функции обращаются к своим аналогам в первом звене. Методы pop и back проверяют в начале, не пуст ли стек, через переменную S. Back получает значение последнего элемента, работая непосредственно с массивом первого звена. exit вообще не создан, как метод, а обрабатывается непосредственно в функции Main().  Собственно, сама эта функция только принимает и обрабатывает через условные операторы запросы, а потому описывать ее нет смысла (см. код программы).

Немного слов для обобщения. Если бы стек бы основан просто на массиве, для неограниченности пришлось бы каждый раз, когда в текущем массиве заканчивается место, копировать уже имеющиеся данные в новый массив большего размера. Кроме того, возникла бы необходимость в очень большом цельном участке памяти. Если бы в этой реализации стека вообще не использовались массивы, а просто у каждого элемента была ссылка на следующий, это бы очень увеличило затраты памяти, т.к. эти ссылки в количестве, равном количеству элементов в стеке, нужно где-то хранить.  В данном же решении нужно какое-то количество цельных, но не таких больших участков памяти, не так много памяти под ссылки на следующее звено, а при заполнении имеющихся массивов ничего не приходится переписывать — просто добавляется еще один. Примечание: эффективность для разных задач зависит от размеров массива в звене.

задача взята с сайта e-olymp

Ссылка на засчитанное решение

ссылка на код на ideone

 

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

Марченко Філіп Олександрович
Марченко Філіп Олександрович

Latest posts by Марченко Філіп Олександрович (see all)

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 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}\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  (множество).

Рассмотрим операции, которые должна уметь обрабатывать наша система:

  1. «register username password». При регистрации нового пользователя будем помещать его в нашу «базу» зарегистрированных пользователей при условии, что он не зарегистрирован. Поиском по ключу в HashMap / map проверим существование уже зарегистрированного никнейма. Если найдётся такой пользователь, то система выдаст сообщение об ошибке.
  2. «login user password». Если база пользователей содержит в себе логин пользователя, пароли совпадают и пользователь не в он-лайне, то система разрешит user’у вход на форум. В противном случае, с соответствующими сообщениями об ошибках, не разрешит вход. Отслеживать пользователей, которые уже online, будем с помощью HashSet. Если пользователя нет в базе пользователей, которые сейчас на сайте, то открывая доступ, система поместит его в базу-online. Тогда новый запрос login с этого ника будет отклонён.
  3. «logout name». Если пользователя нет в базе пользователей, то его logout невозможен. Иначе, если его нет в базе-online, то тоже система выдаст сообщение об ошибке. Если user есть в базе пользователей и находится в онлайне, то выход возможен. Во время logouta удаляем пользователя из базы-online.

Реализация

В данном отчёте задачи будут представлены на языках Java и C++. Опишем, для начала, какие классы и методы необходимо использовать для решения этой задачи на языке Java:

HashMap:

Будем использовать интерфейс Map, имплементация (реализация) — HashMap. Из интерфейса Map воспользуемся следующими методами:

  • containsKey(Key K) — возвращает true, если ключ найден. В противном случае — false;
  • put(Key K, Value V) — записывает пару ключ-значение в структуру;
  • get(Key K) — по ключу возвращает значение.

HashSet:

Используем интерфейс 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: 

Код на С++:

 

Результаты

Обе реализации прошли все тесты на Тимусе с такими результатами:

Язык Время работы Память
С++ 0.015 412 КБ
Java 0.124 1 804 КБ

Ссылки

Задача

Ideone (Java)

Ideone (C++)

Java (Set)

Java (Map)

C++ (map)

C++ (set)

e-olimp: 694. Минимум в очереди

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

e-olimp: 694 — Минимум в очереди

Постановка задачи

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

Алгоритм решения

Классическая модификация очереди с поддержкой минимального хранимого значения подразумевает использование двух модифицированных стеков, один из которых служит только для проталкивания элементов в очередь, а другой — только для выталкивания. Стеки хранят пары значений: непосредственно элемент и минимальное значение в очереди на момент его добавления, что позволяет поддерживать актуальную информацию при выполнении модифицирующих запросов (см. классический труд Кормена и статью на e-maxx). Более подробно механика процесса описана в комментариях к коду.

Реализации:

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

Спортивный подход

ideone: http://ideone.com/pvVixS
засчитанное решение: http://www.e-olimp.com/solutions/1926658

Преимущества

  • Простота. Концепция воплощается буквально — даже в условиях ограниченности во времени ошибиться трудно.
  • Наглядность и компактность кода.
  • Сообразность средств цели: постановка задачи требует реализации только трех функций: проталкивания, выталкивания и взятия крайнего элемента. Каждая из них реализована по возможности наиболее простым способом.

Недостатки

  • Немасштабируемость. При необходимости внедрения дополнительного функционала или изменении постановки задачи (скажем, отсутствии явной верхней границы для входных данных) возникают проблемы, решение которых неизбежно приводит к использованию объектно-ориентированных средств языка.
  • Перерасход памяти. Реальное количество одновременно содержащихся элементов в каждом из стеков на порядок меньше, но из формулировки задания это не следует и выясняется экспериментальным путём.
  • Костыли, избыточные сущности. Отличительная черта одноразового кода. Во время соревнования требования к коду достаточно мягкие: он должен работать. Желательно — предсказуемым образом. Причем, нередко реализуется не оптимальное и логичное решение, а то, которое понимаешь. Отладка и чтение таких программ — занятие не из приятных.

Объектно-ориентированный подход

ideone: http://ideone.com/A6BpwN
засчитанное решение: http://www.e-olimp.com/solutions/1924823

Преимущества

  • Масштабируемость. Добавление функционала сводится к написанию новых методов класса.
  • Универсальность. Основа стека — односвязный список. Следовательно, его размер ограничен только объёмом доступной оперативной памяти.
  • Инкапсуляция. Реализация методов класса отделена от контекста выполняемых им функций в теле программы.
  • Польза процесса. Быстро написать более простое решение, не разобравшись в тонкостях классической реализации, почти наверняка не удастся.

Недостатки

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

e-olimp 693. Минимум в стеке

Ілларіонова Марія Валеріївна
Ілларіонова Марія Валеріївна

Latest posts by Ілларіонова Марія Валеріївна (see all)

Задача e-olimp.com №693. На вход программы подается набор операций со стеком. Каждая операция состоит в добавлении или удалении элемента из стека. После выполнения каждой операции найдите наименьшее число, которое находится в стеке. Сложите все полученные числа и получите ответ. Если после некоторой операции стек оказался пуст, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как стек пуст, то не выполняйте его.

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

Входные данные генерируются в самой программе. На вход подаются параметры для генерации входной последовательности.

Первое число содержит количество операций [latex]n (1\leq n\leq10^{6})[/latex] со стеком. Затем следуют четыре неотрицательных целых числа [latex]a, b, c, x_{0}[/latex] не превосходящие [latex]10000[/latex].

Для получения входных данных генерируем последовательность [latex]x[/latex].

Первое число в генерируемой последовательности [latex]x_{1}[/latex]. Первое, а также каждое следующее число вычисляется из предыдущего по формуле:

[latex]x_{i}=\left(a\cdot x_{i-1}^{2} + b\cdot x_{i-1} + c\right)/100 \bmod{10^{6}}[/latex],

где ‘/‘ — операция целочисленного деления, а ‘[latex] \mod{}[/latex]’ — остаток от деления.

Если [latex]x_{i} \mod{5}<2[/latex], то необходимо удалить число из стека. В противном случае необходимо добавить в стек число [latex]x_{i}[/latex].

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

Выведите результирующую сумму.

Ссылка на задачу. Ссылка на засчитанное решение.

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

 Пояснение решения

На мой взгляд сложность задачи состояла только в том, чтобы реализовать взятие минимального элемента из стека за [latex]O\left(1 \right)[/latex].

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

e-olimp 6124. Стек неограниченного размера

Ілларіонова Марія Валеріївна
Ілларіонова Марія Валеріївна

Latest posts by Ілларіонова Марія Валеріївна (see all)

Стек неограниченного размера

Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы.  Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.

Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.
Пояснение: Размер стека должен быть ограничен только размером доступной оперативной памяти.

Решение

Предлагается реализация стека через связные списки.

Положительные стороны:

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

Отрицательные стороны:

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

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