e-olymp 2401. Обход в ширину

Задача 2401

Условие

Дан неориентированный граф. В нём необходимо найти расстояние от одной заданной вершины до другой.

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

В первой строке содержится три натуральных числа [latex]n, s[/latex] и [latex]f (1 [/latex] [latex]\le[/latex] [latex]s, f[/latex] [latex]\le[/latex] [latex]n[/latex] [latex]\le[/latex] [latex]100)[/latex] — количество вершин в графе и номера начальной и конечной вершин соответственно. Далее в n строках задана матрица смежности графа. Если значение в [latex]j[/latex]-м элементе [latex]i[/latex]-й строки равно [latex]1[/latex], то в графе есть направленное ребро из вершины [latex]i[/latex] в вершину [latex]j[/latex].

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

Вывести минимальное расстояние от начальной вершины до конечной. Если пути не существует, выведите [latex]0[/latex].

Тесты

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

0 1 1 1

1 0 1 0

1 1 0 0

1 0 0 0

2
4 5 1 4
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
2

 

Решение

Для решения данной задачи необходимо использовать алгоритм «Поиск  в ширину». Суть данного алгоритма полагает в том, что все вершины, начиная с начальной, помещаются в структуру очередь [latex](queue)[/latex] в порядке удаления от начальной вершины. По мере заполнения очереди, каждой вершине приписывается величина расстояния [latex](dist)[/latex] от начальной вершины, после чего соответствующая вершина помечается как пройденная [latex](used)[/latex] и её расстояние от начальной вершины более не переписывается даже при повторном просмотре. Таким образом, каждой вершине, для которой существует путь, соединяющий её с начальной вершиной, сопоставляется минимальное расстояние от нее до начальной вершины. Если такого пути не существует, расстояние остается равным нулю. Подробней об этом алгоритме можно прочесть здесь

Ссылки

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

Условие задачи

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

AL6

Задача AL6

Условие

Дана конечная последовательность, состоящая из левых и правых скобок различных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

Тесты

Входные данные Выходные данные
1 ( NO
2 )) NO
3 [} NO
4 {} YES
5 (){}[] YES
6 ({[]}{}) YES
7 [({}())[] NO

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

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать структуру [latex]stack[/latex], в которую поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Ссылки

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

Условие задачи

А291а

Задача: А291а

Условие:

Даны действительные числа [latex]a_{1},\ldots,a_{30}.[/latex] Получить [latex]\max (a_{1}+ a_{30},a_{2}+a_{29},\ldots,a_{15}+a_{n}).[/latex]

Тесты:

Входные данные Выходные данные
1 2 3 5 4 8
2 2 3 7 5 4 14
3 4.5 1.1 3 9.25 0.75 10.35
4 -4.5 -2 0 -7.1 5 0.5

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

Решение:

После считывания входного потока данных в вектор [latex]real[/latex] вещественных чисел, вычисляем размер вектора [latex]sum[/latex], равный половине количества элементов входного потока с округлением вверх. В случае нечетного количества элементов, последним элементом вектора [latex]sum[/latex] будет центральный элемент вектора [latex]real[/latex] увеличенный в два раза. Далее, после сортировки полученного вектора по убыванию, выводим первый элемент вектора.

Ссылки:

Задачник по программированию С. Абрамова.

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

e-olymp 2164. Шифр Юлия

Задача. Юлий Цезарь использовал свой способ шифрования текста. Каждая буква заменялась на следующую по алфавиту через [latex]k[/latex] позиций по кругу. Необходимо по заданной шифровке определить исходный текст.

Входные данные: В первой строке дана шифровка, состоящая из не более чем 255 заглавных латинских букв. Во второй строке число [latex]k (1[/latex] [latex]\leq[/latex] [latex]k[/latex] [latex]\leq[/latex] [latex]10)[/latex].

Выходные данные: Требуется вывести результат расшифровки.

Тесты:

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

1

WORD
2 ZABC

3

WXYZ

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

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

Каждая буква строки является элементом массива [latex]cipher[/latex]. Чтобы расшифровать строку нужно от значения [latex]i[/latex]-го элемента массива отнять [latex]k[/latex], тем самым сдвинуть символ на [latex]k[/latex] единиц по алфавиту, и заменить первоначальный символ на полученный результат. В случае если разница символа [latex]i[/latex]-го элемента и числа [latex]k[/latex] не входит в множество заглавных латинских букв, требуется от символа «Z» отнять оставшееся кол-во шагов [latex]k[/latex] (то есть не считая те которые уже были пройдены от изначального символа символа до крайнего символа «A»), и заменить первоначальный символ на полученный результат. Можно не беспокоиться о том, что символ вернется к «Z» более чем один раз так как условие исключает этот вариант ([latex]k<=10[/latex] при 26-ти символах латинского алфавита).

Используя цикл, повторяющийся столько же, сколько символов в строке [latex]cipher[/latex], требуется применить описанный алгоритм к каждому элементу массива. По окончанию работы цикл, вывести строку cipher, содержащую уже расшифрованные символы.

Код программы с типом данных  string:

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

Чтобы расшифровать слово, находящееся в строке [latex]cipher[/latex], необходимо заменить каждую букву данной строки на букву, находящуюся на [latex](find — k)[/latex] позиции строки [latex]alp[/latex], где [latex]alp[/latex] — строка, содержащая латинский алфавит, а [latex]find[/latex] — позиция заменяемой буквы в алфавите. В случае если разница [latex]find[/latex] и [latex]k[/latex] меньше нуля, заменяем букву строки [latex]cipher[/latex] на букву, находящуюся на [latex](26 — (k — find))[/latex] позиции строки [latex]alp[/latex], то-есть не считая то количество позиций которые уже были пройдены от изначального символа символа до первого символа строки [latex]alp[/latex]. Можно не беспокоиться о том, что символ вернется к к концу алфавита более чем один раз так как условие исключает этот вариант ([latex]k<=10[/latex] при 26-ти символах латинского алфавита).

MLoop 23

Задача:

Вычислите с точностью [latex]\varepsilon[/latex]  сумму ряда [latex]{\sum_{i=1}^\infty}\frac{(-1)^i}{i!}[/latex].

Входные данные: Точность [latex]\varepsilon[/latex].

Выходные данные: Сумма ряда [latex]{\sum_{i=1}^\infty}\frac{(-1)^i}{i!}[/latex] с точностью [latex]\varepsilon[/latex].

Тесты:

0.1

0.01

0.001

0.0001

Точность

[latex]\varepsilon[/latex]

Сумма ряда

[latex]{\sum_{i=1}^\infty}\frac{(-1)^i}{i!}[/latex]

1 0.1 0.375
2 0.01 0.366667
3 0.001 0.367857
4 0.0001 0.367882

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

В условии нам дана формула суммы ряда [latex]{\sum_{i=1}^\infty}\frac{(-1)^i}{i!}[/latex] с точностью [latex]\varepsilon[/latex].

Для начала, программа читает входные данные и присваивает их переменной [latex]\varepsilon[/latex](точность). Также вводим переменную [latex]sum[/latex], равную первому члену (на случай если введенная точность не позволит циклу начаться), накапливающую сумму ряда.

Далее следует цикл [latex]for[/latex] считающий сумму членов [latex]x[/latex] пока не достигнет точности [latex]\varepsilon[/latex]. Цикл прибавляет к [latex]sum[/latex] слагаемое, деленное на [latex]i[/latex] и с противоположным знаком. По окончании цикла выводим значение суммы [latex]sum[/latex] .

Ссылка на условие задачи

Ссылка на компилятор с кодом

MLoops 4

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

-+-+-*-+-+-*-+-+-*-+-+-*-
+-+-*-+-+-*-+-+-*-+-+-*-+
-+-*-+-+-*-+-+-*-+-+-*-+-
+-*-+-+-*-+-+-*-+-+-*-+-+
+*-+-+-*-+-+-*-+-+-*-+-+-
*-+-+-*-+-+-*-+-+-*-+-+-*
-+-+-*-+-+-*-+-+-*-+-+-*-
+-+-*-+-+-*-+-+-*-+-+-*-+

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

Количество столбцов [latex]n > 0[/latex] и строк [latex]m > 0[/latex].

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

Таблица размером [latex]n[/latex] [latex]\times[/latex] [latex]m[/latex] аналогичная таблице в условии.

Тесты:

[latex]n[/latex]   [latex]m[/latex] Таблица
1 1 1
 

2

1 7
+

+

*
3 7 1 -+-+-*-
4 10 10 -+-+-*-+-+
+-+-*-+-+-
-+-*-+-+-*
+-*-+-+-*-
-*-+-+-*-+
*-+-+-*-+-
-+-+-*-+-+
+-+-*-+-+-
-+-*-+-+-*
+-*-+-+-*-
5 25 8 -+-+-*-+-+-*-+-+-*-+-+-*-
+-+-*-+-+-*-+-+-*-+-+-*-+
-+-*-+-+-*-+-+-*-+-+-*-+-
+-*-+-+-*-+-+-*-+-+-*-+-+
-*-+-+-*-+-+-*-+-+-*-+-+-
*-+-+-*-+-+-*-+-+-*-+-+-*
-+-+-*-+-+-*-+-+-*-+-+-*-
+-+-*-+-+-*-+-+-*-+-+-*-+

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

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

Посмотрев на таблицу можно заметить, что знак «-» выводится когда номер члена последовательности нечетный, знак «+» когда четный и знак «*» когда член последовательности кратный 6. После объявления переменных [latex]n[/latex] и [latex]m[/latex](количество столбцов и строк соответственно) создаем два цикла — один внутри другого. Внешний цикл считает номер строки и, после выполнения внутреннего, переносит последовательность на новую строку. Внутренний цикл считает номер столбца и выполняет проверку на кратность шести, в этом случае выводится знак «*». В противном случае проводится проверка на кратность двум. Если номер члена последовательности кратен двум выводиться знак «+», в противном случае — «-«.

Условие задачи

Код в компиляторе