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].

Ссылки

 

Mif 17.12

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

Принадлежит ли точка [latex] (x;y) [/latex] фигуре на рисунке?17.12

Код

 

Тесты

Входные данные
Выходные данные
x y
9 0 No
-5 3 No
1 2 Yes
-3 5 Yes
1 -1 Yes
4 -4 No

Решение

  1. Сначала ищем длину отрезка ([latex] a [/latex]) от начала координат к точке [latex] (x;y) [/latex]  по формуле: [latex]\sqrt{{({x}_{0}-x)}^{2}+{({y}_{0}-y)}^{2}}[/latex], где              [latex]({x}_{0};{y}_{0})[/latex] — координаты начала координат.
  2.  Дальше проверяем, если [latex]a^{2}\leq 36[/latex] (т.е. точка находится в круге, т.к радиус четверти круга равен 6, а, возведя [latex]a[/latex] в квадрат, радиус также нужно возвести в квадрат) и [latex] (x;y) [/latex] находятся в первой четверти координат, то программа выводит «Yes» (можем возвести радиус ([latex] a=\sqrt{x^{2}+y^{2}} [/latex] )в квадрат,т.к. радиус не может быть отрицательным).
  3. Также, если сумма [latex] x + y [/latex] в четвертой четверти координат не превышает 6, то точка принадлежит треугольнику и программа выводит «Yes».
  4. В том случае, если тока не принадлежит фигуре, программа выводит «No».

Ссылки

 

Mif 1

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

Даны действительные числа [latex] x [/latex], [latex] y [/latex]. Получить [latex]\min (x, y)[/latex].

Код

Код (с тернарной операцией)

Тесты

Входные данные Выходные данные
[latex]x[/latex] [latex]y[/latex] [latex]\min (x, y)[/latex]
4 9 min=4
23 32 min=23
48 125 min=48
842 361 min=361
15 15 min=15

Решение

Вводим данные [latex] x [/latex], [latex] y [/latex]. Затем сравниваем их. Если [latex] x\leq y [/latex], то выводится [latex] x [/latex]. Иначе, то есть,если [latex] y < x [/latex], то выводится [latex] y [/latex].

Ссылки

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

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

ML16

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

На какую высоту [latex] h [/latex](в метрах) поднимется тело брошенное вертикально вверх со скоростью [latex] v [/latex] м/сек с поверхности планеты масса которой  [latex] m [/latex] кг а радиус [latex] R [/latex] м? Вращением планеты можно пренебречь.

Код

Тесты

v m R h
3 7 9 3.67092e+11
10 20 25 1.19867e+13
6 15 9 6.7425e+12
7 11 23 1.93122e+12

Решение

  1. Прямолинейное равноускоренное движение описывается двумя формулами: [latex]v=v_{0}+g \cdot t[/latex] (в этой формуле [latex] v_{0} [/latex] — начальная  скорость , а [latex] v [/latex] — текущая скорость) и [latex]h=v\cdot t-\frac{g \cdot t^{2}}{2}[/latex]. Однако, тело бросали вверх, следовательно,  произведение ускорения на время надо вычитать из начальной скорости:[latex]v=v_{0}-g \cdot t[/latex].
  2. В условии спрашивается на какую высоту [latex] h [/latex] (в метрах) поднимется тело брошенное вертикально вверх. Т.к тело начало равноускоренное движение из состояния покоя имеем: [latex] v_{0}=0 [/latex], отсюда получаем: [latex] v=0-g \cdot t[/latex] . Теперь можем выразить [latex] t [/latex]: [latex]t=-\frac{v}{g}[/latex].
  3. Подставляем   [latex] t [/latex] во вторую формулу. Получаем: [latex] h=\frac{v^{2}}{g}-\frac{v^{2}}{2\cdot g} [/latex], т.е [latex]h=\frac{v^{2}}{2\cdot g}[/latex].
  4. Остается только найти ускорение свободного падения ( [latex] g [/latex] ).Для этого нужно найти силу притяжения ([latex] F [/latex]).Согласно закону гравитации сила притяжения ([latex] F [/latex]), которая действует на тело массой [latex] M [/latex] возле поверхности планеты равна: [latex] F=\frac{G\cdot m\cdot M}{R^{2}} [/latex], где [latex] m [/latex]- масса планеты, [latex] R [/latex] — радиус планеты, а [latex] G [/latex] — гравитационная постоянная, которая равна: [latex] G=6.67408\cdot 10^{-11} [/latex].
  5. Согласно второму закону Ньютона: [latex] g=\frac{F}{M} [/latex]. Подставляем [latex] F [/latex] и получаем:[latex] g=\frac{G\cdot m}{R^{2}} [/latex].
  6. Теперь есть все составляющие для нахождения высоты: [latex] h=\frac{v^{2}\cdot R^{2}}{2\cdot G\cdot m} [/latex].

Ссылки

 

e-olymp 478. Белые кубики

Условие

Профессор Самоделкин задумал изготовить кубики из брусков белого цвета. Длина каждого ребра равна 1 дм. После изготовления кубиков профессор решил сделать все кубики также белого цвета. Сколько кубиков со стороной 1 дм сможет изготовить из одного бруска профессор, и сколько сторон придется ему покрасить, если известно, что длины сторон брусков — целые числа и заданы также в дециметрах.

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

В одной строке задано три целых числа – размеры бруска в дм, не превышающие 1000000.

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

В единственной строке записать через пробел два целых числа: количество полученных кубиков и количество граней кубиков, которые необходимо покрасить.

Код

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

Входные данные Выходные данные
1 1 2 3 6 14
2 1 1 2 2 2
3 2 2 2 8 24
4 3 4 5 60 266

Решение

Т.к. сторона изготовленных кубиков равна 1 дм, можем узнать их количество, найдя объём бруска по формуле:[latex] a \cdot b \cdot c[/latex]. Что бы узнать сколько сторон необходимо покрасить покрасить, нужно от количества всех сторон отнять уже окрашенные в белый цвет. Для нахождения всех сторон умножаем количество всех кубиков на количество сторон одного кубика: [latex]6 \cdot a \cdot b \cdot c[/latex]. Количество уже окрашенных сторон кубиков можно получить, узнав площадь поверхности бруска:            [latex] 2 \cdot (a \cdot b+a \cdot c+b \cdot c)[/latex]. Находим разность (кол-во неокрашенных сторон): [latex]a \cdot b \cdot c \cdot 6 — 2 \cdot (a \cdot b+a \cdot c+b \cdot c)[/latex].

Ссылки

Условие задачи на E-Olymp;

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

Подтверждение решения на E-Olymp.