e-olymp 4481. В стране невыученных уроков

Задача

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

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

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

Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].

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

Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.

Тесты

Входные данные: Выходные данные:
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 5
2
2
5
1

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

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

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

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

Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

e-olymp 1455. Цикл

Задача

Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

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

Первая строка содержит количество вершин графа n (1n100). В следующих n строках находится по n чисел — матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

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

В первой строке выведите «YES«, если цикл существует, или «NO» в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковыми первую и последнюю) и в третьей строке — вершины, входящие в этот цикл в порядке обхода. Если циклов несколько — выведите любой.

Тесты

Входные данные Выходные данные:
2
0 -1
-1 0
YES
3
1 2 1
4
0 2 0 9
2 0 6 0
0 6 0 -3
9 0 -3 0
YES
3
3 4 3
3
0 2 3
2 0 1
3 1 0
NO

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

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

Для решения данной задачи задействован алгоритм Беллмана-Форда, который позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов. Создадим вектор, который будет содержать в себе элементы матрицы смежности графа. По определению смежных вершин графа, учитывая условие задачи (если ребра нет, соответствующее значение равно [latex]100000[/latex]), заполним этот вектор. Далее будем использовать алгоритм Беллмана-Форда. Если алгоритм даст отрицательный ответ на вопрос задачи, то выводим NO. Если цикл все-таки существует, то выводим YES. В вектор записываем вершины, входящие в цикл отрицательного веса. Далее выводим их количество, а затем и сами вершины в порядке обхода.

Для получения подробной информации об алгоритме Беллмана-Форда можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

e-olymp 6127. Очередь неограниченного размера

Задача

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

push n

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

pop

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

front

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

size

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

clear

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

exit

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

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

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

Тесты 

Входные данные Выходные данные:
1 push 1
front
exit
ok
1
bye
2 size
push 1
size
push 2
size
push 3
size
exit
0
ok
1
ok
2
ok
3
bye

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

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

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

Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

 

 

 

A304

Задача
Даны действительные числа [latex]a_{1},a_{2},\cdots[/latex] (читать до конца входного потока). Переставить члены последовательности так, чтобы сначала расположились все ее неотрицательные члены, а потом  — все отрицательные. Порядок как среди неотрицательных членов, так и среди отрицательных должен быть сохранен прежним.
Код программы

Тесты

Test № Input Output
1 -23 45 17 -78 0 34 45 17 0 34 -23 -78
2 -56 -56.34 0.2 56 9 0.2 56 9 -56 -56.34
3  -1 3 2 1 0 -3 -2 3 2 1 0 -1 -3 -2
4 -0.333 -1 0 1 0 -2 0 2 0 1 0 0 2 -0.333 -1 -2
5 9 -9 0 -96 -11 27 -13 9 0 27 -9 -96 -11 -13

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

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

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

 

A279

Задача

Даны действительные числа [latex]a_{1},[/latex] … [latex], a_{n},[/latex] [latex]b_{1},[/latex] … [latex], b_{n}[/latex]. Вычислить [latex](a_{1} + b_{n})(a_{2} + b_{n-1})[/latex] … [latex](a_{n} + b_{1})[/latex].
Тесты
Test № Input Output
1  1 2 3 4 5 6  343
2  1 1 1 1  4
3  0.5 0.1 0.07 -4 7 13  -376.691
4  0 0 0 0 0 0 0 0  0
5  0.4 0.3 2 -1 0.7 0.6  1

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

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

 Считываем все действительные числа до конца входного потока и записываем их в один вектор c. Далее работаем по такому алгоритму: складываем первый элемент вектора с последним, а полученный результат умножаем на переменную result, значение которой изначально равно единице, т.к, единица  — нейтральный элемент при умножении. Далее складываем второй элемент вектора с предпоследним, а полученный результат снова умножаем на переменную result и т.д. Так делаем до тех пор, пока не дойдем но середины вектора  c. Затем выводим полученное значение переменной  result.

MLoops 11

Задача

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

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

Три числа: количество столбцов и строк, параметр [latex]k[/latex].

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

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

Решение:

Для построения данной таблицы нужно найти закономерность чередования символов в таблице. Решение данной задачи можно осуществить с помощью двух циклов. Первый отвечает за строки, а второй — за столбцы. Пусть нумерация строк и столбцов начинается с нуля. Тогда, если номер строчки нацело делится на [latex](k+1)[/latex], то рассматриваем столбцы этой строчки. Если номер столбца нацело делится на [latex](k+1)[/latex], то записываем «+», иначе «-«. Если номер строки не делится нацело на [latex](k+1)[/latex], а номер столбца в этой строке — делится, то записываем «|». Если номер строки и столбца не делятся нацело на [latex](k+1)[/latex], то создаем переменную, с помощью которой будем заполнять таблицу цифрами. Так как, каждый столбик и каждая строка имеют свой номер, то с помощью нахождения суммы остатка от деления строки и столбца на [latex](k+1)[/latex] будем находит значение элемента, стоящего на пересечении [latex]i- [/latex]ой строки и [latex]i-[/latex]ого столбца, но этого не достаточно, в таблице есть перестановка, чтобы ее реализовать отнимаем от суммы единицу, делая этим сдвиг вправо. Также от полученного результата нужно найти остаток от деления на параметр [latex]k[/latex] для того, чтобы выполнялась правильная последовательность символов. Если результат вычисления переменной равен нулю, то записываем значение параметра [latex]k[/latex], иначе — результат вычисления переменной.

Тесты:

m n k

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

5 5 10
 
 14 13  5
 
 9  7  5
 
 17  30 7
 

 

 

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

MLoop 10

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

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

Для нахождения значения функции  f\left( x \right) = \text{ch}x (гиперболический косинус) с точностью [latex]\varepsilon[/latex]  воспользуемся формулой Тейлора (разложение функции в бесконечную сумму степенных функций):[latex]chx=1+\frac{x^2}{2}+\frac{x^4}{4}+[/latex]…[latex]=\sum_{n=0}^{\infty}\frac{1}{(2n+1)!}\times x^{2n}[/latex]. [latex]x_n=\frac{1}{(2n+1)!}\times x^{2n}[/latex], тогда [latex]x_{n-1}=\frac{1}{(2(n-1)+1)!}\times x^{2(n-1)}[/latex]. Рекуррентное соотношение [latex]x_n[/latex] и [latex]x_{n-1}=[/latex][latex]\frac{x_n}{x_{n-1}}=\frac{x^2}{2n\times(2n-1)}[/latex].

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

Тесты:

Входные данные Выходные данные
x e ch(x)
9 0.01 4051.54
16 0.0001 4.44306e+06
0.85 0.00001 1.38353
0.11 0.001 1.00606

Здесь можно посмотреть решение задачи на ideone.com

Mif 17.8

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

17_8

Решение:

Фигура, изображенная на рисунке, ограничена двумя дугами окружностей с центрами в начале координат. Для того, чтобы точка принадлежала ей необходимо, чтобы ее ордината была больше либо равнялась двум, а также, чтобы  выполнялись такие неравенства: [latex]{x}^{2}+{y}^{2}>=16[/latex] и [latex]{x}^{2}+{y}^{2}<=36[/latex], где [latex]16[/latex] и [latex]36[/latex] — радиусы двух окружностей, возведенные в квадрат по формуле.

Код:

Тесты:

x y Результат
0 0 NO
-1 4 YES
6 -2 NO
2.5 3 NO

Тут можно посмотреть решение задачи на ideone.com

Mif 12

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

Банк предлагает три вида депозитов на 3 месяца (p_3% годовых), на 6 месяцев (p_6% годовых) и на 12 месяцев (p_{12}% годовых). Какой депозит принесёт больше дохода при многолетнем вложении.

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

Для решения данной задачи нужно использовать формулу вычисления сложных процентов: [latex]{(1+\frac{p}{100\%})}^n[/latex], где [latex]p-[/latex]процентная ставка за расчетный период, а [latex]n-[/latex]количество расчетных периодов. Для депозита на [latex]3[/latex] месяца получаем формулу [latex]{(1+\frac{p_3}{4\times100\%})}^4[/latex], для депозита на [latex]6[/latex] месяцев получаем формулу [latex]{(1+\frac{p_6}{2\times100\%})}^2[/latex], для депозита на [latex]12[/latex] месяцев получаем формулу [latex](1+\frac{p_{12}}{100\%})[/latex]. Программа будет сравнивать полученные результаты и выводить максимальный.

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

Тесты:

Входные данные Выходные данные Входные данные Выходные данные
Срок вклада Ставка(%) Прибыль Выгода Срок вклада Ставка(%) Прибыль Выгода
 3 месяца  1  1.01004   3 месяца  10  1.10381
 6 месяцев  10  1.1025  6 месяцев  20  1.21
 12 месяцев  30  1.3  На 12 месяцев  12 месяцев  30  1.3  На 12 месяцев

 

Входные данные Выходные данные Входные данные Выходные данные
Срок вклада Ставка(%) Прибыль Выгода Срок вклада Ставка(%) Прибыль Выгода
 3 месяца  4  1.0406  На 3 месяца   3 месяца  1  1.01004
 6 месяцев  4  1.0404  6 месяцев  38  1.4161  На 6 месяцев
 12 месяцев  4  1.04  12 месяцев  9  1.09

 

Входные данные Выходные данные Входные данные Выходные данные
Срок вклада Ставка(%) Прибыль Выгода Срок вклада Ставка(%) Прибыль Выгода
 3 месяца  1  1.01004   3 месяца  11  1.11462
 6 месяцев  20  1.21  6 месяцев  5  1.05062
 12 месяцев  25  1.25  На 12 месяцев  12 месяцев 17  1.17  На 12 месяцев

Рассмотрим работу данной программы на реальных предложениях этого банка для депозитов «Плюс срочный» и «Стандарт срочный».

 Плюс срочный Входные данные Выходные данные  Стандарт срочный Входные данные Выходные данные
Срок вклада Ставка(%) Прибыль Выгода Срок вклада Ставка(%) Прибыль Выгода
 3 месяца  23.5  1.25653   3 месяца  22.5  1.24471
 6 месяцев  24.5  1.26001  На 6 месяцев  6 месяцев  23.5  1.24881  На 6 месяцев
 12 месяцев  25.5  1.255  12 месяцев 24.5   1.245

В результате получили, что эти оба депозита выгодны при сроке вклада на [latex]6[/latex] месяцев. По тестам видно, что депозит «Плюс срочный» при вкладе на  [latex]6[/latex] месяцев приносит большую прибыль, чем депозит «Стандарт срочный». Посчитаем, на сколько первый депозит выгоднее второго, для этого воспользуемся формулой: разница[latex]=[/latex](первый депозит[latex]-[/latex]второй депозит)[latex]\div[/latex]второй депозит[latex]\times{100\%}[/latex]. Подставив значения, получим  — на [latex]\approx0.89685\%[/latex].


Здесь
можно посмотреть решение задачи на ideone.com

e-olymp 11. Большая точность

Задача. Дана рациональная дробь [latex]\frac{m}{n}[/latex]. Запишите её в виде десятичной дроби с точностью [latex] k[/latex] знаков после запятой.

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

В одной строке записано 3 числа [latex]m,n,k[/latex]. [latex]{{0}<{m,n}\leq{100}}[/latex], [latex]{{0}\leq{k}\leq{1000}}[/latex].

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

Вывести [latex]k[/latex] точных значащих цифр после десятичной точки искомого числа.

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

Деление уголком

Деление уголком


Разделим [latex]m[/latex] на [latex]n[/latex] в столбик. Определим, сколько раз [latex]n[/latex] помещается в [latex]m[/latex]. Это будет целая часть частного. Умножим ее на [latex]n[/latex] и отнимем от [latex]m[/latex]. Таким образом получим остаток от деления. Будем умножать его на [latex]10[/latex] (эквиваленто сноске [latex]0[/latex]) и  проводить такую же операцию, как при нахождении целой части пока не закончится цикл. Так мы определим количество всех цифр после запятой, кроме последней. Последнюю будем находить в отдельном цикле для точности округления. Если идущая за ней цифра больше или равна [latex]5[/latex], то будем увеличивать ее на [latex]1[/latex], в противном случае — нет.

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

 

Проверка:

  1. (По условию задачи):
Ввод: # Вывод:
m 1 0.500
n 2
k 3

2.

Ввод: # Вывод:
m 2 0.66666666666666666667
n 3
k 20

3.

Ввод: # Вывод:
m 9 1.000000000
n 9
k 9

4.

Ввод: #
m 1 0.33333333333333333333
n 3
k 20

Здесь можно посмотреть решение на ideone.com

Здесь можно посмотреть  условие задачи на e-olymp.com

ML12

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

Даны [latex]x,y,z[/latex]. Вычислить  [latex] a = x \arctan{y} — e^{1-z}[/latex] и [latex] b = \frac{\sqrt{\left|3-x^2 \right|}- \sqrt[3]{\left|y-x \right|}}{1-\frac{x^2}{2}+\frac{y^2}{4}-\frac{z^2}{8}}.[/latex]

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

1)В условии задачи не указано какие должны быть числа [latex]x,y,z[/latex] , поэтому правильнее всего использовать диапазон long double, чтобы включить как можно больше значений.

2)Подключим библиотеку <cmath> , с помощью которой подключим математические функции и, придерживаясь правил порядка вычислений, расставим скобки.

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

Тесты:

Ввод: # Вывод: #
x 1 a 0.971813
y 2 b 1.10457
z 3
Ввод: # Вывод: #
x -9 a -16.1645
y 13 b 2.19263
z 0
Ввод: # Вывод: #
x 7 a 10.361
y 11 b -0.107389
z 21

Здесь находится код в ideone.com

e-olymp 7336. Пирожки

Условие задачи можно посмотреть здесь

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

Пирожок в столовой стоит [latex]a[/latex] гривен и [latex]b[/latex] копеек. Найдите сколько гривен и копеек заплатит Петя за [latex]n[/latex] пирожков.

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

Три натуральных числа [latex]a, b[/latex], [latex]n[/latex] [latex](0\leq a, b, n\leq 100)[/latex].

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

Через пропуск два числа: стоимость покупки в рублях и копейках.

Решение

Описание решения

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

Этой формулой мы считаем, сколько в копейках заплатил Петя за определенное количество пирожков:  [latex]p=(a\cdot 100 + b)\cdot n[/latex]

Далее, из количества копеек высчитываем количество гривен [latex]p/ 100[/latex] и с помощью деления по модулю находим количество копеек [latex]p\% 100[/latex], и выводим ответ на экран.

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

Для того, чтобы посмотреть, как работает программа со входными данными [latex]1, 25, 2,[/latex] нужно нажать сюда.