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 165. Симметрия

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

 

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]10[/latex] [latex]2[/latex]
2 [latex]116[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]1[/latex]
4 [latex]454[/latex] [latex]2[/latex]
5 [latex]12301230[/latex] [latex]2[/latex]

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

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 1078. Степень строки

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

Обозначим через [latex]a\cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a=[/latex] «abc» и [latex]b=[/latex] «def», то [latex]a\cdot b=[/latex] «abcdef».
Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

[latex]a^{0}=[/latex] «» (пустая строка)
[latex]a^{n+1}=a\cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

Входные данные Выходные данные
1 abcabcabc 3
2 aaaaaaaaaa 10
3 ollollo 1
4 pjpjpjpj 4

Посмотреть работу программы на примере приведенных выше тестов можно на сайте ideone.

Решение

Описание решения

Получая строку str из потока ввода, вызываем функцию static public int StringPow(final String str) и передаем полученную строку в качестве входного параметра. Функция StringPow возвращает значение типа int — наибольшую степень строки, которую программа и передаст в поток вывода в качестве выходных данных.

Минимальной степенью строки может быть число [latex]1[/latex] — в том случае, если в заданной строке [latex]s[/latex] нет повторяющихся подстрок. Максимальной же степенью строки может быть количество символов, из которых строка состоит — в том случае, если строка состоит из одного повторяющегося символа. В этом случае этот символ и будет считаться повторяющейся подстрокой.

Получив в качестве входного аргумента строку str, предположим внутри тела функции StringPow, что степень данной строки равна [latex]1[/latex] ( int pow = 1;) на тот случай, если бо́льшую степень найти не удастся.

Так как нужно найти число повторений подстроки минимального размера в строке str, будем проверять все подстроки размером от [latex]1[/latex] символа до size/2, где size — длина строки. Строка не может состоять из повторяющейся подстроки размером меньше [latex]1[/latex] или больше половины строки. Отсюда цикл for (int i=1; i<=size/2; i++).

Сразу будем отсеивать подстроки, из повторений которых строка не может состоять из-за несоответствия количества символов строки и подстроки ( if (size % i != 0) continue;). К примеру, строка длиной [latex]8[/latex] символов не может состоять из повторений подстроки длиной [latex]3[/latex] символа.

Запоминаем эту подстроку String sub1 = new String(str.substring(0, i));, а затем будем сравнивать с каждой следующей подстрокой такого же размера String sub2 = new String(str.substring(j, j+i)); во внутреннем цикле, предполагая перед этим, что мы нашли нужную нам подстроку ( boolean found = true;); если сверяемые подстроки различаются ( if (!sub1.equals(sub2))) — значит рассматриваемая подстрока sub1 искомой подстрокой не является. Прерываем действие внутреннего цикла и переходим к следующей подстроке, длиной на 1 символ больше. Если же строка полностью состоит из подстроки sub1 находим степень строки — число повторений подстроки в строке, иначе говоря, делим размер строки на размер подстроки ( pow = (size/i);).

Посмотреть решение задания можно на сайте e-olymp.