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