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

Задача

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

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

Первая строка содержит количество элементов в массивеn (1n106). Во второй строке находится n чисел – элементы ai (1ai109) массива. В третьей строке находится количество запросовm (1m 105). Далее в m строках находится по три числа q, l, r (1lrn). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.

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

Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.

Решение

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

Код

Тесты

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

Задача взята отсюда.

Решенная задача на e-olymp.

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

 

A293

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex].
Если в данной последовательности ни одно четное число не расположено после нечетного,
то получить все отрицательные члены последовательности, иначе –все положительные. Порядок следования чисел в обоих случаях заменяется на обратный.

Тесты

Входные данные Выходные данные
-1 -4 5 7 7 5
1 2 3 4 5 -6 5 4 3 2 1
2 1 1 1 1

 Алгоритм

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

Код

MLoop7

Задача

Вычислите с точностью \epsilon значение функции f\left( x \right) = \tan x. При вычислениях допустимо использовать только арифметические операции.

Решение

Функцию [latex]f(x)=\tan x [/latex] можно представить в виде: [latex]f(x)=\frac{\sin x}{\cos x}[/latex] (по свойствам тангенса). Поэтому будем раскладывать в ряд две функции: [latex]\sin x[/latex] и [latex]\cos x[/latex].

Для решения задачи необходимо воспользоваться формулой Тейлора  с опорной точкой x_{0}=0 (ряд Маклорена). Для функции [latex]f(x)=\sin x[/latex]  она имеет следующий вид:

[latex]f(x)=x-\frac{x^{3}}{3!}+\frac{x^{5}}{5!}-\cdots=\sum_{n=0}^{\infty}(-1)^{n}\frac{x^{2n+1}}{(2n+1)!}[/latex]

А для [latex]f(x)=\cos x[/latex]:

[latex]f(x)=1-\frac{x^{2}}{2!}+\frac{x^{4}}{4!}-\cdots=\sum_{n=0}^{\infty}(-1)^{n}\frac{x^{2n}}{(2n)!}[/latex]

Далее нам нужно найти рекуррентные формулы для членов данных рядов.

[latex]\frac{a_n}{a_n-_1}=\frac{-x^{2}}{(2n+2)(2n+3)}[/latex];

[latex]\frac{b_n}{b_n-_1}=\frac{-x^{2}}{(2n+1)(2n+2)}[/latex]

При помощи функции fmod удалим период, так как тангенс [latex]\pi[/latex] периодичная функция.

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

Код

 

Тесты

Входные данные Выходные данные
0.42 0.001 0.446569
1.52 0.001 19.9377
3.1415 0.0001 -0.000113798

Задача взята отсюда.

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

e-olymp 2166: Анаграммы

Задача

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

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

Два слова заданы в отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

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

Следует вывести «YES«, если введенные слова являются анаграммами друг друга и «NO» если нет.

Решение 1

В данной задаче требуется определить являются ли два введенных слова анаграммами. Для этого заведем две отдельные строки и считаем их.
Основная проблема состоит в том, что буквы находятся в словах на различных позициях и это мешает нам просто сравнить строки. Поэтому упорядочим символы в строке, например, по возрастанию с помощью встроенной функции sort().
Теперь мы можем выполнить сравнение строк с помощью функции strcmp(), которая вернет нам 0 только в том случае, если строки идентичны. В таком случае и выводим «YES», а в противном случае «NO».

 

Код(строки c-string)

Решение 2

Решение аналогично, но нам не нужно теперь использовать функцию strcmp(), а мы просто сравниваем получившиеся строки, смотрим равны ли они, если да, то выводим «YES», а в противном случае «NO».

Код (строки string)

Тесты

 

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

marsh

 YES
ananas

nnaass

NO
tommarvoloriddle
iamlordvoldemort
YES

Задача взята отсюда.

Решенная задача на e-olymp.

Код на Ideone.com: c-string, string.

 

MLoops2

Задача

Найти закономерность и написать программу, которая выводит аналогичную таблицу для любых чисел n > 0 (количество столбцов) и m > 0 (количество строк).

-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*

Решение

Для того, чтобы решить поставленную задачу, нужно сначала понять закономерность чередования символов — и * в таблице. Каждый символ имеет свой номер строки([latex]m[/latex]) и столбца([latex]n[/latex]), а чтобы определить их номера зададим счетчики [latex]i[/latex] и [latex]j[/latex]. Задача состоит из того, что нужно определить закономерность появления символа [latex]-[/latex], в остальных случаях нужно выводить символ [latex]*[/latex]. Символ [latex]-[/latex] чередуется с символом [latex]*[/latex],  и поэтому можно увидеть, что этот символ [latex]-[/latex] ставится на место, при котором сумма номеров столбцов и строк делится нацело на 2. Решить данную задачу можно с помощью тернарной операции.

Код

Тесты

Входные данные 10 10 8 5 25 8
Выходные данные -*-*-*-*-*
*-*-*-*-*-
-*-*-*-*-*
*-*-*-*-*-
-*-*-*-*-*
*-*-*-*-*-
-*-*-*-*-*
*-*-*-*-*-
-*-*-*-*-*
*-*-*-*-*-
-*-*-*-*
*-*-*-*-
-*-*-*-*
*-*-*-*-
-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*

Задача взята отсюда.

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

e-olymp 931. Отношение произведения к сумме

Задача

Вычислить отношение произведения цифр натурального числа к их сумме.

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

Натуральное число [latex]n[/latex], не превышающее 2·109.

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

Вывести отношение произведения цифр числа [latex]n[/latex] к их сумме с 3 десятичными цифрами.

Решение

Для решения поставленной задачи нам нужно выделить отдельные цифры в записи данного числа, чтобы сосчитать их произведение и сумму. Для этого прочитаем это число из входного потока данных и реализуем разбиение числа на цифры с помощью цикла while.  Благодаря остатку от деления числа на 10 получаем последнюю цифру текущего числа, затем делим это число на 10. Если полученное число не 0, повторяем все действия, постепенно накапливая произведение и сумму. Найденные значения произведения и суммы цифр данного числа разделим, предварительно воспользовавшись явным преобразованием к типу double. Это и будет ответом, но так как в задаче указано вывести ответ с тремя десятичными цифрами, я использовала функцию <code>setprecision(3)</code>. В итоге получаем решение этой задачи.

Код

 

Тесты

Входные данные Выходные данные
36 2.000
3456 20.000
1645 7.500

Задача взята отсюда.

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