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

e-olymp 517. Задачка от Николая

Задача на e-olymp

Приближается Новый год! Третьеклассники уже мечтают побывать возле новогодней елки в Киеве. Учительница математики одного из 3-х классов г. Александрия им сообщила, что она сможет свозить на ёлку в Киев только тех учеников, которые решать задачку от святого Николая. Он хочет узнать качество заданного числа.

По мнению Николая, качеством числа [latex]N[/latex] является сумма цифр всех натуральных чисел [latex] A[/latex] не больших самого числа [latex] N[/latex] таких что остаток от деления числа [latex] N[/latex] на число [latex] A[/latex] равен [latex] 0[/latex] .

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

Первая строка содержит натуральное число [latex]N[/latex] – количество учеников в 3-м классе. В последующих [latex]N[/latex] строках размещены задания для каждого ученика: натуральное число не больше чем [latex] 15 000 000[/latex] (Николай решил пожалеть учеников и числа выбрал не очень большие)

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

Для каждого из чисел, заданных Николаем ученикам, укажите его качество.

Код:

Тесты:

Количество строк 1 задание 2 задание Вывод
2 2 10 3; 9
2 2 1500000 3; 666
2 5 9 6; 13
2 60 15000000 42; 978
2 1 0 1; 0

Решение

В данной задаче я выделил отдельную функцию — [latex]SumOfDigit()[/latex]. Не трудно догадаться, что она считает сумму цифр числа для будущих вычислений. Для первого цикла мы сначала должны ввести число [latex]N[/latex] — количество заданий для учеников. Именно столько раз будет выполняться основной цикл. Чтобы определить качество числа, необходимо найти все его натуральные делители. Для решения данной задачи я воспользовался методом перебора всех чисел до корня из исходного, что значительно ускоряет вычисление по сравнению с перебором вплоть до самого числа. Во внутреннем цикле проверяется каждое число, и если оно удовлетворяет условию, то вызывается функция [latex]SumOfDigit[/latex], а в переменную [latex]sum[/latex] записываются значения сумм.

Данная строка необходима для проверки, если исходное число является квадратом.

В конце основного цикла программа печатает на экран качество данного числа.

Данная задача решалась совместно со Стасом Коциевским на факультативе.

Код на ideone.com

Принятое решение на e-olymp

Mif 17.19

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

file
Тесты:

[latex]x[/latex] [latex]y[/latex] Вывод
-3 0 no
-1.5 2 yes
2 5 yes
3 4 yes
3 3 no

 

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

 

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

В данной программе проверяются допустимые значения [latex]x[/latex] и [latex]y[/latex], при которых точка с данными координатами может принадлежать данной фигуре. Если координаты соблюдают все условия, то программа выводит «yes», т.е. принадлежит . В остальных случаях на экран выводится «no».

Ю2.28

Задача.

Вклад. Банк предлагает 3 вида срочных вкладов: на 3 месяца под [latex]p_{1}[/latex]%, на 6 месяцев под [latex]p_{2}[/latex]% и на год под [latex]p_{3}[/latex]%. Какой из вкладов наиболее выгоден для вкладчика?

Тесты:

[latex]p1[/latex] [latex]p2[/latex] [latex]p3[/latex] Вывод программы
0 0 0 Нет наиболее выгодного вклада из трех
10 10 10 Первый вклад выгоднее
10 10 50 Третий вклад выгоднее
50 10 10 Первый вклад выгоднее
5 20 20 Второй вклад выгоднее

 

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

 

 

 

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

Для решения этой задачи я пользовался следующей формулой: [latex]B = A(1 + \frac{P}{100\%})[/latex], где [latex]B[/latex] — будущая стоимость, [latex]A[/latex] — текущая стоимость, [latex]P[/latex] — процентная ставка за расчетный период, [latex]n[/latex] — количество расчетных периодов. В программе я ее представил в другом виде, так как для сравнения выгодности вкладов одинаковой суммы, саму сумму можно не учитывать.

Код на ideone.com

ML21

Задача. Найти сумму членов арифметической прогрессии a, a+d, a+2d \dots, a+(n-1)d по данным значениям a, d, n.

Тесты:

[latex]a[/latex] [latex]d[/latex] [latex]n[/latex] [latex]Sn[/latex]
8 657 0 0
5 0 2 10
5 8 1 5
0 5565 88 21302776

Код:

Алгоритм.

В данной программе я воспользовался формулой суммы арифметической прогрессии. А именно [latex] S_{n} = \frac{a_{1} + d(n — 1)}{2} * n [/latex], где [latex]a_{1}[/latex] — первый член арифметической прогрессии, [latex]d[/latex] -разница арифметической прогрессии и [latex]n[/latex] — номер последнего члена суммы. Программа же просто выводит результат данных вычислений на экран.

e-olymp 931. Отношение произведения к сумме

Задача с сайта e-olymp #931.

Ссылка на засчитанное решение

Вычислить отношение произведения цифр натурального числа к их сумме.

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

Натуральное число n, не превышающее 2·109.

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

Вывести отношение произведения цифр числа n к их сумме с 3 десятичными цифрами.

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

Для решения данной задачи я вывел две функции, до главной, а именно — функцию умножения цифр натурального числа и функцию сложения цифр натурального числа, которыми воспользуемся в дальнейшем.

В главной же функции мы выводим отношение произведения цифр к их сумме, округленное до третьего знака после запятой.

Более краткий вариант программы.