e-olimp 1310. Наибольший блок

Задача

Блоком строки [latex]S[/latex] в позиции [latex]i[/latex] назовём наибольшую подстроку [latex]S[/latex], которая начинается в позиции [latex]i[/latex] и совпадает с префиксом [latex]S[/latex]. Длину блока в позиции 0 считать равной нулю. Вычислить длину наибольшего блока заданной строки [latex]S[/latex].

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

Единственная строка [latex]S[/latex] [latex]\left(\left|S\right|\leq{10}^{6}\right)[/latex].

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

Длина наибольшего блока строки [latex]S[/latex].

Тесты 

 Входные данные  Выходные данные
abaabaab  5
aaaaa 4
aaabaab 2

Реализация 

Код на ideone.com

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

Решение

Для решения данной задачи необходимо рассмотреть алгоритм эффективного вычисления [latex]Z[/latex]-функции. Создадим массив [latex]z[/latex], где [latex]i[/latex]-ый элемент  равен наибольшему числу символов, начиная с [latex]i[/latex]-ой позиции,  совпадающих с первыми символами заданной строки [latex]s[/latex]. Эффективность алгоритма состоит в том, что при вычислении очередного элемента массива [latex]z[/latex] мы будем использовать уже вычисленные ранее значения. Назовем отрезком совпадения подстроку, совпадающую с префиксом заданной строки. Тогда искомое значение [latex]z\left [ i \right ][/latex] — это длина самого длинного отрезка совпадения, начинающегося в позиции [latex]i[/latex]. Из всех найденных отрезков совпадения будем хранить тот, который оканчивается правее всего. Положим, что [latex]l[/latex] и [latex]r[/latex] — индексы начала и конца данного отрезка соответственно. Тогда при вычислении [latex]z\left [ i \right ][/latex] возможны две ситуации: [latex]i>r[/latex] и [latex]i\leq r[/latex]. В первом случае позиция  [latex]i[/latex] лежит за пределами проанализированной части строки . Тогда ищем значение [latex]Z[/latex]-функции перебором до тех пор, пока не дойдем до несовпадения или конца заданной строки. Стоит отметить, что если [latex]z\left [ i \right ]>0[/latex], следует изменить индексы отрезка совпадений. Во втором случае текущая позиция [latex]i[/latex] лежит внутри отрезка совпадений [latex]\left [ l,r \right ][/latex]. Так как подстроки [latex]s\left [ l\ldots r \right ][/latex] и [latex]s\left [ 0\ldots r-l \right ][/latex] совпадают, то в качестве значения [latex]z\left [ i \right ][/latex] можно взять значение [latex]z\left [ i-l \right ][/latex]. Однако, значение [latex]z\left [ i-l \right ][/latex] может быть слишком большим для данного блока (суффикс строки будет меньше, чем данное значение, чего быть не может). Следовательно, [latex]z\left [ i \right ][/latex]-ому элементу будем присваивать значение минимума из длины суффикса [latex]\left ( r-i+1 \right )[/latex] и [latex]z\left [ i-l \right ][/latex]. Далее используем вышеописанный перебор. В конечном итоге максимальный элемент массива — длина наибольшего блока заданной строки.

e-olimp 4852. Кратчайшее расстояние

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]x[/latex]  [latex]\left ( 1\leq n\leq 1000,1\leq x\leq n \right )[/latex] — количество вершин в графе и стартовая вершина соответственно. Далее в [latex]n[/latex] строках по [latex]n[/latex] чисел — матрица смежности графа: в [latex]i[/latex]-ой строке на [latex]j[/latex]-ом месте стоит [latex]1[/latex], если вершины [latex]i[/latex] и [latex]j[/latex] соединены ребром, и [latex]0[/latex], если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].

Тесты 

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

 

Реализация

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

Код на ideone.com

Решение

Для решения данной задачи необходимо применить  алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем  вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид  [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.

А291б

Задача
Даны действительные числа [latex]{a}_{1},\ldots,{a}_{30}[/latex].

Получить: [latex]\min\left({a}_{1}{a}_{16},{a}_{2}{a}_{17},\ldots,{a}_{15}{a}_{30}\right)[/latex]

Тесты
 Входные данные  Выходные данные
 2 4 8 1 3 5 4 8 1 10 5 2 4 9 3 9 1 5 4 3 7 8 2 11 1 4 5 10 3 8  4
0 8 9 6 11 2 5 3 6 9 8 8 5 20 1 4 8 12 15 7 6 31 0 5 14 5 0 14 11 2 0
8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 16

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

Код на ideone.com

Решение

Для решения задачи мы условно разделяем исходную последовательность действительных чисел на две подпоследовательности.: [latex]{a}_{1},\ldots,{a}_{15}[/latex] и [latex]{a}_{16},\ldots,{a}_{30}[/latex]. Длина подпоследовательностей в два раза меньше длины исходной последовательности. Таким образом, разность индексов элементов, которые необходимо перемножить, равна длине подпоследовательности. Тогда перемножаем необходимые элементы и находим минимальное значение из полученных результатов.

e-olymp 506. Новый компилятор

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

Постановка задачи

Вам необходимо преобразовать множество старых программ для новой версии компилятора. Для этого необходимо заменить «->» на «.» везде, кроме комментариев. Комментарии в данном языке программирования начинаются с символов «//» и продолжаются до конца строки. Напишите программу, выполняющую такое преобразование.

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

Входной файл содержит от 1 до 500 строк длиной не более 50 символов с ASCII-кодами от 32 до 127 – текст программы, которую нужно преобразовать.

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

В выходной файл вывести преобразованный текст программы.

Тесты

Исходный текст программы Преобразованный текст программы

Реализация

Код на ideone.com

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

Ход решения

Для решения данной задачи используем функцию  getchar, так как данная функция может работать с управляющими символами (когда программа находит комментарий, необходимо печатать без изменений до конца строки). Так как по условию задачи нам нужно найти такие комбинации символов, как «//» и «->» , мы при каждом проходе цикла, сравнивая символы входных данных с теми, что надо найти, запоминаем два соседних символа.

 

MLoops15

 

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

Тесты

[latex] m[/latex] [latex] n[/latex] [latex] k[/latex] Результат
25 4 8 1122334455667788112233445
8112233445566778811223344
8811223344556677881122334
7881122334455667788112233
8 9 3 11223311
31122331
33112233
23311223
22331122
12233112
11223311
31122331
33112233
4 4 3 1122
3112
3311
2331

Код

Код на ideone.com

Решение

Для решения данной задачи введем дополнительную переменную  [latex]l[/latex], которая будет накапливать в  себе количество напечатанных символов в строке. Каждое число в строке повторяется дважды, следовательно печатать будем число, равное  целой части [latex]\left( l\div 2 \right)[/latex].

Обратим внимание на начало каждой строки. В каждой следующей строке мы сдвигаем последовательность на одно число вправо. Тогда значение  переменной  [latex] l[/latex] на второй строке должно быть максимально возможным [latex]\left(k\cdot2 \right)[/latex] и уменьшаться на единицу при каждом переходе на следующую строку.

 

 

MLoop 15

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

Тесты

[latex]x[/latex] [latex]\varepsilon[/latex] Результат
42  0.3 -8.09848e-05
8 0.15 -0.0117188
55.5 0.04 -3.50972e-055
-12 0.6 0.00347222
-82 0.0001 -3.23677e-08

Код

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

Решение :

Косеканс — это тригонометрическая функция, которою можно определить формулой [latex]\csc x=\frac{1}{\sin x}[/latex]. Таким образом, мы можем разложить  функцию [latex]\sin x[/latex] в бесконечную сумму степенных функций, воспользовавшись формулой Тейлора. Получим, что [latex]\sin x=x-\frac{{x}^{3}}{3!}+\frac{{x}^{5}}{5!}-\dots=\sum_{n=0}^{\propto}\frac{{-1}^{n}\times{x}^{2n+1}}{\left(2n+1\right)!}[/latex]. Слагаемые данной суммы являются геометрической прогрессией, знаменатель который можно найти по формуле [latex]\frac{a_n}{a_{n-1}}=\frac{\frac{{-1}^{n}\times{a}^{2n+1}}{\left(2n+1 \right)!}}{\frac{{-1}^{n-1}\times{a}^{2n-1}}{\left(2n-1 \right)!}}=\frac{\left( -1\right){a}^{2}}{2n\times\left( 2n+1\right)}[/latex].  Будем вычислять сумму до тех пор, пока разность [latex]n[/latex]-го и  [latex]\left ( n+1 \right )[/latex]-го слагаемых  будет больше заданной точности.

Mif 17.1

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

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

Два числа [latex] x[/latex], [latex]y[/latex] — координаты точки.

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

Слово «YES», если точка принадлежит треугольнику и «NO» ,  если не принадлежит.

17_1Тесты

[latex]x[/latex] [latex]y [/latex] Результат
4 -2  NO
2 1 YES
0 3 YES
5 0 NO
0 -1 NO

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

 

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

Решение

Точка будет принадлежать треугольнику только при таких [latex]x[/latex] и [latex]y[/latex], что сумма их модулей не превышает 4. При выполнении условия выводим на экран: «YES». В противном случае — «NO».

e-olymp 192. Просто Фибоначчи

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

Найти [latex]N[/latex]-е по порядку простое число Фибоначчи.

Во входном файле число [latex]N[/latex], [latex]\left(1\leq N\leq 10 \right)[/latex]
В выходной файл следует записать [latex]N[/latex]-е по порядку простое число Фибоначчи.

Тесты

[latex]N[/latex] Простое число Фибоначчи
 3  5
5 89
7 1597
9 514229
10 433494437

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

Код на ideone.com

Выполненное задание на сайте  e-olimp.com здесь.

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

  1. Нам необходимо вычислить первые десять элементов  последовательности Фибоначчи.  Для этого будем использовать цикл.   Пусть  [latex] a<b<c [/latex] , где [latex] a, b, c [/latex] являются членами последовательности Фибоначчи.  Обозначим, что элемент последовательности  равен сумме двух ему предшествующих элементов.  Далее присвоим переменным [latex]a, b[/latex] значения следующих элементов последовательности соответственно.  Таким образом присваиваем переменной [latex] a [/latex] значение переменной [latex] b [/latex] , переменной [latex] b[/latex] — значение переменной [latex] c [/latex] , а  переменной [latex] c [/latex] —  значение равное  [latex](a+b)[/latex].
  2. Но не каждый элемент последовательности Фибоначчи является простым числом. Следовательно, нам необходимо проверить делится ли без остатка полученное нами число на какое-либо число, отличное от [latex] 0 [/latex] , [latex] 1 [/latex] и самого себя.  Таким образом, если найденный элемент [latex] c [/latex] делится без остатка на целые  числа, принадлежащие отрезку [latex]\left[2;\sqrt{c} \right][/latex] , то найденный элемент не является простым числом. Тогда необходимо рассмотреть следующий элемент последовательности Фибоначчи. Для этого введем логическую переменную [latex] (bool x) [/latex] , которая будет принимать значение истинны только тогда, когда число простое.
  3. Когда логическая переменная принимает значение истины, то увеличим счетчик на единицу.  А искать последующие значения элемента[latex] c [/latex] будем до тех пор, пока значение счетчика не станет равным числу [latex] N [/latex].

Mif 5

Задача. Даны действительные числа [latex] x, y, z.[/latex]  Вывести наименьшее и наибольшее из них. Если наименьших или наибольших чисел окажется несколько, то укажите в скобках количество.

Тесты

[latex] x [/latex] [latex] y [/latex] [latex]z[/latex] Наименьшее число Наибольшее число
100.56  812.34 -12 -12 812.34
-722.5  812.34 -722.5 -722.5 (2)   812.34
 256 145695 145695 256 145695 (2)
0  0 0 0 (3) 0(3)
-518.3 -759.3  -1995.6 -1995.6 -518.3

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

 

Здесь находится код в ideone.com

Решение

  1. Так как по условию нам даны действительные числа, то, чтобы охватить наибольший диапазон чисел, используем тип данных long double;
  2. Для того, чтобы решить данную задачу мы предполагаем, что одна из переменных является наименьшей[latex] (x=min)[/latex] , а потом сравниваем ее с остальными переменными.
  3. Возможно, наше предположение верно. Тогда присваиваем счетчику значение [latex] 1 [/latex]. Если какая-либо из оставшихся переменных равна минимуму, то увеличиваем значение счетчика на единицу.
  4. Если значение переменной [latex] y[/latex] или  [latex] z[/latex] меньше минимума, то наше предположение было не верно. Тогда присваиваем значение минимального числа соответствующей переменной, а счетчику — значение [latex] 1 [/latex] . Если  несколько переменных имеют наименьшее значение, то при каждом совпадении значения счетчик увеличивается на единицу.
  5. Аналогичный подход применяем к максимальному значению.

ML5

Задача. Даны два действительных числа. Найти среднее арифметическое этих чисел и среднее геометрическое их модулей.

Тесты

Первое число Второе число Среднее арифметическое Среднее геометрическое
156 82 119 113.102
-1158 2569 705.5 1724.79
256.3 289.5 272.9 272.395
9854.08 -493 4680.54 2204.1
-544.59 -12 -278.295 80.8398

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

  1.  Так как в постановке задачи не указан диапазон чисел, то рациональнее всего использовать  тип данных long double, охватывающий наибольшее количество возможных вариантов входных данных.
  2. Нам необходимо найти среднее арифметическое чисел, которое  представляет собой  сумму всех зафиксированных значений, делённую на их количество. Для нашей задачи формула приобретает следующий вид:  [latex]A=\frac{a+b}{2}[/latex].
  3.  Для нахождения среднего геометрического модулей двух чисел воспользуемся формулой  [latex] G=\sqrt{\left|x_1\times x_2 \right|} [/latex].

Здесь находится код в ideone.com

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

e-olymp 157. Зоопарк

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

Постановка задачи

В зоопарке [latex] N [/latex] клеток выстроены в ряд. В зоопарке, кроме прочих обитателей, живут две мартышки, Слава и Юра. Слава и Юра всегда были большими друзьями и сидели в соседних клетках, но теперь они поссорились и больше не хотят видеть друг друга. Смотритель уже собрался переселить их в соответствии с их желанием, однако возникла проблема. Слава и Юра — очень образованные мартышки (каждый из них закончил аж по восемь классов!), и они непременно хотят знать, сколько всего существует способов расселить их так, чтобы их клетки не были соседними, и уж конечно их клетки должны быть различными. Можно считать, что все  [latex] N [/latex] клеток доступны, остальные обитатели зоопарка готовы переехать куда угодно.

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

В первой строке входных данных находится число [latex] N [/latex]  [latex](2\leq N\leq 100)[/latex] — количество клеток в зоопарке.

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

Выведите одно число — количество способов поселить Славу и Юру в разные клетки так, чтобы эти клетки не были соседними.

Тесты

4 6
15 182
30 812
48 2162
60 3422

Реализация

Здесь находится код в ideone.com

Решение

Рассмотрим  возможные расположения клеток при условии, что  одна из обезьян занимает первую клетку. Очевидно, что другая обезьяна не может занимать первую и вторую клетки, т к клетки должны быть разными и не соседними. Следовательно, существует [latex] (n — 2) [/latex] вариантов расположения второй обезьяны. Далее предположим, что первая обезьяна занимает вторую клетку. Тогда  количество вариантов расположения второй обезьяны равно [latex] (n-2-1) = (n-3) [/latex] . И так далее, до тех пор пока не останется один вариант расположения второй обезьяны. Таким образом, ключ к решению задачи лежит в рассмотрении количества вариаций расположения клеток обезьян как  арифметической  прогрессии. Исходя из условия задачи, нам необходимо найти сумму первых [latex] n [/latex]  членов прогрессии. Формула для вычислений: [latex] S=\frac{(a_1 + a_k}{2}*k [/latex], где  [latex] a_1=n-2 [/latex] и [latex] a_k=1 [/latex], и [latex] k=n-2 [/latex].  Применяя математические преобразования, получаем что [latex] S=\frac{(n-1) * (n-2)}{2} [/latex]. Однако,  имеет значение не только, непосредственно,  какие две клетки заняты, но и какая именно из обезьян занимает определенную клетку. То есть при [latex] n=3 [/latex] мы имеем лишь пару клеток, которые можем использовать, но два способа поселения. Следовательно, полученное выражение необходимо умножить на два. Таким образом, мы вывели необходимую нам формулу.

Выполненное задание на сайте  e-olimp.com здесь.