e-olymp 7337. Скидки

Latest posts by Мороз Дима (see all)

Задача

В супермаркете электроники, если верить телерекламе, существует система скидок: из двух купленных товаров полностью оплачивается только стоимость товара, который дороже, а другой отдается бесплатно. Какой суммы достаточно, что бы оплатить покупку трёх товаров, если известна цена каждого?
Входные данные: три натуральных числа $a, b, c$ — цены трёх товаров $\left(1 ≤ a, b, c ≤ 10000 \right).$
Выходные данные: стоимость покупки.

Тесты

Входные данные
Выходные данные
213   6554   234
6767
320   3670   5555
5875
15   47   13
60
215   30   73
245
370   53   823
876

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

Решение задачи

Для нахождения самого дорогого и самого дешёвого товаров мы используем встроенные функции $\min \left(\right)$ и $\max \left(\right)$. Находим минимальное число среди чисел $a$, $b$ и $c$: $\min \left(\min \left(a, b \right), c \right)$ (пример: $\min \left(\min \left(1, 2 \right), 3 \right) = 1$). Далее проводим такую же операцию с нахождением максимального числа среди $a$, $b$ и $c$: $\max \left(\max \left(a, b \right), c \right)$ (пример: $\max \left(\max \left(1, 2 \right), 3 \right) = 3$). Затем суммируем полученные минимальное и максимальное числа и получаем ответ.

Ссылки

Условие задачи на e-olymp.com
Код задачи на ideone.com

A297

Молоканов Юрий
Молоканов Юрий

Latest posts by Молоканов Юрий (see all)

Условие

Даны целые числа [latex]a_1, \ldots , a_{100}[/latex]. Получить новую последовательность из 100 целых чисел, заменяя [latex]a_i[/latex] нулями, если [latex]|a_i|[/latex] не равно [latex]\text{max} (a_1, \ldots , a_{100})[/latex], и заменяя [latex]a_i[/latex] единицей в противном случае ([latex]i = 1, \ldots , 100[/latex]).

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

Тестирование

Входные данные Выходные данные
1 0 1
2 1 0 -1 1 0 1
3 -1 0 -1 0 1 0
4 -1 -1 -1 0 0 0
5 4 4 4 4 1 1 1 1
6 10 5 -1 -10 -20 0 1 2 3 1 0 0 1 0 0 0 0 0

Код

Решение

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

Так как последовательность состоит из целых чисел и ее длина неизвестна, воспользуемся классом vector типа int:

Затем отдельно считаем первый элемент последовательности и возьмем его в качестве максимума, после чего поместим в вектор:

Заполним вектор оставшимися числами, попутно обновляя переменную max , если встретим число, большее хранимого максимума:

Теперь обработаем последовательность согласно условию задачи, то есть заменим каждое число либо нулем, если его абсолютное значение не равно максимуму, либо единицей в противном случае:

Наконец, выведем ответ на задачу — полученную последовательность из нулей и единиц:

Ссылки

Код программы на Ideone.com;

Условие задачи в сборнике задач по программированию (С. А. Абрамов).

e-olymp 1308. Наибольшая грань подстроки

Молоканов Юрий
Молоканов Юрий

Latest posts by Молоканов Юрий (see all)

Условие

Гранью (border, verge, brink) [latex]br[/latex] строки [latex]S[/latex] называется любой собственный префикс этой строки, равный суффиксу [latex]S[/latex].

Строка [latex]S = abaababaabaab[/latex] имеет две грани (не пустые): [latex]ab[/latex] и [latex]abaab[/latex]. Строка [latex]S = abaabaab[/latex] также имеет две грани: [latex]ab[/latex] и [latex]abaab[/latex], но вторая грань — перекрывающаяся. Строка длины [latex]n[/latex] из повторяющегося символа, например [latex]aaaaaaaa[/latex] (или [latex]a^8[/latex]), имеет [latex]n — 1[/latex] грань. Для [latex]S = a^8[/latex] это грани: [latex]a[/latex], [latex]aa[/latex], [latex]aaa[/latex], [latex]aaaa[/latex], [latex]aaaaa[/latex], [latex]aaaaaa[/latex], [latex]aaaaaaa[/latex].

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

Длина грани — это количество символов в ней.

Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок [latex]S[1..i][/latex] ([latex]i = 1..n[/latex])  и сохранить их в массиве [latex]br[1..n][/latex].

Найдите наибольшее значение грани в массиве наибольших граней [latex]br[/latex] для всех подстрок [latex]S[/latex].

Тестирование

Входные данные Выходные данные Комментарий
1 abaabaab 5 abaab в исходной строке
2 abaababaabaab 6 abaaba в подстроке abaababaabaab
3 aaaaaaaa 7 aaaaaaa в исходной строке
4 YM 0 Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме Y в качестве префикса и M в качестве суффикса вариантов выбора нет
5 &#%*%#& 1 & в исходной строке
6 15015105 2 15 в подстроке 15015105
7 f0A+.f0A+.f0A.+.A0f 8 f0A+.f0A в подстроке f0A+.f0A+.f0A.+.A0f

Код

Решение

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

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

  1. Так как по условию грань не может совпадать со строкой, перебор начнем со случая, когда первый символ суффикса находится на второй позиции в строке, а первый символ префикса — на первой позиции. В каждой следующей итерации первый символ суффикса будет смещаться на одну позицию вправо, но первый символ префикса будет неизменно оставаться на первой позиции. Цикл продолжается до тех пор, пока не дойдем до случая, когда первый символ суффикса будет последним символом строки, и пока количество символов от начала суффикса до конца строки будет больше длины максимальной найденной на данный момент грани (это условие необязательно, но оно ускоряет работу программы, отбрасывая варианты, когда получить более длинную грань уже никаким образом не получится):
  2. Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают. К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.
    В виду того, что нумерация символов в строке начинается с нуля, переменная j выполняет здесь одновременно роль первого символа префикса и длины текущей грани.
  3. Сравним длину текущей грани с длиной максимальной грани и, если необходимо, обновим значение максимальной.

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

Ссылки

Условие задачи на E-Olymp;

Код программы на Ideone.com;

Подтверждение решения на E-Olymp.