e-olimp №2907. Можете ли Вы ответить на эти вопросы — 3

Условие

Задана последовательность целых чисел [latex]a_1, a_2, \ldots, a_n[/latex] ([latex]| a_i | \le 10000[/latex], [latex]1 \le n \le 50000[/latex]). Над ней Вам следует выполнить [latex]m[/latex] ([latex]m \le 50000[/latex]) операций:

  • модифицировать [latex]i[/latex]-ый элемент последовательности
  • для заданных [latex]x[/latex] и [latex]y[/latex] вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j[/latex], [latex]x \le i \le j \le y \}[/latex]

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

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность [latex]a_1, a_2, \ldots, an[/latex]. Третья строка содержит число [latex]m[/latex]. Следующие [latex]m[/latex] строк содержат запросы вида:

  • [latex]0[/latex] [latex]x[/latex] [latex]y[/latex]: изменить [latex]a_x[/latex] на [latex]y[/latex] ([latex]| y | \le 10000[/latex]).
  • [latex]1[/latex] [latex]x[/latex] [latex]y[/latex]: вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y \}[/latex]

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

Для запроса на выполнение программы нажать здесь.

Ссылка на использованный алгоритм.

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

e-olimp 5079. Транзитивность ориентированного графа

Задача e-olimp 5079.

Условие

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин [latex]u[/latex], [latex]v[/latex] и [latex]w[/latex] из того, что из [latex]u[/latex] в вершину [latex]v[/latex] ведет ребро и из вершины [latex]v[/latex] в вершину [latex]w[/latex] ведет ребро, следует, что из вершины [latex]u[/latex] в вершину [latex]w[/latex] ведет ребро.

Проверьте, что заданный ориентированный граф является транизитивным.

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

Входной файл содержит число [latex]n (1 \le n \le100)[/latex] — число вершин в графе, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

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

Выведите в выходной файл YES если граф является транзитивным и NO в противном случае.

Тесты

Входные данные Выходные данные
3
0 1 1
0 0 1
0 0 0
YES
3
0 1 1
1 0 0
0 1 0
NO

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

Ссылка на засчитанное решение.
Для запроса на выполнение нажать здесь.

Решение

Представим матрицу смежности графа в виде двумерного массива. Тогда, если [latex]a[i][j] = 1[/latex], то из вершины [latex]i[/latex] в вершину [latex]j[/latex] ведёт ребро. Проверяем с помощью циклов транзитивность графа, то есть если из вершины [latex]i[/latex] в вершину [latex]j[/latex] ведёт ребро и из вершины [latex]j[/latex] в вершину [latex]z[/latex], то граф транзитивен, если есть ребро [latex]a[i][z][/latex].
 

e-olymp 6122. Простой стек

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

  • push [latex]n[/latex] — Добавить в стек число [latex]n[/latex] (значение [latex]n[/latex] задается после команды). Вывести ok.
  • pop — Удалить из стека последний элемент. Программа должна вывести его значение.
  • back — Вывести значение последнего элемента, не удаляя его из стека.
  • size — Вывести количество элементов в стеке.
  • clear — Очистить стек и вывести ok.
  • exit — Вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

Тесты

Входные данные Выходные данные
1 push 2
push 3
push 5
back
size
pop
size
push 7
pop
clear
size
exit
ok
ok
ok
5
3
5
2
ok
7
ok
0
bye
2 push 7
size
push 1
pop
back
exit
push 4
pop
ok
1
ok
1
7
bye

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

Для запроса на выполнение нажать здесь.

Решение

Реализуем стек с помощью массива, указателя на на верхнюю незаполненную ячейку массива ([latex]cursor[/latex]) и функций, с помощью которых выполняются команды push, pop, back, size, clear:

  • функция push выполняет запись в ячейку с номером [latex]cursor[/latex] элемента [latex]n[/latex];
  • функция pop возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом удаляя его из стека;
  • функция back возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом не удаляя его из стека;
  • функция size возвращает значение [latex]cursor[/latex], то есть размер стека;
  • функция clear присваивает [latex]cursor[/latex] значение [latex]0[/latex].

Команда exit выполнена с помощью оператора [latex]break[/latex], который заканчивает выполнение цикла, в котором запрашиваются команды.

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

А286

Задача

Даны целые числа [latex]a_1,\cdots, a_{n}[/latex]. Получить новую последовательность, выбросив из исходной все члены со значением [latex]max(a_1,\cdots,a_{n})[/latex].
Тесты
Входные данные Выходные данные
1 0 0 0 0 0 0 0 0
2 998 103678 3333 800000 542 2 48 132 9 745 998 103678 3333 542 2 48 132 9 745
3 1 2 42 -138 0 99 1 242 70  21 1 2 42 -138 0 99 1 70 21
4 -144 -789342454657 -155 -923 -7 -144 -789342454657 -155 -923
5  8 8 8 8 11 11 11 11 8 8 8 8  8 8 8 8 8 8 8 8
Код программы
Для запроса на выполнение нажать здесь.

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

Mif 18

Задача Mif 18.

Условие

Введите из стандартного потока целое число и выведите его словами на английском языке.

Тесты

Входные данные Выходные данные
0  zero
-7284 minus seven thousand two hundred and eighty-four
900000000000000010 nine hundred billiard ten
4561230057773 four billion five hundred and sixty-one milliard two hundred and thirty million fifty-seven thousand seven hundred and seventy-three
599999990999999900 five hundred and ninety-nine billiard nine hundred and ninety-nine billion nine hundred and ninety milliard nine hundred and ninety-nine million nine hundred and ninety-nine thousand nine hundred

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

Для запроса на выполнение нажать здесь.

Решение

Данная программа выводит число «по частям», то есть вначале триллионы, затем биллиарды, биллионы  и т.д. до единиц (за условием их наличия). Если число отрицательное, то она выводит «минус» и его абсолютную величину.

При выполнениии задания я воспользовалась длинной шкалой наименования чисел.

Программа выводит целые числа в промежутке [latex](-10^{19}; 10^{19})[/latex].

e-olymp 378. Таинственная записка

Задача e-olymp 378.

Условие

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

Закодированное сообщение: HPC PJVYMIY

Декодированное сообщение: ACM CONTEST

В этом примере выполнены следующие замены: H=A, P=C, C=M, J=O, V=N, Y=T, M=E и I=S.

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

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

В первой строке входного файла записано закодированное сообщение. Вторая строка — 26 латинских букв верхнего регистра, представляющих собой код для соответствующего символа алфавита: первый символ дает код для A, второй для B и так далее. Используются только буквы верхнего регистра. В закодированном сообщении могут появиться пробелы, которые должны быть сохранены в выходной строке.

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

В выходной файл вывести одну строку, в которой содержится расшифрованное сообщение.

Тесты

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

BLMRGJIASOPZEFDCKWYHUNXQTV

ACM CONTEST
FDY GAI BG UKMY
KIMHOTSQYRLCUZPAGWJNBVDXEF
THE SKY IS BLUE
LJBSLJL IJWWDEJ
KCFAGWRZMEXDNUYHVBOIJLSTPQ
DECODED MESSAGE

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

Для запроса на выполнение нажать здесь.

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

Код программы с использованнием класса «string»

Для запроса на выполнение нажать здесь.

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

Решение

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