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]-го слагаемых  будет больше заданной точности.