Ю4.8

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

В массиве [latex]C(m)[/latex] заменить каждый третий элемент полусуммой двух предыдущих, а стоящий перед ним — полусуммой соседних с ним элементов.

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

1.Инициализируем переменную [latex]n[/latex], которая будет размером массива и сам массив [latex]a[/latex];
2.С помощью ввода задаем длину массива;
3.С помощью цикла и ввода заполняем массив;
3.Меняем каждый третий элемент начиная со второго;
4.Находим полусумму двух предыдущих элементов;
5.Берем число стоящее перед числом кратным трем;
6.Заменяем его на полусумму стоящих рядом элементов.

Тесты

Кол-во элементов Элементы Результат
3 5 9 1 5 3 7
6 8 7 6 9 4 0 8 7 7,5 9 4,5 6,5
9 2 5 7 3 6 9 4 6 2 4,5 3,5 3 6 4,5 4 5,5 5

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

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

А701б

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

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] c [latex]n[/latex] элементами. Получить вектор \[A^{2} \cdot b\]

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

Считываем матрицу. Возводим ее в квадрат ( перемножение матрицы осуществляется при помощи циклов). Считываем вектор. Умножаем матрицу на вектор. Выводим ответ.

Фактически, умножение матриц пишется по определению. Сумма произведений элементов строки на элементы столбцов.

Тесты

[latex]n[/latex] [latex]A[/latex] [latex]b[/latex] Результат
3 1 1 1
1 1 1
1 1 1
5 5 5 45 45 45
5 1 0 0 0 0
0 2 0 0 0
0 0 3 0 0
0 0 0 4 0
0 0 0 0 5
8 1 8 1 8 8 4 72 16 200
2 1 0
0 1
2 2 2 2

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

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

Ю1.19

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

Найти координаты вершины параболы \[y = ax^{2}+bx+c\]

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

Мы знаем координаты вершины параболы вычисляются по формулам:

1) \[x_{0} = — \frac{b}{2 \cdot a}\] 2) \[y_{0} = ax_{0}^{2}+bx_{0}+c\]

(Для простоты в программе [latex]x_{0}[/latex] и [latex]y_{0}[/latex] заменены на [latex]x[/latex] и [latex]y[/latex] соответственно).

Теперь учтем ситуации в проработке которых могут возникнуть сложности:
Если [latex]a=0[/latex], то график [latex]y(x)[/latex] не является параболой, о чем на должен проинформировать компилятор. Это все проблемы связанные с графиком.

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

Тесты

[latex]a[/latex] [latex]b[/latex] [latex]c[/latex] [latex]x[/latex] [latex]y[/latex] Комментарий
-1 -2 -3 1 -4 Пройден
0 2 2 Не пройден так график [latex]y(x)[/latex] не является параболой и программа оповещает об ошибке
1 0 4 0 4 Пройден
2 1 3 -0.25 2.875 Пройден

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

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

ML11

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

Определить время падения камня на поверхность земли с высоты [latex]h[/latex].

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

Для начала оговорим трактовку условия задачи.

1. Поскольку в условии ничего не говорится про начальную скорость камня, будем считать ее равной нулю.
2. Аналогично в условии ничего не говорится про точность результата. От этого зависит как округление до определенного количества знаков после запятой в выводе, так и то, с какой точностью следует указать ускорение свободного падения, поскольку каноны физики требуют, чтобы ответ на физическую задачу указывался с точностью наимение точно указанного в условии данного. В данном решении я взял значение [latex]g[/latex] свойственное Одессе с точностью 4 значка после запятой. Соответственно, ответ будет выводиться с такой же точностью.
3. Предполагается что высота и время должны указываться в СИ

Тогда наша рабочая формула выглядит следующим образом: \[\sqrt{\frac{2 \cdot h}{g}},\] где \[g = 9.8075 \frac{m}{s^{2}}\] Вводить в программе [latex]g[/latex], как отдельную переменную или константу нет смысла, т.к. она используется только раз. Поэтому в коде вместо [latex]g[/latex] стоит просто ее значение.

Тесты

Высота (м) Время (сек)
1 0 0
2 5 1.0098
3 20 2.0195
4 80 4.0391

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

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

e-olymp 419. Задача 3n + 1

Задача

Рассмотрим следующий алгоритм генерации последовательности чисел:

Например, для [latex]n = 22[/latex] будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сойдется к [latex]n = 1[/latex] для любого целого [latex]n[/latex]. По крайней мере, это предположение верно для всех целых [latex]n[/latex], для которых [latex]0 < n < 1,000,000[/latex].
Длиной цикла числа [latex]n[/latex] будем называть количество сгенерированных чисел в последовательности включая [latex]1[/latex]. В приведенном примере длина цикла числа [latex]22[/latex] равна [latex]16[/latex].
Для двух заданных чисел [latex]i[/latex] и [latex]j[/latex] необходимо найти максимальную длину цикла среди всех чисел между [latex]i[/latex] и [latex]j[/latex] включительно.

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

Каждый тест задается в отдельной строке и содержит пару целых чисел [latex]i[/latex] и [latex]j[/latex]. Входные числа будут меньше [latex]1000000[/latex] и больше [latex]0[/latex]. Считайте, что для вычислений достаточно использовать [latex]32[/latex] битный целочисленный тип.

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

Для каждой пары чисел [latex]i[/latex] и [latex]j[/latex] выведите числа [latex]i[/latex] и [latex]j[/latex] в том же порядке, в каком они поступили на вход. После чего выведите максимальную длину цикла среди всех целых чисел между [latex]i[/latex] и [latex]j[/latex] включительно. Для каждого теста три числа следует выводить в отдельной строке, разделяя одним пробелом.

Тесты

Входные данные Выходные данные
1 10
100 200
201 210
900 1000
1 10 20
100 200 125
201 210 89
900 1000 174
1 10
10 1
1 10 20
10 1 20
5 25
70 54
38 250
5 25 24
70 54 113
38 250 128

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

Решение

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

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp 1780. Коды Грея

Задача

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.

Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».

Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].

0
1

Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].

00
01
11
10

Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:

000
001
011
010
110
111
101
100

При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2^n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.

Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

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

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k (0 < k < 10^{18})[/latex] в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

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

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

Входные данные Выходные данные
1 3
14
5
12
2
9
7
10
2 10
50
15
43

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

Решение

Рассмотрим биты числа [latex]n[/latex] и биты числа [latex]G(n)[/latex]. Заметим, что [latex]i[/latex]-ый бит [latex]G(n)[/latex] равен единице только в том случае, когда [latex]i[/latex]-ый бит [latex]n[/latex] равен единице, а [latex]i+1[/latex]-ый бит равен нулю, или наоборот ([latex]i[/latex]-ый бит равен нулю, а [latex]i+1[/latex]-ый равен единице). Таким образом, имеем: [latex]G(n) = n \oplus (n>>1)[/latex], где [latex]\oplus[/latex] — операция «побитовое исключающее ИЛИ», а [latex]>>[/latex] — «побитовый сдвиг вправо».

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp 143. Точка и треугольник

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

Входные данные Выходные данные
1 2 6 -9 3 8 1 5 11 1
2 -13 10 -12 5 99 80 17 13 0
3 98 -50 -87 7 5 3 23 17 0
4 5 15 7 12 5 3 2 54 1
5 2 2 3 1 1 3 9 11 1

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

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

 

Ссылки

Ссылка на Ideone
Ссылка на e-olymp

e-olymp 51. К-домино

Задача

ДоминоРаботник отдела технического контроля любил выбраковывать «доминошки», которые содержали одинаковые значения. Так как на предприятии, выпускающем [latex]K[/latex]-домино, этого не знали, к нему постоянно поступали претензии на сумму, равную стоимости [latex]K[/latex]-домино. Стоимость [latex]K[/latex]-домино составляла ровно столько гривен, сколько было в купленном покупателем наборе доминошек.Для того, чтобы его не уволили с работы, работник ОТК выбраковывал иногда не только все не любимые «доминошки», а несколько больше, но не более половины гарантированно выбраковыванных.Зная сумму претензии, пришедшей на предприятие, установите, какой из наборов [latex]K[/latex]-домино был куплен покупателем.

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

Единственное число [latex]S[/latex] – сумма претензии, пришедшей на предприятие, [latex]S ≤ 2000000000[/latex].

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

Единственное число – индекс [latex]K[/latex] купленного покупателем [latex]K[/latex]-домино.

Входные данные Выходные данные
1 5 3
2 10 4
3 1000000 1414
4 555666777888 1054198
5 13 5

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

Решение

[latex]K[/latex]-домино — набор домино с минимальным количеством точек на одной из половин доминошки.
Количество дублей, то есть количество точно выбракованных доминошек — [latex]k[/latex]+1. Общее количество доминошек [latex]k[/latex]-домино:$$(k+1){{k+2}\over{2}}$$
Пусть работник дополнительно выбраковывал [latex]e[/latex] доминошек. [latex]s[/latex] — сумма претензии, тогда имеем:

[latex]k+1+e+s= (k+1){{k+2}\over{2}}[/latex]  
[latex]k^2<=2s+1[/latex]  
[latex]k=[\sqrt{2s+1}][/latex]

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp4491 Трое из Простоквашино

Условие задачи:
— Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
— Подожди, Шарик, я занят.
— Ну Дядя Федор, ну смотри какой я код написал:

— Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из [latex]n[/latex] неотрицательных чисел и число [latex]k[/latex], а ты мне скажешь сколько существует таких пар [latex]l;r \left ( 1\leq l\leq r\leq n \right ),[/latex] что функция, вызванная следующим образом:

[latex]get[/latex]_[latex]max(1, 1, n, l, r)[/latex]

вернет значение равное [latex]k[/latex]. Можно считать, что перед этим была вызвана функция

[latex]build(1, 1, n)[/latex]

— Хорошо, Дядя Федор!

Входные данные:
В первой строке находятся число [latex]n \left ( 1\leq n\leq 10^{6} \right )[/latex] — количество элементов в массиве и [latex]k \left ( 1\leq k\leq 10^{9} \right )[/latex] — значение, которое должна вернуть функция. В следующей строке находится [latex]n[/latex] неотрицательных чисел, не превышающих [latex]10^{9}[/latex] — элементы массива.

Выходные данные:
Выведите единственное число – ответ на задачу.

Тесты:

Входные данные Выходные данные
[latex]n[/latex] [latex]k[/latex] [latex]elem[/latex]_[latex]tree[][/latex] [latex]ans[/latex]
5 3 1 2 3 2 3 11
10 6 1 4 7 6 2 4 1 9 6 6 7
20 15 5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6 43

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

Алгоритм решения:
Зададим отрезок массива, на котором обозначим границы [latex]\left [ left, right \right ][/latex]. Инициализируем изначально оба конца нулем. Рассмотрим некоторое [latex]elem\_tree\left [ i \right ][/latex] на нашем сегменте. Тогда если [latex]elem\_tree\left [ i \right ]=k[/latex], то на всем отрезке от [latex]left[/latex] до [latex]i[/latex] максимумом будет [latex]k[/latex]. Увеличим в таком случае [latex]left[/latex] и сделаем его равным [latex]i[/latex], причем [latex]right=0.[/latex] Если [latex]elem\_tree\left [ i \right ]\lt k[/latex], максимум будет также равен [latex]k[/latex]. В таком случае увеличиваем только [latex]right.[/latex] Если же [latex]elem\_tree\left [ i \right ]\gt k[/latex] , то [latex]left[/latex] устанавливаем равным [latex]i+1[/latex], а [latex]right[/latex] обнуляем.
Пройдя по всему массиву, мы должны получить значения [latex]left[/latex] равное количеству пар в которых максимум равен [latex]k[/latex], а [latex]right[/latex] должно стать равным нулю.

Код программы на Java
Условие задачи

e-olymp 1388. Заправки

Задача с сайта e-olymp.com.

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

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

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

Сначала идет количество городов n (1 ≤ n ≤ 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

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

Выведите одно число — суммарную стоимость маршрута или -1, если добраться невозможно.

Тесты

Входные данные Выходные данные
1 4
1 10 2 15
4
1 2 1 3 4 2 4 3
3
2 4
1 10 2 15
0
-1
3 5
1 2 3 4 5
4
1 2 2 3 3 4 4 5
10

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

Описание

Оптимальную стоимость маршрута будем находить по алгоритму Дейкстры. Цены на бензин в i-ом городе хранятся в массиве price. Минимальные стоимости маршрутов к каждому из городов хранятся в массиве distance, изначально все маршруты принимаем бесконечно дорогими. Кроме того, для хранения информации о том, был ли рассмотрен i-й город, используется массив used. Сам граф представляется в виде списка смежности. Для этого используется массив векторов graph. Если в итоге стоимость маршрута до целевого города осталась бесконечной, значит, пути к нему не существует, и выводится -1. Иначе выводится эта стоимость.

Код на ideone.com.

Засчитанное решение на e-olymp.com.