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»

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

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

Решение

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

MLoops 10

Задача MLoops 10

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex]m > 0[/latex] (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр [latex]k < n[/latex].
Замечание 2. Многоточие означает продолжение последовательности
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

Тесты

Входные данные Выходные данные
3 6 2 121+12
21+121
1+121+
5 5 4 12343
23432
34321
4321+
321+1
4 19 9 12345678987654321+1
2345678987654321+12
345678987654321+123
45678987654321+1234
7 14 10 123456789109876
234567891098765
345678910987654
456789109876543
567891098765432
678910987654321
78910987654321+

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

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

Решение

Дано [latex]m[/latex] строк, в каждой из которых определены последовательности, каждая из которых состоит из чисел, возрастающих от 1 до [latex]k[/latex], затем спадающих до 1 и знак «+». Закономерность данной задачи состоит в последовательном сдвиге вправо каждой последующей строки и её выведении с элемента стоящего на первом месте.

Последовательность знаков каждой строки повторяется через каждые [latex]2k[/latex] знаков. Именно поэтому на [latex]2k[/latex]-ом месте будет стоять «+» (так как отсчёт начинается с 1, а не с 0).

Определяем первый знак каждой строки сравнением номера строки [latex]i[/latex] с [latex]k[/latex]: если он меньше или равен [latex]k[/latex], то он и будет первым знаком данной строки, в противном случае — первым знаком будет [latex](2k — i)[/latex].

Затем выводим цифры каждой строки:

  • если цифра, с которой ведётся отсчёт данной строки, меньше [latex]k[/latex], то увеличиваем каждую последующую цифру (за «+» следует 1 и далее аналогично этому условию);
  • если цифра равна [latex]k[/latex], то уменьшаем последующие цифры.

 

MLoop 12

Задача. MLoop 12

Вычислите с точностью [latex]\varepsilon[/latex] значение функции [latex]f(x) = \arctan x[/latex]. При вычислениях допустимо использовать только арифметические операции.

Тесты

Входные данные Выходные данные
Точность Аргумент [latex]\arctan x[/latex] Погрешность
1 1 0.5 0.5 0.0363524
2 10 0.82 0.669293 0.0175249
3 100 0.77 0.652823 0.00335552
4 1000 1 0.666667 0.118731

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

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

Решение

Для того, чтобы найти приблизительное значение [latex]\arctan x[/latex] возпользуемся формулой ряда Тейлора: [latex]\arctan x = x — \frac{x^3}{3} + \frac{x^5}{5} -[/latex] … [latex]= \sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1}\cdot x^{2n+1}[/latex] для всех [latex]|x| \le 1[/latex]. Представим каждый член суммы как [latex]a_n = \frac{(-1)^n\cdot a^{2n+1}}{2n+1}[/latex], и будем рекурсивно вычислять числитель данной дроби [latex]m_n = m_{n-1} \cdot (- a^2)[/latex]. Тогда, будем находить значение очередного члена ряда по формуле [latex]a_n = \frac{m_n}{2n + 1}[/latex], пока [latex]a_n > \frac{1}{\varepsilon}[/latex].

Mif 17.13

17_13

Задача №17.13

Условие

Принадлежит ли точка (х;у) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты

Входные данные (точка K) Выходные данные
(3;4) no
(1;1) yes
(1;4) yes
(3;0) yes
(0;6) no
(-13; -3) no
(-4.5; -3) yes

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

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

Решение

[latex](x — x_A)(y_B — y_A) — (y — y_A)(x_B — x_A) = 0[/latex] — уравнение прямой, проходящей через точки [latex]A[/latex] и [latex]B[/latex]. Тогда для любой точки [latex](x; y)[/latex] можно определить её местоположение относительно прямой [latex]AB[/latex]. Если левая часть неравенства будет равно 0, то точка лежит на прямой. Прямая [latex]AB[/latex] разбивает плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения, а точки из другой полуплоскости — отрицательные. Тогда, объединением условий местоположения точки [latex](x; y)[/latex] и местоположения точек [latex]C, A, B[/latex] относительно прямых [latex]AB[/latex], [latex]BC[/latex], [latex]AC[/latex] соответственно, мы сможем определить местоположение данной точки относительно треугольника.

По рисунку видно, что [latex]A(1;4), B(5, -4), C(-5, -3)[/latex]. Тогда, определяем положение точки [latex]K[/latex] относительно каждой прямой и точки не лежащей на данной прямой треугольника [latex]ABC[/latex].

 

e-olymp 10. Садовник

Задача e-olymp №10

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

Условие

Садовник посадил за день [latex]n[/latex] деревьев и должен был вылить под каждое деревцо по ведру воды. Так как в день посадки шёл дождь, садовник начал поливку деревьев не в день посадки, а начиная с какого-то [latex]k[/latex]-го дня.

Сколько дней садовник не поливал деревья, если в последний день он под каждое из деревьев вылил [latex]\frac{1}{n}[/latex] часть воды из ведра, в предпоследний [latex]\frac{1}{n-1}[/latex]часть, и т.д., а всего под каждое из деревьев вылил не более, чем по половине ведра воды?

 

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

Количество деревьев [latex]n[/latex]. [latex]0 < n \le 1000000[/latex]

 

Тесты

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

(количество деревьев)

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

(искомое количество дней)

3 2
1000000 606531

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

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

Решение

Пускай в переменной [latex]days[/latex] будет храниться количество дней, в которые садовник поливал деревья, но так как отсчёт начинает с [latex]days = 0[/latex], ([latex]\frac{1}{n}[/latex]), то количество всех дней, когда садовник поливал деревья будет равно максимальному значению [latex]days[/latex] в цикле плюс 1; в переменной [latex]waterPerTree[/latex] — количество вёдер воды, вылитых на одно дерево. Количество вёдер воды, вылитых под одно дерево в определённый день: [latex]\frac{1}{n — days}[/latex]. Так как под каждое дерево садовник вылил не больше [latex]\frac{1}{2}[/latex] ведра воды, то будем выполнять цикл, пока [latex]waterPerTree[/latex] не будет равно этому значению.

Чтоб найти количество дней, на протяжении которых садовник поливал деревья, разделим количество воды, потраченное садовником за всё время поливки [latex]\frac{1}{2}[/latex] на количество вёдер воды, вылитых под одно дерево в определённый день [latex]\frac{1}{n — days}[/latex]. Тогда получим, что [latex]\frac{n — days}{2}[/latex].

По условию задачи, садовник должен был вылить по ведру воды под каждое деревцо, но вылил всего по половине из-за дождя. Из этого следует, что количество воды, выпавшей на каждое деревцо, пиблизительно равно [latex]\frac{1}{2}[/latex] ведра воды. Тогда если всего под каждым деревом по 1 ведру воды за [latex]x[/latex] дней, а садовник вылил по [latex]\frac{1}{2}[/latex] ведра воды за [latex]days + 1[/latex] дней, то [latex]x = 2n — 2days[/latex]. В итоге, [latex]k = \frac{1}{2}x = n — days[/latex]. Но, так как в последнем действии цикла вычисленное [latex]waterPerTree[/latex] будет больше [latex]\frac{1}{2}[/latex], то [latex]k = n — (days — 1)[/latex].

Mif13

Задача Mif 13. Фазовая диаграмма воды

Фазовая диаграмма воды

Фазовая диаграмма воды

Условие

По заданным значениям температуры [latex]t[/latex]и давления [latex]p[/latex] определите в каком состоянии находится вода. Для решения воспользуйтесь фазовой диаграммой воды и её приближённым описанием.

Тесты

Входные данные Выходные данные
[latex]p[/latex](Па) [latex]t[/latex](К)
0 0 Solid
103856284537 623 Solid
302758463 333 Liquid
423 600 Vapor
8827443265 891 Supercritical water

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

Нажмите здесь, чтобы выполнить этот код.

Решение

Пользуясь фазовой диаграммой воды, сравниваем значение введённого [latex]p[/latex](Па) и [latex]t[/latex](К) со значениями, при которых вода в жидком, твёрдом. газообразном и сверхкитическом жидком состоянии.

 

 

 

e-olymp 388. Превращение

Задача e-olimp.com №388

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

Условие

Возьмем какое-нибудь натуральное число [latex]N[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы всегда получаем число 1. Например, из числа 11 получается число 12, затем 6, 3, 4, 2 и, наконец, 1. Таким образом, для получения 1 из 11 нужно проделать 6 изменений.

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

Число N (1  ≤ N ≤  109).

Тесты

Входные данные(N) Выходные данные
11 6
43 9
1 0

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

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

Решение

Пусть [latex]N[/latex] — это число, которое мы будем изменять, а [latex]counter[/latex] — количество превращений. Цикл должен выполняться до того момента, пока [latex]N \neq 1[/latex]. Чтоб проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число — чётное, то делим его на 2, в противном случае — добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.

ML13

Условие:

Дана сторона равностороннего треугольника. Найти площадь этого треугольника.

Тесты:

Входные данные Выходные данные
5 2.1650635094
1.7237891231 0.74642258566
9223372036854773806 3.9938372461e+18

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

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

Решение:

Пусть [latex]a[/latex] — длина стороны равносторонннего треугольника, а [latex]s[/latex] — площадь. Тогда [latex]s = \frac{a^2\sqrt{3}}{4}[/latex].

Формула для нахождения площади равностороннего треугольника.

e-olymp 67. New food for Anfisa — 2

Задача e-olimp.com №67

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

Условие:

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

Тесты

Входные данные Выходные данные
a b c
2 3 4 23
1 2 3 5

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

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

Решение

При разрезании сторон a, b, c мы получаем a, b, c количество частей соответственно. Следовательно, при разрезании стороны A, мы выполняем [latex](a-1)[/latex] разрезов. Тогда, при разрезании стороны B, делаем [latex]a*(b-1)[/latex]; при разрезании стороны C — [latex]a*b*(c-1)[/latex] соответственно. Всего мы совершаем [latex](a-1)+a*(b-1)+a*b*(c-1)[/latex] разрезов. В итоге, получаем формулу [latex]a*b*c — 1[/latex].