e-olymp 1060. Линии

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

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

В таблице из [latex]n[/latex] строк и [latex]n[/latex] столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.

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

В первой строке находится число [latex]n \left (2\leq n\leq 40 \right )[/latex], в каждой из следующих [latex]n[/latex] строк — по [latex]n[/latex] символов. Символом точки обозначена свободная клетка, латинской заглавной [latex]O[/latex] — шарик, [latex]@[/latex] — исходное положение шарика, который должен двигаться, латинской заглавной [latex]X[/latex] — конечное положение шарика.

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

В первой строке выводится [latex]Y[/latex], если движение возможно, или [latex]N[/latex], если нет. Если движение возможно далее следует [latex]n[/latex] строк по [latex]n[/latex] символов — как и на вводе, но [latex]X[/latex], а также все точки на пути заменяются плюсами.

Тесты

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

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

ideone.com

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

Решение

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

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

e-olymp 2941. Дима и массив

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

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

Мама подарила мальчику Диме массив длины [latex]n[/latex]. Массив этот не простой, а особенный. Дима может выбрать два числа [latex]i[/latex] и [latex]d[/latex] ([latex]1\leq i\leq n[/latex], [latex]-1000\leq d\leq 1000[/latex]), и элемент с индексом [latex]i[/latex] магически становится равным [latex]d[/latex]. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex]? Дима легко справился с этими вопросами, сможете ли Вы?

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

В первой строке находятся два целых числа [latex]n[/latex] и [latex]q[/latex] [latex]1\leq n\leq 5\cdot 10^{5},~1\leq q\leq 10^{5}[/latex] — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано [latex]n[/latex] чисел [latex]a_{1},a_{2},\ldots,a_{n}[/latex] [latex]\left ( -1000\leq a_{i}\leq 1000 \right )[/latex] — начальное состояние массива. В следующих [latex]q[/latex] строках заданы операции и запросы. Первый символ в строке может быть [latex]=[/latex] или [latex]?[/latex]. Если строка начинается с [latex]=[/latex], то это операция присваивания. Далее следуют [latex]i[/latex] и [latex]d[/latex], ограничения на которые описаны в условии. Если строка начинается с [latex]?[/latex], то это запрос. Далее следуют числа [latex]f[/latex] и [latex]t[/latex] [latex]\left (1\leq f,~t\leq n \right )[/latex].

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

Для каждого запроса выведите сумму чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex], по одному результату в строке.

Тесты

Входные данные Выходные данные
3 3
1 2 3
? 1 3
= 3 2
? 1 3
6
5
5 3
1 2 3 4 5
? 1 5
= 1 7
? 1 3
15
12
5 6
1 2 3 4 5
? 1 5
= 1 0
? 1 5
= 2 7
? 1 5
? 1 3
15
14
19
10

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

ideone.com

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

Решение

Для решения данной задачи необходимо воспользоваться структурой данных «дерево отрезков».

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

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

Для выполнения запроса суммы также используется рекурсивная функция. Она запускается либо от правого, либо от левого сына текущей вершины, если границы исходного запроса лежат в одном из их отрезков. Либо запускается от обоих сыновей, если границы исходного запроса принадлежат пересечению их отрезков, суммируя результаты двух запросов. Таким образом функция доходит до отрезка, границы которого совпадают с текущим запросом или до листа и возвращает их значение.

Для решения данной задачи были использованы материалы сайта e-maxx.ru.

e-olymp 1342. Периодические строки

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

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

Будем говорить, что символьная строка имеет период [latex]k[/latex], если она может быть образована путем объединения одной или нескольких одинаковых строк длиной [latex]k[/latex]. Например, строка «[latex]abcabcabcabc[/latex]» имеет период [latex]3[/latex], так как она может быть образована путём объединения [latex]4[/latex]-х строк «[latex]abc[/latex]». Она также имеет период [latex]6[/latex] (объединение двух строк «[latex]abcabc[/latex]») и [latex]12[/latex] (сама строка «[latex]abcabcabcabc[/latex]»).

Напишите программу определяющую наименьший период заданной строки.

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

В первой строке задано количество тестовых случаев [latex]N[/latex] во входных данных. Каждый тестовый случай размещен в отдельной строке и содержит не более [latex]80[/latex] символов без пробелов.

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

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

Тесты

Входные данные Выходные данные
2
HoHoHo
mama
2

2

2
abcdefg
abcabcabc
7

3

3
b
bbb
bbbbb
1

1

1

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

ideone.com

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

Решение

Строка длины [latex]s[/latex] может быть образована подстрокой, длина которой не превышает половины длины строки. Следовательно, период лежит в промежутке [latex]\left [ 1;s/2 \right ][/latex], либо равен длине строки. Последовательно разбивая строку на подстроки длиной от [latex]1[/latex] до [latex]s/2[/latex], проверяем равны ли они между собой. Если такие подстроки не нашлись, то период равен длине строки.

A294

С.А.Абрамов. Задачи по программированию.

Задача

Даны действительные числа [latex]r_{1},\ldots,r_{n}[/latex], среди которых заведомо есть как отрицательные, так и не отрицательные. Получить [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex], где [latex]x_{1},\ldots,x_{p}[/latex] — отрицательные члены последовательности [latex]r_{1},\ldots,r_{n}[/latex], взятые в порядке следования, [latex]y_{1},\ldots,y_{q}[/latex] — неотрицательные члены, взятые в обратном порядке, [latex]s=min\left ( p,q \right )[/latex] .

Тесты

 Входные данные Выходные данные
 -1 1  -1
 -1  0
-1 -1  0
 1 2 -5 10 -2  -54
 4 6 3 4 -8 2 7 5  -40

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

ideone.com

Решение

Считывая числа из входного потока, выполняем проверку и записываем положительные в вектор [latex]y[/latex], отрицательные — в вектор [latex]x[/latex]. Затем вычисляем [latex]s[/latex]. Вычисляем [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex].

e-olymp 2040. Обычная перестановка.

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

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

По заданным двум строкам a и b следует вывести такую строку x наибольшей длины, которая одновременно является подстрокой перестановки a и подстрокой перестановки b.

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

Состоит из нескольких тестов, каждый их которых содержит две строки. То есть строки 1 и 2 — это первый тест, строки 3 и 4 — второй тест и т.д. Каждая строка состоит из символов нижнего регистра, причём первой строкой в паре является a, а второй строкой b. Максимальная длина каждой строки 1000 символов.

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

Для каждого теста следует в отдельной строке вывести строку x. Если таких строк несколько, то вывести наименьшую в алфавитном порядке.

Тесты

Входные данные Выходные данные
walking
down
nw
the
street
 et
abcd
efg
abbcdd
badbc
 abbcd

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

ideone.com

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

Решение

Для решения данной задачи необходимо проходя по алфавиту, искать есть  ли текущая буква в обеих строках и удалять её. Если буквы нет одновременно в обеих строках, необходимо перейти к следующей букве алфавита.

MLoop 17

Задача

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

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

В одной строке заданы значение переменной [latex]x[/latex] и точность вычислений [latex]\varepsilon[/latex].
[latex]\left | x \right |< 1[/latex]

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

Значение функции в точке [latex]x[/latex] .

Тесты

[latex]\varepsilon[/latex] [latex]x[/latex]  [latex]ln(1-x^2)[/latex] Результат
0.001 0.5 [latex]ln(0.75)[/latex] -0.287435
0.0001 0.5 [latex]ln(0.75)[/latex] -0.287671
0.01 0.1 [latex]ln(0.99)[/latex] -0.01005
0.001 -0.1 [latex]ln(0.99)[/latex] -0.01005
0.1 0 [latex]ln(1.00)[/latex] 0
0.01 0 [latex]ln(1.00)[/latex] 0

 

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

ideone.com

 

Решение

Функцию [latex]f\left( x \right) = \ln \left( 1-x^2 \right)[/latex] можно представить в виде:
[latex]ln\left ( 1-x^2 \right )= ln\left ( 1-x \right )\left ( 1+x \right ) = ln\left ( 1-x \right )+ln\left ( 1+x \right )[/latex] (по свойствам логарифма).

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

[latex]ln\left (1+x\right )=x-\frac{x^{2}}{2}+\frac{x^{3}}{3}-\cdots+\frac{\left ( -1 \right )^{n-1}}{n}x^{n}=\sum_{n=1}^{\infty}\frac{\left (-1\right )^{n-1}}{n}x^{n}[/latex]

Подставив в формулу [latex]-x[/latex] вместо [latex]x[/latex] , получим:

[latex]ln\left (1-x\right )=-x-\frac{x^{2}}{2}-\frac{x^{3}}{3}-\cdots -\frac{x^{n}}{n}=-\sum_{n=1}^{\infty}\frac{x^{n}}{n}[/latex]

Тогда,

[latex]ln\left (1+x\right )+ln\left (1-x\right )=\sum_{n=1}^{\infty}\frac{\left (-1\right )^{n-1}}{n}x^{n}-\sum_{n=1}^{\infty}\frac{x^{n}}{n}=[/latex]

[latex]=\sum_{n=1}^{\infty }\left[\frac{\left (-1\right )^{n-1}}{n}x^{n}-\frac{x^{n}}{n}\right]=\sum_{n=1}^{\infty }\frac{x^{n}\left (\left (-1\right )^{n-1}-1\right )}{n}=[/latex][latex]=-x^{2}+0-\frac{x^{4}}{2}+0-\frac{x^{6}}{3}+0-\cdots[/latex]

Так как при нечетном [latex]n[/latex] члены данного ряда обращаются в ноль, его можно записать в виде:

[latex]-\sum_{0}^{\infty}\frac{x^{2n+2}}{n+1}=-x^{2}-\frac{x^{4}}{2}-\frac{x^{6}}{3}-\cdots-\frac{x^{2n+2}}{n+1}[/latex]

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

[latex]\frac{a_{n}}{a_{n-1}}=\frac{x^{2n+2}}{n+1}\cdot\frac{n-1+1}{x^{2\left ( n-1 \right )+2}}=\frac{x^{2}\cdot n }{n+1}[/latex]

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

MLoops 16

Задача

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

123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231

 

Тесты

[latex]m[/latex]    [latex]n[/latex]
4    3 123

231

132

123

8    8 12312312
23123123
13213213
12312312
23123123
13213213
12312312
23123123
 10    27 123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123

 

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

 

ideone.com

Решение

Пронумеруем строки от  [latex]1[/latex]  до  [latex]m[/latex] , столбцы — от  [latex]1[/latex]  до  [latex]n[/latex].

1 2 3 4 5 6 7 n
1 1 2 3 1 2 3 1
2 2 3 1 2 3 1 2  …
3 1 3 2 1 3 2 1
4 1 2 3 1 2 3 1  …
5 2 3 1 2 3 1 2  …
6 1 3 2 1 3 2 1  …
7 1 2 3 1 2 3 1  …  …
 …  …  …  …
m  …  …  …  …

 

Положение символа  [latex]2[/latex] определяется однозначно для всей таблицы [latex]\left (n+m \right )\vdots 3[/latex]. В столбцах, где [latex]n\vdots 3[/latex], положение символа [latex]1[/latex]  —  [latex]\left ( n+m+1 \right )\vdots 3[/latex] , на оставшихся свободных местах — символ [latex]3[/latex] . В столбцах, где [latex]\left ( n-1\right )\vdots 3[/latex], на свободных местах стоит символ [latex]1[/latex]. В оставшихся столбцах на свободных местах стоит символ [latex]3[/latex].

Ю2.16

Задача

Задача взята из задачника А.Юркина

Кратные пары

Среди заданных целых чисел [latex]k, l, m[/latex] найти пары кратных.

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

Целые числа [latex]k, l, m[/latex].
[latex] \left | k,l,m \right |< 2\cdot 10^{9} [/latex]

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

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

Тесты

 Входные данные Выходные данные
1.  1 2 3  1 2

1 3

2.  0 2 4

2 4

3. 1 2 6 1 2

1 6

2 6

4.  5 5 2  5 5
 5.  0 0 3
6. 2 5 3
7. -10 5 2

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

 

ideone.com

Решение

Хотя свойство делимости определено на всём множестве целых  чисел, обычно рассматривается лишь делимость натуральных  чисел.

Кратное натурального числа [latex]b[/latex] — это натуральное число [latex]a[/latex],  которое делится на [latex]b[/latex] нацело. Наименьшим кратным данного числа является само это число.

 

 

 

e-olymp 248. Юный садовод

Задача взята с сайта www.e-olymp.com

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

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

К счастью Васи оказалось, что листья на деревьях растут ярусами, причем на верхнем ярусе два листа, на втором — четыре, на следующем — шесть, и так далее, на каждом последующем ярусе на два листа больше по сравнению с предыдущим. А на самой верхушке растет еще один листик. Хитрый Вася послал младшую сестренку Машеньку подсчитать количество ярусов на каждом дереве, а Вас просит написать программу, которая для каждого дерева вычислит количество литров воды для его полива.

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

Количество ярусов [latex]n (0 \leq n \leq 1000)[/latex] на дереве.

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

Вывести количество литров воды для полива этого дерева.

 

Тесты

Входные данные Выходные данные
1. 3 13
2. 0 1
3. 50 2551
4. 560 314161

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

ideone.com

Решение

Для решения этой задачи необходимо найти сумму арифметической прогрессии, где [latex]N=n,[/latex] [latex]a_{1} = 2[/latex] и  [latex]d = 2[/latex] и добавить к ней единицу (лист с верхушки).  Для этого можно воспользоваться формулой суммы арифметической прогрессии [latex]Sn=\frac{2a_{1}+d\left(n-1 \right)}{2}n \rightarrow n^2+n[/latex], либо при помощи цикла [latex]n[/latex] раз прибавлять к [latex]a[/latex] двойку, получая при этом следующий член прогрессии и добавлять его к сумме.

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

Mif 17.10

Задача

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

2

 

Тесты

[latex]\left( x;y \right)[/latex] Ответ
1. (1;6) нет
2. (-5;3) нет
3. (0;0) нет
4. (3.5;1.7) да
5. (2;4) да

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

ideone.com

Решение

Рисунок находится в I четверти, следовательно только точка с положительными [latex]x[/latex] и [latex]y[/latex] может принадлежать этому рисунку. Далее необходимо воспользоваться уравнением окружности [latex]\left(x-a \right)^2+\left(y-b \right)^2=R^2[/latex], т.к. центр окружности(сегмент которой изображен на рисунке) находится в начале координат формула имеет такой вид: [latex]x^2+y^2=R^2[/latex]. Также рисунок ограничен прямой [latex]y=3-x[/latex]. Если [latex]x>0[/latex] и [latex]y>0[/latex] ,  [latex]R\leq6[/latex] , [latex]y\geq3-x[/latex], то точка принадлежит фигуре на рисунке.

ML17

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

Входные данные
В одной строке заданы гипотенуза [latex] (c)[/latex] и катет [latex] (a)[/latex] прямоугольного треугольника, не превышающие  [latex]1000[/latex].

Выходные данные
В одной строке через пробел — второй катет и радиус вписанной окружности с точностью два знака после запятой.

Тесты

Входные данные Выходные данные
1. 5 4 3.00 1.00
2.  3.25  1  3.09  0.42
3.  15  8  12.69  2.85
4.   42.2 25 34.00 8.40
5. 62  23 57.58  9.29
6. 125 47 115.83 18.91
7. 1000 758 652.25 205.13

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

ideone.com

Решение
Для нахождения катета необходимо воспользоваться теоремой Пифагора  [latex]c^2=a^2+b^2 \ \Rightarrow \ b^2=c^2-a^2 \ \Rightarrow \ b=\sqrt(c^2-a^2)[/latex].
Радиус окружности, вписанной в прямоугольный треугольник:
рассмотрим прямоугольный треугольник [latex]ABC[/latex] со вписанной окружностью с центром в точке [latex]O[/latex].

2
[latex]OD=OE=r[/latex] ; [latex]AC[/latex], [latex]CB[/latex], [latex]AB[/latex] — касательные к окружности. По свойствам касательных (1.касательная к окружности перпендикулярна радиусу, проведенному в точку касания; 2.отрезки касательных, проведенных из одной точки равны) [latex]AE=AD, DC=FC, BF=BE[/latex] ; [latex]OD\perp AC, OE\perp AC[/latex], следовательно [latex]AEOD[/latex] — квадрат и [latex]AD=AE=r[/latex].
Пусть [latex]AC=a, AB=b, BC=c[/latex], тогда [latex]\begin{cases}r+DC=a\\r+BE=b\\DC+BE=c\end{cases}\Rightarrow \begin{cases}DC=a-r\\BE=b-r\\a+b-2r=c\end{cases} \Rightarrow[/latex]
[latex]r=\frac{a+b-c}{2}[/latex].

e-olymp 903. Первая или последняя?

Задача взята с сайта e-olimp.com

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

Задано трехзначное число. Какая цифра в нем больше: первая или последняя?

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

Одно трехзначное число.

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

Вывести большую из указанных цифр. В случае их равенства вывести знак «=» (без кавычек).

Тесты:

Входные данные Результат
1 328 8
2 956 9
3 384 4
4 672 6
5 558 8
6 733 7
7 797 =
8 555 =

 

 

ideone.com

Пояснение:

Для того чтобы определить первую цифру [latex] (a) [/latex] трехзначного числа [latex]n[/latex] необходимо найти целую часть от деления этого числа на сто, воспользовавшись формулой  [latex]a = n/100[/latex]. Чтобы определить вторую цифру [latex] (b) [/latex] необходимо найти остаток от деления числа на десять, воспользовавшись формулой [latex]b=n[/latex][latex]\%[/latex][latex]10[/latex] . Затем необходимо проверить равны ли эти цифры, если нет-найти большую.

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