e-olymp 9407. Слияние строк

Задача

Имеются две строки $A$ и $B$.

Ваша задача — найти такую строку $C$, которая содержит в себе и $A$ и $B$ в качестве подстрок и является кратчайшей среди всех таких возможных строк.

Подстрокой строки называется последовательно идущая подпоследовательность этой строки. Например, строка $kbtu$ является подстрокой строки $kbtu open$, но строка $fall$ подстрокой не является.

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

Первая строка содержит строку $A$ $(1 \leqslant |A| \leqslant 10^5)$.

Вторая строка содержит строку $B$ $(1 \leqslant |B| \leqslant 10^5)$.

Гарантируется, что обе строки содержат только строчные латинские буквы.

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

Выведите одну строку $C$.

Тесты

Входные данные Выходные данные
1. compressing
single
compressingle
2. can
you
canyou
3. compressiondoneright
doner
compressiondoneright
4. details
tail
details
5. essential
code
essentialcode

Код

Решение

В данной задаче необходимо создать строку $C$, которая будет содержать в себе строки $A$ и $B$. Рассмотрим два варианта решения задачи. Первый – если строка $B$ полностью содержится в строке $A$, то выводим строку $A$. Второй – если строка $B$ содержится в $A$ частично или не содержится вообще, выводим строку $A$ $+$ элементы строки $B$, которых нет в $A$.

Для проверки, находится ли строка $B$ в $A$, воспользуемся функцией contains(). Если попадаем в первый вариант решения задачи, то выводим $A$. Иначе, создаём цикл, который будет удалять символы в конце первой строки и символы в начале второй, пока они не будут равны. Затем из строки $B$ удаляем элементы, которые входят в строку $A$, и на выход подаём строку $C$, которая состоит из строки $A$ и оставшихся элементов строки $B$.

Ссылки

  • Условие задачи на e-olymp
  • Код программы на ideone.com
  • Засчитанное решение на e-olymp

e-olymp 4764. Степени вершин

Задача

Простой неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

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

В первой строке задано количество вершин графа [latex]n (1 ≤ n ≤ 100)[/latex]. Затем идут [latex]n[/latex] строк по [latex]n[/latex] элементов в каждой — описание матрицы смежности.

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

Выведите [latex]n[/latex] чисел — степени всех вершин.

Тесты

# Входные данные Выходные данные
1 3
0 1 0
1 0 1
0 1 0
1
2
3
2 4
0 1 0 1
0 0 1 1
0 1 0 0
1 0 1 0
2
2
1
2
3 4
1 1 1 0
1 0 1 1
1 1 0 1
0 1 1 1
3
3
3
3
4 5
0 1 0 1 1
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0
3
3
3
3
4
5 5
0 1 0 0 1
1 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 1 1 1 0
2
4
3
3
4

Код задачи

Решение

В ячейке [latex]deg[i][/latex] будем подсчитывать степень вершины [latex]i[/latex], которая равна количеству единиц в i-ой строки матрицы смежности.
Для неориентированного графа степень вершины — это количество всех инцидентных ей ребер.
Граф [latex]G=(V,U)[/latex] может быть задан матрицей смежности. Это квадратная матрица размерности [latex]n\times n[/latex], где [latex]n=\left |V \right | [/latex]. Матрица смежности неориентированного графа симметрична. Элементы матрицы смежности определяются следующим образом.
1- если [latex]i[/latex]-тая и [latex]j[/latex]-тая вершины графа смежны
0- иначе
[latex] a_{ij}=\left\{\begin{matrix}
1\\
0
\end{matrix}\right.\\[/latex]

Ссылки

Задача на e-olymp

Код задачи на ideone

e-olymp 44. Единицы

Задача


В арифметическом выражении разрешается использовать число [latex]1[/latex], операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число [latex]n[/latex]?

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

Одно число [latex]n[/latex] [latex](1 \leqslant n \leqslant 5000).[/latex]

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

Искомое количество единиц.

Тесты

# Входные данные Выходные данные
1 7 6
2 22 10
3 90 13
4 157 16
5 985 21

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

Решение задачи

Нам нужно найти минимальное количество [latex]1,[/latex] с помощью которых можно составить заданное число. Если последней операцией будет сложение, то первое слагаемое будет состоять из [latex]f(i)[/latex] единиц, а второе — из [latex]f(n-i).[/latex] Значение [latex]i[/latex] будем выбирать таким, чтобы сумма этих двух слагаемых была минимальной. Если [latex]n[/latex] нацело делится на [latex]i[/latex], то последней операцией будет умножение. Первый множитель будет состоять из [latex]f(i)[/latex] единиц, а второй — [latex]\displaystyle f \left (\frac{n}{i} \right).[/latex] Тогда значение [latex]i[/latex] будем перебирать до [latex]\sqrt{n},[/latex] чтобы сумма этих слагаемых была минимальной. Затем выводим искомое количество единиц на экран. Задача решена.

Ссылки

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