e-olymp4491 Трое из Простоквашино

Условие задачи:
— Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
— Подожди, Шарик, я занят.
— Ну Дядя Федор, ну смотри какой я код написал:

— Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из [latex]n[/latex] неотрицательных чисел и число [latex]k[/latex], а ты мне скажешь сколько существует таких пар [latex]l;r \left ( 1\leq l\leq r\leq n \right ),[/latex] что функция, вызванная следующим образом:

[latex]get[/latex]_[latex]max(1, 1, n, l, r)[/latex]

вернет значение равное [latex]k[/latex]. Можно считать, что перед этим была вызвана функция

[latex]build(1, 1, n)[/latex]

— Хорошо, Дядя Федор!

Входные данные:
В первой строке находятся число [latex]n \left ( 1\leq n\leq 10^{6} \right )[/latex] — количество элементов в массиве и [latex]k \left ( 1\leq k\leq 10^{9} \right )[/latex] — значение, которое должна вернуть функция. В следующей строке находится [latex]n[/latex] неотрицательных чисел, не превышающих [latex]10^{9}[/latex] — элементы массива.

Выходные данные:
Выведите единственное число – ответ на задачу.

Тесты:

Входные данные Выходные данные
[latex]n[/latex] [latex]k[/latex] [latex]elem[/latex]_[latex]tree[][/latex] [latex]ans[/latex]
5 3 1 2 3 2 3 11
10 6 1 4 7 6 2 4 1 9 6 6 7
20 15 5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6 43

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

Алгоритм решения:
Зададим отрезок массива, на котором обозначим границы [latex]\left [ left, right \right ][/latex]. Инициализируем изначально оба конца нулем. Рассмотрим некоторое [latex]elem\_tree\left [ i \right ][/latex] на нашем сегменте. Тогда если [latex]elem\_tree\left [ i \right ]=k[/latex], то на всем отрезке от [latex]left[/latex] до [latex]i[/latex] максимумом будет [latex]k[/latex]. Увеличим в таком случае [latex]left[/latex] и сделаем его равным [latex]i[/latex], причем [latex]right=0.[/latex] Если [latex]elem\_tree\left [ i \right ]\lt k[/latex], максимум будет также равен [latex]k[/latex]. В таком случае увеличиваем только [latex]right.[/latex] Если же [latex]elem\_tree\left [ i \right ]\gt k[/latex] , то [latex]left[/latex] устанавливаем равным [latex]i+1[/latex], а [latex]right[/latex] обнуляем.
Пройдя по всему массиву, мы должны получить значения [latex]left[/latex] равное количеству пар в которых максимум равен [latex]k[/latex], а [latex]right[/latex] должно стать равным нулю.

Код программы на Java
Условие задачи

e-olymp 1388. Заправки

Задача с сайта e-olymp.com.

Условие задачи

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

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

Сначала идет количество городов n (1 ≤ n ≤ 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

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

Выведите одно число — суммарную стоимость маршрута или -1, если добраться невозможно.

Тесты

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

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

Описание

Оптимальную стоимость маршрута будем находить по алгоритму Дейкстры. Цены на бензин в i-ом городе хранятся в массиве price. Минимальные стоимости маршрутов к каждому из городов хранятся в массиве distance, изначально все маршруты принимаем бесконечно дорогими. Кроме того, для хранения информации о том, был ли рассмотрен i-й город, используется массив used. Сам граф представляется в виде списка смежности. Для этого используется массив векторов graph. Если в итоге стоимость маршрута до целевого города осталась бесконечной, значит, пути к нему не существует, и выводится -1. Иначе выводится эта стоимость.

Код на ideone.com.

Засчитанное решение на e-olymp.com.

e-olymp 6129. Дек с защитой от ошибок

Задача с сайта e-olymp.com.

Условие задачи

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

push_front

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

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

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

pop_back

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

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

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

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

 

Входные данные
Каждая строка содержит одну команду.

Выходные данные
Для каждой команды вывести в отдельной строке соответствующий результат.

Тесты

Входные данные Выходные данные
1 front
back
pop_back
pop_front
exit
error
error
error
error
bye
2 push_back 1
back
exit
ok
1
bye
3 push_back 1
push_front 2
back
front
size
clear
size
pop_back
exit
ok
ok
1
2
2
ok
0
error
bye

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

Описание

Структура данных «дек» реализована в виде двусвязного списка. В классе MyDeque реализованы все требуемые методы. Те из них, после вызова которых, по условию, программа должна вывести некоторую строку, возвращают эту строку («ok» или «bye»). При попытке удалить или просмотреть элемент пустого дека создаётся и передаётся новый объект класса DequeException, наследующего класс Exception. В ходе работы функции main создаётся объект класса MyDeque, после чего читаются строки из входного потока и выполняются требуемые команды. В случае, если перехватывается исключение, выводится строка «error».

Код на ideone.com.

Засчитанное решение на e-olymp.com.

e-olimp 7365

Ссылка на оригинал задачи

Задача «Молоко и пирожок»

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Тесты:

Количество детей Вес Количество упаковок молока Количество пирожков
3 30 29 30 1 1
5 25 41 56 20 20 1 3
4 30 30 30 30 0 0
7 25 26 27 28 29 23 24 2 7

Код:

Алгоритм:

  1. Объявление и ввод значений переменных.
  2. Используем цикл for для подсчета необходимого количества пирожков.
  3. На основе предыдущих данных и округления в большую сторону (метод  Math.ceil ), подсчитываем необходимое количество пакетов молока.
  4. Окончание работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник

A393a

Задача:

Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n},[/latex] где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале [latex]i[/latex]-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

Тесты:

 
Вводимые данные Предполагаемый вывод Комментарий
4 4 3 2 1 4 3 2 1 Тест пройден
4 3 2 1
4 3 2 1
4 3 2 1
1 2 3 4 1 1 1 1 Тест пройден
1 2 3 4
1 2 3 4
1 2 3 4

Решение:

Считываем матрицу и проходим в цикле по каждой строке ведя поиск минимального элемента (но есть одно «Но»,  поиск ведется под главной диагональю матрицы).
У всех элементов находящихся под главной диагональю матрицы, включительно, индекс строк больше или равен индексу столбцов заданной матрицы. Учтем это при составлении программы.
Осталось только написать код с учетом вышеперечисленных особенностей задачи.

Код:

 

Версия программы на Ideone.com

Ссылка на источник

Шифровка

Условие задачи

Взята с сайта.
Мюллер много раз пытался поймать Штирлица с поличным, но тот всё время выкручивался. Как-то раз Штирлиц просматривал электронную почту. В это время незаметно вошел Мюллер и увидел, как у него на экране появился бессмысленный набор символов. «Шифровка», — подумал Мюллер. «UTF-8», — подумал Штирлиц.
Известно, что Штирлиц шифрует текст следующим образом:

1)Убирает все пробелы и знаки препинания.
2)Заменяет все подряд идущие одинаковые буквы на одну такую букву.
3)Многократно вставляет в произвольное место текста две одинаковых буквы.

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

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

aaxxHuuuuelllnnloxxvvoo!

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

Hello!

Решение с использованием функционала класса String

Решение с использованием функционала структуры данных ArrayList

Решение

Записываем строку в переменную типа $latex String$. Записываем ее в $latex ArrayList$ посимвольно. В следующем цикле добавляем проверку на индекс текущего элемента чтобы не выйти за пределы списка и проверяем совпадают ли ближайшие 2 символа, если да то удаляем их, если нет то переходим к следующему шагу цикла. По его окончанию выводим элементы списка.
Пример решения со строками на ideone.
Пример решения с списком на ideone.

Ю 4.24

Задача:

В массиве [latex]A[n][/latex] каждый элемент, кроме первого, заменить суммой всех предыдущих элементов.

 
Вводимые данные Предполагаемый вывод Комментарий
1 1 1 1 1 1 1 1 2 3 4 5 Тест пройден
1 2 3 4 5 6 7 8 9 1 1 3 6 10 15 21 28 36 Тест пройден
3 5 2 9 0 4 65 156 1 3 3 8 10 19 19 23 88 244 Тест пройден
2 -7 3 8 -4 5 -2 4 2 2 2 -5 -2 6 2 7 5 9 Тест пройден

Код:

Описание:

Простейшие операции с массивом. С помощью цикла записываем данные в массив, после чего, снова с помощью цикла, записываем новые данные во второй массив. Далее выводим результат.

Алгоритм:

  1. Объявление переменной и ввод размерности массива.
  2. Создание массива.
  3. Создание цикла, для записи вводимых данных в массив.
  4. Создание нового  массива.
  5. Создание цикла, для ввода обработанных данных в новый массив.
  6. Создание цикла, для вывода результата.
  7. Окончания работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник

AL6

Условие

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

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

$latex ({([])})$

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

Yes.

Код

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать класс $latex stack$, в который поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

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

Монстр

Ссылка на оригинал задачи

Задача:

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени [latex]b,[/latex] [latex]b + a,[/latex] [latex]b + 2a,[/latex] [latex]b + 3a,[/latex]…, а Морти кричит в моменты времени [latex]d,[/latex] [latex]d + c,[/latex] [latex]d + 2c,[/latex] [latex]d + 3c,[/latex]….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод:

Первая строка входных данных содержит два целых числа [latex]a[/latex] и [latex]b[/latex]  [latex](1\leq a,[/latex]  [latex]b\leq 100).[/latex]

Вторая строка входных данных содержит два целых числа [latex]c[/latex] и [latex]d[/latex] [latex](1\leq c,[/latex]  [latex]d\leq 100).[/latex]

Вывод:

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или  - 1, если они никогда не закричат одновременно.

Тесты:

Ввод
Вывод
20 2
9 19
82
2 1
16 12
-1

Код:

Решение:

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при [latex]a[/latex] и [latex]c.[/latex] Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

 

Версия программы на Ideone.com

Ссылка на источник

A60г

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть [latex]u[/latex] определяется по [latex]x[/latex] и [latex]y[/latex] yследующим образом: [latex] u=\begin{cases}x^(2)-1;\text{if}(x,y)\in D \\\sqrt{\left| x-1\right|};\text{ another case }\end{cases}[/latex] (запись[latex](x,y)\in D[/latex] означает, что точка с координатами [latex]x,y[/latex] принадлежит [latex]D[/latex]).

Даны действительные числа [latex]x[/latex] и [latex]y[/latex]. Определить [latex]u.[/latex]

a60%d0%b3
Тесты:

ВХОД ВЫХОД
[latex]x[/latex] [latex]y[/latex] [latex]u[/latex]
1 0.3 0.3 0.836660
2 1 1 0.000000
3 2 2 1.000000
4 0 0 -1.000000

Код:

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex]y<0.[/latex] Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3.

Версия программы на Ideone.com

Ссылка на источник