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](количество столбцов и строк соответственно) создаем два цикла — один внутри другого. Внешний цикл считает номер строки и, после выполнения внутреннего, переносит последовательность на новую строку. Внутренний цикл считает номер столбца и выполняет проверку на кратность шести, в этом случае выводится знак «*». В противном случае проводится проверка на кратность двум. Если номер члена последовательности кратен двум выводиться знак «+», в противном случае — «-«.

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

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

Mif 14

Задача:

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин в трёхмерном пространстве, определить имеют ли они общие точки.

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

Координаты отрезков [latex]AB[/latex] и [latex]CD[/latex]:

[latex]A(x_1;y_1),B(x_2;y_2),C(x_3;y_3),D(x_4;y_4)[/latex].

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

Расположение отрезков [latex]AB[/latex] и [latex]CD[/latex] относительно друг друга:

  1.  Прямые в разных плоскостях,
  2.  Прямые параллельны,
  3.  Отрезки находятся на одной прямой но не совпадают,
  4.  Отрезки совпадают,
  5.  Отрезки пересекаются,
  6.  Отрезки не пересекаются;

Тесты:

Координаты

[latex]A(x_1;y_1)B(x_2;y_2)C(x_3;y_3)D(x_4;y_4)[/latex]

Расположение отрезков
1 1 1 1  2 2 2  0 5 0  2 6 -1 Прямые в разных плоскостях
2 1 1 1  -1 -1 -1  0 0 -1  2 2 1 Прямые параллельны
3 1 1 0  2 2 1  4 4 3  5 5 4 Отрезки находятся на одной прямой но не совпадают
4 0 0 0  3 3 6  2 2 4  5 5 10 Отрезки совпадают
5 0 0 0  1 1 1  0 1 1  0 -1 -1 Отрезки пересекаются
6 0 0 1  1 1 1  5 -2 5  4 -1 4 Отрезки не пересекаются
7 1 0 0  1 1 0  0 0 1  1 0 1 Прямые в разных плоскостях
8 1 1 0  1 1 5  2 4 -1  2 4 1 Прямые параллельны
9 1 1 0  2 1 0  5 1 0  6 1 0 Отрезки находятся на одной прямой но не совпадают

 

10 -1 -1 -1  1 1 1  0 0 0  2 2 2   Отрезки совпадают
11 1 1 4  2 2 4  2 1 4  1 2 4 Отрезки пересекаются
12 1 0 3  1 3 3 2 2 3  4 4 3 Отрезки не пересекаются

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

Для решения задачи нам понадобятся следующие функции:

1.[latex]Mixed[/latex] — функция возвращающая значение смешанного произведения векторов

(Основная формула [latex]a_xb_yc_z+a_yb_zc_x+a_zb_xc_y-a_zb_yc_x-a_yb_xc_z-a_xb_zc_y [/latex])

2.[latex]Collinear[/latex] — функция принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.

(Основная формула [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex]  )

3.[latex]VectorEquation[/latex] — Функция принимающая координаты двух точек принадлежащих разным прямым и координаты направляющего вектора, и возвращающая логическое значение true, если они принадлежат одной прямой, и false в противном случае.

(Основная формула [latex]\frac{x — x_0}{V_x} =\frac{y — y_0}{V_y} = \frac{z — z_0}{V_z}[/latex] )

4.[latex]Min[/latex] — возвращает минимум двух чисел.

5.[latex]Max[/latex] –  возвращает максимум двух чисел.

6.[latex]CollinearforPerp[/latex] — функция принимающая координаты векторов, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае. Используется в случае для формулы коллинеарности [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex] при [latex]b_x=0[/latex] , [latex]b_y=0[/latex] или [latex]b_z=0[/latex].

(Основная формула [latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex] )

Для удобства, заведем переменные для координат векторов соответствующих отрезкам. Первая проверка определяет чему равно смешанное произведение векторов. Если произведение равно [latex]0[/latex] то  векторы находятся в одной плоскости, в противном случае — в разных.

Далее проверяем является ли какой либо вектор перпендикулярным какой-либо оси. Это необходимо так как в таком случае координаты вектора [latex] \vec{CD}[/latex] равны нулю, что недопустимо при делении функций на координаты данного вектора.

В случае если какой либо вектор перпендикулярный какой-либо оси, проверяем их коллинеарность по формуле [latex]CollinearforPerp[/latex]:

[latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex]

 

Если векторы коллинеарны то они параллельны в том случае, если координата вектора перпендикулярного некой оси не равна координате другого вектора той же оси [latex](X_c=X_d and X_a \neq X_c)[/latex] [latex]||[/latex] [latex](Y_c=Y_d and Y_a \neq Y_c)[/latex] [latex]||[/latex] [latex](Z_c=Z_d and Z_a \neq Z_c)[/latex] . В противном случае прямые совпадают. Отрезки также совпадают если одна из координат одного отрезка находится между большим и меньшем значением координат другого отрезка, для всех осей:

[latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_c and Max(X_a,X-b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

 

В противном случае отрезки находятся на одной прямой но не совпадают.

В случае если данные векторы не коллинеарны, их прямые пересекаются. Отрезки также пересекаются тогда когда одна из координат одного отрезка находится между большим и меньшем значением координат другого отрезка, для всех осей:

[latex](Min(X_a,X_b)[/latex][latex]\le[/latex][latex]X_c and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

 

Если же ни один вектор не перпендикулярен ни одной оси, проверяем вектора на коллинеарность стандартным способом ([latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex])

Для коллинеарных векторов используем функцию VectorEquation которая возвращает логическое значение true, если точка одного отрезка принадлежит прямой другому, и false если векторы перпендикулярны. Проверка на совпадение отрезков проводиться аналогично первому случаю.

Когда вектора не коллинеарны, прямые пересекаются. Проверка на пересечение отрезков проводиться аналогично первому случаю.

 

Ссылка на код программы

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

e-olymp 2061. Юные программисты

Задача

Известно, что в школе не менее чем [latex]k_1[/latex]  учеников, но не более чем [latex]k_2[/latex] учеников. Также известно, что каждый мальчик дружит с [latex]n[/latex] девочками, а каждая девочка с [latex]m[/latex] мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Тесты:

Ввод Вывод
1 20 30 4 5 27 15 12
2 40 50 5 4 45 20 25

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

Решение:

Увеличиваем количество девочек на 1 пока количество мальчиков по формуле [latex]b = g \cdot m / n[/latex] не станет целочисельным значением и сумма мальчиков и девочек будет больше или равна минимальному возможному количеству учеников [latex]k_1[/latex].

  • Условие задачи можно найти на сайте e-olymp.
  • Ссылка на решение задачи на ideone.com здесь.
  • Ссылка на полностью решенную задачу здесь.

Mif17.11

Задача. Принадлежит ли точка [latex](x;y)[/latex] фигуре на рисунке?
Новый текстовый документ

Тесты:

Ввод [latex](x,y)[/latex] Вывод
1 3 1 YES
2 -3 1 NO
3 -3 -1 NO
4 3 -1 YES
5 4 7 NO
6 4 -7 NO

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

Решение:

Изучив рисунок, находим координаты трех точек сегмента круга. После, находим координаты центра круга и его радиус с помощью данного сайта. Если проекция точки на ось [latex]OX[/latex] не находиться в области допустимых значений [latex]x[/latex], то точка не принадлежит сегменту круга в любом случае. Если же первое условие выполняется, то точка принадлежит сегменту круга тогда, когда квадрат расстояния ([latex]l[/latex]) от центра круга до точки меньше либо равно квадрату радиуса ([latex]r[/latex]) круга ([latex]r*r[/latex] >= [latex]l[/latex])

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

Ссылка на решение задачи на компиляторе ideone.com здесь.

ML14

Задача. Вычислить период колебания маятника длины [latex]l[/latex].

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

Длина нити маятника [latex]l[/latex].

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

Период колебаний маятника.

Тесты

Входные данные Выходные данные
1 0,3 1.09891
2 1 2.00632
3 40 12.6891

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

Пояснение

Условием задачи было вычислить период колебаний маятника [latex]T[/latex], имея длину маятника [latex]l[/latex]. Период колебаний маятника можно рассчитать с помощью формулы: [latex]T = 2\pi\sqrt{\frac{l}{g}}[/latex]. Мы объявляем три переменные типа [latex]double[/latex] [latex]T, l, g,[/latex] где [latex]T[/latex]-период колебаний маятника, [latex]l[/latex] — длина маятника,  [latex]g[/latex] = [latex]9.8075[/latex] — ускорение свободного падения на поверхности Земли в Одессе.  [latex]l[/latex]  — входной параметр. Затем, используя формулу [latex]T = 2\pi\sqrt{\frac{l}{g}}[/latex], вычисляем и выводим значение периода.

  • Условие задачи здесь.
  • Ссылка на решение на ideone.com здесь.

e-olymp 929 Параллелограмм

Задача взята с сайта e-olymp

Условие:

Задано 4 числа [latex]a, b, c, d[/latex] определяющие длины отрезков. Определить, можно ли с этих отрезков образовать параллелограмм.

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

В единственной строке задано 4 числа через пробел.

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

Вывести в единственной строке слово «YES«, если параллелограмм образовать можно или «NO» (без кавычек) в противном случае.

Тесты

Входные данные Выходные данные
1 2 4 2 4 YES
2 2 4 2.5 4 NO

Решение:

Параллелограммом  называется четырехугольник у которого противолежащие стороны равны. Чтобы четырехугольник со сторонами [latex]a, b, c, d[/latex] являлся параллелограммом должно выполнятся одно из трех условий:

[latex]a=c[/latex] и [latex]b=d[/latex];

[latex]a=b[/latex] и [latex]c=d[/latex];

[latex]a=d[/latex] и [latex]c=b[/latex],

Код на IDEONE можно увидеть здесь.

Ссылку на полностью засчитанное решение на сайте e-olymp.com можно найти здесь