e-olymp 978. Получи дерево

Задача с сайта e-olymp.com.

Условие

Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.

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

Первая строка содержит количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100) и количество ребер [latex]m[/latex] графа. Следующие [latex]m[/latex] пар чисел задают ребра графа. Гарантируется, что граф связный.

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

Выведите [latex]n — 1[/latex] пару чисел — ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

Код

Тесты

Ввод Вывод
4 4
1 2
2 3
3 4
4 1
1 2
2 3
3 4
6 7
1 2
2 3
3 4
4 5
5 6
6 1
1 2
2 3
3 4
4 5
5 6
6 5
1 2
2 3
3 4
4 5
5 6
1 2
2 3
3 4
4 5
5 6
4 5
4 3
2 4
2 3
1 2
1 3
4 3
2 4
1 2
6 9
1 2
1 3
1 5
2 5
2 4
3 5
3 6
4 5
5 6
1 2
1 3
1 5
2 4
3 6

Решение

Учитывая то, что по условию задачи нам дан связный неориентированный граф без петель и кратных ребер и то, что любое дерево с [latex]n[/latex] вершинами содержит [latex]n-1[/latex] ребро, то для получения дерева нужно удалить столько ребер, пока не останется [latex]n-1[/latex] ребро.

Данную задачу я решил, применяя упрощенный алгоритм Краскала, учитывая, что данное дерево не является взвешенным и сортировку применять не нужно.  Для начала объявляем наш исходный граф используя вектор ребер (edge). Структура ребер является простой и содержит в себе только информацию о вершинах, которое ребро соединяет. Алгоритм Краскала заключается в том, что мы каждую вершину помещаем в свое множество. Затем при просмотре каждого ребра исходного графа мы проверяем принадлежат ли вершины ребра одному множеству. Если нет, то добавляем данное ребро в наше дерево (предварительно его создав с помощью вектора ребер), после добавления мы добавляем все вершины, которые принадлежали тому же множеству, что и вторая вершина ребра, в множество первой вершины. Если же вершины уже принадлежат одному множеству, то переходим к следующему этапу цикла. После этой процедуры нам достаточно вывести на экран значения из нашего дерева — это и будут необходимые ребра.

UPD: обновил код, тесты, описание решения и ссылки.

A288

Задача A288

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

Даны целые числа [latex]a_{1}[/latex], …, [latex]a_{n}[/latex], каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются (+, –, +, –,  или –, +, –, +, … ), то ответом должна служить сама исходная последовательность. Иначе получить все отрицательные члены последовательности, сохранив порядок их следования.

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

Тесты

 

Входные данные Выходные данные
5 5 3 1 2 7 8 100000
-9 -5 -1 -3 -7 -4198 -852 -9 -5 -1 -3 -7 -4198 -852
5 -3 1 81 3 -7 1 -5 6 -3 -7 -5
-1 2 -8 995 -3 777 -42 -1 2 -8 995 -3 777 -42

Решение

Для решение данной задачи я воспользовался следующим алгоритмом. Заводим два целочисленных вектора, булеву переменную, которую мы будем проверять при печати и целочисленную переменную, которая будет являться первым элементом последовательности, а также начальным значением переменной [latex]tester[/latex], с которой будет сравниваться следующий элемент, а после этого его значение мы снова положим в [latex]tester[/latex].  В ходе цикла мы положительные числа кладем в один вектор, а отрицательные в оба. И в зависимости от того чередовались ли знаки или нет (значение переменной [latex]alternate[/latex]), мы печатаем нужный вектор.

e-olymp 1309. Блоки строки

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

Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.

Вычислить длины блоков строки S для всех позиций.

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

Единственная строка S (|S| ≤ 106).

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

В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.

Тесты:

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

 

 

 

Алгоритм

В данной задаче из-за того, что наша строка может принимать длину до  106 включительно, то необходим эффективный алгоритм. Я воспользовался алгоритмом вычисления Z-функции. Для начала мы заводим переменные left и right, в которых мы будем хранить координаты самого длинного отрезка, который совпадает с началом нашей строки. В начале цикла проверяем находится ли ячейчка, для которой ищется результат в отрезке между left и right. После прохождения цикла while, мы обновляем границы подстроки.

 

Код на ideone.com

Принятая задача на e-olymp.

e-olymp 2459. Юбилей Винни-Пуха

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

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

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

Входной файл содержит дату Юбилея Винни-Пуха в формате dd.mm.gggg. Гарантируется, что дата корректна.

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

В выходной файл нужно вывести YES, если дата, читающаяся справа налево корректна, и NO в противном случае.

 

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

Тесты

Входные данные Выходные данные
23.02.2002 YES
20.02.2023 NO
20.12.2015 NO
20.12.2051 YES

Решение

Как только получили строку из стандартного ввода, воспользуемся функцией reverse(). Эта функция записывает нашу строку «задом наперед», в это же время удаляя символ ‘.’ из строки. Так как я точно знаю, что строка из ввода записана верно, то я могу не проверять остальные символы. Пользуясь этим же фактом я завел три переменные целочисленного типа: day, month, year. В новой строке присутствуют только цифры, поэтому я присваиваю каждой новой переменной соответствующие подстроки, после приведения типа string к типу int с помощью функции stoi(). В выводе проверяется соответствуют ли значения дня и месяца требованиям. День проверяется с помощью функции get_days(). Она позволяет получить количество дней в зависимости от месяца и года. В самой функции get_days() используется функция is_leap(), которая проверяет год на високосность и возвращается булевское значение. В зависимости от этого значения, изменяется значение количества дней в феврале — 28 или 29 соответственно. Когда наши числа прошли все проверки, то мы получаем на вывод «YES», если новая дата является корректной или «NO» в ином случае.

 

Код на ideone.com

Засчитанная задача на e-olymp.com

MLoops 17

Задача

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

Замечание 1. В некоторых задачах появляется дополнительный параметр k < n.

Тесты

Входные данные Выходные данные
m n  k
13 31 9
5 8 4
20 20 3

 

 

Алгоритм

Программа выполняется с помощью двух циклов. Первый цикл отвечает за строки, второй за столбцы. Метод заключается в том, чтобы узнать, когда мы записываем именно ‘+’, а уже в остальные места записываем ‘.’.  Для начала проверяем делится ли номер строки, уменьшенный на 1, нацело на 6. Если да, то записываем +.  Далее проверяем, делится ли номер столбца,  уменьшенный на 1, на число [latex]k+1[/latex], где [latex]k[/latex] — вводимый параметр. Во всех остальных случаях пишем ‘.’.

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

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

 

MLoop 11

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

Вычислите с точностью \epsilon значение функции f\left( x \right) = \arccos x. При вычислениях допустимо использовать только арифметические операции.

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

 

Тесты

Входные данные Выходные данные Арккосинус
e x arccos = ([latex]\pi[/latex]/2 — f) Арккосинус
0.000001 0.866 0.523651 0.5236495809
0.01 0.5 1.04727 1.0471975512
0.00000000000001 0.35 1.21323 1.2132252231
0.00001 0.99 0.141873 0.1415394733

 

Решение

Для того, чтобы представить функцию f\left( x \right) = \arccos x необходимо воспользоваться формулой Тейлора, а именно рядом Маклорена для арккосинуса. Она имеет следующий вид:

[latex]\arccos x=\frac{\pi}{2}-\sum_{n=1}^\infty\frac{(2n)!}{4^{n}(n!)^{2}(2n+1)}x^{2n+1}[/latex]

Чтобы при вычислениях использовать только арифметические операции необходимо преобразовать это выражение. Первый член данной суммы — [latex]x[/latex]. Нужно узнать на что нужно домножить первый элемент, чтобы получить следующий. Для этого следует найти, чему будет равно отношение [latex]\frac{a_{n+1}}{a_{n}}[/latex]. В результате мы получим следующее: [latex]\frac{x^{2}(2n+1)^{2}}{2(n+1)(2n+3)}[/latex].

В функции [latex]f[/latex] переменная [latex]p[/latex] — слагаемые нашей суммы, а изначально — первый элемент. Также, в начале мы присвоили переменной суммы значение первого элемента. Затем в цикле мы домножаем наше слагаемое на полученный ранее коэффициент и складываем его с суммой до тех пор, пока значение [latex]p[/latex] превышает значение заданной точности [latex]e[/latex]. В основной части программы мы лишь выводим разность [latex]\pi/2[/latex] и нашей суммы. Это и будет значение арккосинуса.

 

Код на ideone.com