e-olymp 4082. Произведение на отрезке

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

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [latex] n [/latex] целых чисел [latex] x_{1}, x_{2},\cdots , x_{n} [/latex]. Потом следует  [latex] k [/latex] раундов, на каждом из которых выполняется одна из следующих команд:

  • команда изменения, когда необходимо изменить одно значение в последовательности;
  • команда умножения, когда по заданным значениям [latex] i [/latex] и [latex] j [/latex] необходимо определить, является ли произведение [latex] x_{i}\cdot x_{i+1} \cdot \; \; \cdots \; \; \cdot x_{j-1} \cdot x_{j} [/latex] положительным, отрицательным или равным нулю.

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

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

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа [latex] n [/latex]  и [latex] k [/latex]   ([latex] 1\leq n,k\leq 10^{5}[/latex]) — количество элементов в последовательности и число раундов в игре. Вторая строка содержит [latex] n [/latex] целых чисел [latex] x_{i} [/latex] — начальные значения последовательности ([latex] -100\leq x_{i}\leq 100[/latex] для [latex]i=1,2, \cdots ,n[/latex]). Каждая из следующих [latex] k [/latex]  строк описывает команду, начинающуюся заглавной буквой  [latex] C [/latex] или [latex] C [/latex]. Если это буква [latex] C [/latex], то строка содержит команду замены, за буквой следуют два числа [latex] i [/latex] и [latex] v [/latex], указывающих на то что [latex] x_{i} [/latex] необходимо заменить на [latex] v [/latex] ([latex] 1\leq i\leq n[/latex] и [latex]-100\leq v\leq 100[/latex]). Если это буква [latex] P [/latex], то строка задает команду умножения, за буквой следуют два числа [latex] i [/latex] и [latex] j [/latex] — необходимо вычислить произведение от [latex] x_{i} [/latex] до [latex] x_{i} [/latex] включительно ([latex] 1\leq i\leq j\leq n [/latex]) . Каждый тест содержит как минимум одну команду умножения.

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

Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. [latex] i [/latex]-ый символ строки является результатом [latex] i [/latex]-ой команды умножения. Если произведение положительно, то вывести символ [latex] + [/latex] (плюс); если произведение отрицательно, то вывести [latex] — [/latex] (минус); если произведение равно нулю, то вывести [latex] 0 [/latex] (ноль).

Тесты

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

-2 6 0 -1

C 1 10

P 1 4

C 3 7

P 2 2

C 4 -5

P 1 4

5 9

1 5 -2 4 3

P 1 2

P 1 5

C 4 -5

P 1 5

P 4 5

C 3 0

P 1 5

C 4 -5

C 4 -5

0+-

+-+-0

5 5

10 -2 0 5 1

C 1 0

P 1 4

C 2 7

P 1 1

C 2 0

00
6 4

0 20 0 30 0 -10

P 2 2

P 2 3

P 3 6

P 2 6

4 3

0 -1 -2 0

P 2 3

C 1 9

P 1 2

3 3

5 2 0

C 1 7

C 3 0

C 1 0

6 5

100 10 55 11 0 -33

P 1 4

C 5 6

C 3 72

C 5 -20

P 5 6

+000

+-

 

++

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

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте e-maxx). Следовательно, при построении дерева сначала считывается массив, а после выполняется построение дерева (от корня). В том случае, если функция, строящая дерево, вызывалась от листа,  все значения элементов массива записываются в дерево как [latex]1[/latex], если элемент больше нуля, если меньше нуля, то записывается как [latex]-1[/latex], а в случае равенства элемента нулю, он записывается [latex]0[/latex] (нулём).  В ином случае (если функция вызывалась не от листа), она начинает вызываться рекурсивно от каждого из двух сыновей и перемножает вычесленные значения.

Для выполнения функции изменения элемента ей (функции) передаётся текущая вершина. Затем выполняется вызов из сына, сожержащего элемент с данным номером. Таким образом процесс доходит до листа, которому и присваевается значение. При чём, аналогично построению дерева, элементы записываются как [latex]1[/latex],[latex]-1[/latex] или же [latex]0[/latex].

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

Далее  (в программе) идёт процесс построения дерева и выполнение действий, удовлетворяющих команды, описанные в уловии задачи.

Ссылки

  • Рабочий код на Ideone.com
  • Засчитанное решение на e-olymp.com
  • При ришении данной задачи был использован материал по структурам данных «дерево отрезков» с сайта e-maxx.ru
  • Задача взята с сайта e-olymp.com

A287

Задача A287

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

Даны целые числа [latex] a_{1}\dots a_{n} [/latex]. Все члены последовательности с четными номерами, предшествующие первому по порядку члену со значением [latex] max(a_{1}\dots a_{n}) [/latex], домножить на  [latex] max(a_{1}\dots a_{n}) [/latex].

Тестирование

Входные данные Выходные данные
1. 1 2 3 4 3 2 1 1 8 3 4 3 2 1
2. 1 2 3 4 4 2 5 5 3 3 2 1 1 10 3 20 4 10 5 5 3 3 2 1
3. 11 4 6 7 9 11 4 6 7 9
4. 9 8 10 1 2 4 5 4 6 13 9 104 10 13 2 52 5 52 6 13
5. -10 -4 -6 -7 -3 0 -1 -20 -10 0 -6 0 -3 0 -1 -20

Реализация

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

Считываем все целые числа до конца входного потока и записываем их в вектор [latex] a [/latex]. Затем:

  1. Сравниваем между собой каждый элемент вектора, и если находится большее значение, то запоминается номер данного элемента.
  2. Далее проходим все члены последовательности, предшествующие первому по порядку члену с максимальным значением.
  3. Умножаем все элементы с четными номерами на  [latex] max(a_{1}\dots a_{n}) [/latex].

Ссылки

Код на ideaone.

e-olymp 494. Гласные

Условие

К гласным буквам в латинском алфавите относятся буквы A, E, I, O, U и Y. Остальные буквы считаются согласными. Напишите программу, считающую количество гласных букв в тексте.

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

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

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

В выходной файл вывести одно целое число – количество гласных во входном тексте.

Код

Код с функцией strpbrk()

Решение

Объявляется инициализированная строка, в которой может поместиться шесть символов, а последнее, седьмое место отводится под нуль-терминатор. Далее считываются все веденные символы, включая пробелы. Сравнивается  первый элемент строки с каждым элементом считываемых символов. Если считываемый символ соответствует символу строки, то увеличиваем количество гласных на единицу и так далее для всех гласных букв. Когда первый элемент строки сравнили со всеми считываемыми символами, начинаем так же сравнивать каждый последующий элемент.

Реализация с использованием string

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

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

Тестирование

Входные данные Выходные данные
1 COBBRA 2
2 REE BA 3
3 U GFD 1

Ссылки

 

MLoops8

Задача

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

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

Два числа:количество столбцов и строк.

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

Таблица размером n*m со следующей закономерностью:

+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21

Код

Упрощенный вариант

 

Тесты

[latex]n[/latex] [latex]m[/latex] Выходные данные
1 1  +
7 7 +21++21

1++21++

+21++21

1++21++

+21++21

1++21++

+21++21

 

15 6  +21++21++21++21

1++21++21++21++

+21++21++21++21

1++21++21++21++

+21++21++21++21

1++21++21++21++

 

25 8 +21++21++21++21++21++21++

1++21++21++21++21++21++21

+21++21++21++21++21++21++

1++21++21++21++21++21++21

+21++21++21++21++21++21++

1++21++21++21++21++21++21

+21++21++21++21++21++21++

1++21++21++21++21++21++21

Решение

Для решения сначала нужно найти закономерность чередования символов в таблице. Пусть нумерация столбцов и строк будет начинаться с единицы, тогда, если строка [latex]i \vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 1 кратен 4 ([latex] (j+1)\vdots 4 [/latex]), то в данной строке и столбце находится «1», если же результат от прибавления номера столбца к 2 кратен 4([latex] (j+2)\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Если же строка [latex]i\vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 3 кратен 4 ([latex] (j+3)\vdots 4[/latex]), то в данной строке и столбце находится «1», а если номер столбца кратен 4([latex] j\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Ссылки

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

Упрощенный код

MLoop 24

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

Вычислите с точностью [latex]\varepsilon [/latex] сумму ряда [latex]\sum_{i=1}^{\infty} (-1)^{i}\cdot \frac{2^{i}}{\left ( 2\cdot i+1 \right )!} [/latex].

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

  1. В условии нужно найти сумму ряда,задан его общий член. Благодаря этому можно найти формулу, согласно которой каждый последующий член ряда выражается как предыдущий, умноженный на выражение: [latex]\frac{-2}{2 \cdot k + 3}[/latex].
  2. Вычисляется первый член ряда, предполагается, что он и будет равен сумме ряда, и этот член ряда сравнивается по модулю с заданной точностью [latex]\varepsilon [/latex].
  3. В случае, если требуемая точность не достигнута — подсчитывается следующий член ряда, он прибавляется к сумме и сравнивается по модулю с заданной точностью.
  4. Пункт 3 повторяется до тех пор, пока заданная точность не достигнута.

Код

Исправленный вариант

 

Тесты

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

(точность [latex]\epsilon [/latex])

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

(сумма ряда [latex]\sum_{i=1}^{\infty} (-1)^{i}\cdot \frac{2^{i}}{2\cdot i+1}[/latex])

e=1e-10 sum=-0.301544
 e=0.0001 sum=-0.301543
 e=0.001 sum=-0.301543
 e=0.01 sum=-0.301587
 e=0.1 sum=-0.3

Ссылки

e-olymp 916. Интересное произведение

Условие

Определить все возможные значения произведения [latex]i\cdot j[/latex], если целочисленные значения переменных [latex]i[/latex] и [latex]j[/latex] меняются соответственно  [latex]i[/latex]  от [latex]a[/latex] до [latex]b[/latex] и [latex]j[/latex] от [latex]c[/latex] до [latex]d[/latex] ([latex]1\leq a,b,c,d\leq 10[/latex]).

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

В одной строке заданы 4 числа [latex]a,b,c,d[/latex] ( [latex]a[/latex] может быть больше [latex]b[/latex],  [latex]c[/latex] может быть больше [latex]d[/latex] ).

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

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

Код

 

Тестирование

Входные данные Выходные данные
1 1 10 1 10 42
2 7 2 4 1  18
3 2 7 1 4 18
4 3 9 2 4 16

Решение

Для нахождения всех возможных результатов произведения без повторений [latex]i\cdot j[/latex] будем проверять каждое число [latex] p [/latex] (которое находится в диапазоне от  произведения минимальных значений [latex] i [/latex] и [latex] j [/latex] до произведения их максимальных значений) на то, возможно ли его получить при помощи данного произведения. Если получить число хотя бы один раз, перемножив [latex] i [/latex] и [latex] j [/latex], реально,тогда значению [latex] flag [/latex] присваиваем 1. Если [latex] flag [/latex] присваивается 1, тогда  [latex] rez [/latex] увеличивается на 1. В результате выводим итоговое [latex] rez [/latex].

Ссылки