e-olymp 1108. Червячные дыры

Условие:

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

  • Червячные дыры являются односторонними.
  • Время путешествия по любому тоннелю равно нулю.
  • Червячная дыра имеет два конца, каждый из которых находится в звездной системе.
  • Звездная система в своих границах может иметь несколько концов червячных дыр.
  • По некоторой неизвестной причине начиная с нашей Солнечной системы всегда можно достигнуть любую другу звездную систему перемещаясь некоторой последовательностью червячных дыр (возможно, это потому что Земля является центром универсума).
  • Между любой парой звездных систем существует не более одной червячной дыры в любом из направлений.
  • Оба конца червячной дыры не могут находиться в одной звездной системе.
  • Каждая червячная дыра перемещает путешественника на определенное константное количество лет вперед или назад. Например, одна дыра может переместить на 15 лет в будущее, а другая на 42 года в прошлое.

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

Ученый хочет достигнуть цикла червячных дыр, который поможет ему попасть в прошлое. Двигаясь по этому циклу несколько раз, можно прийти ко времени, когда имел место Большой Взрыв и наблюдать его собственными глазами. Напишите программу, которая определяет существование такого цикла.

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

Первая строка содержит количество звездных систем n (1n1000) и количество червячных дыр m (0m2000). Звездные системы пронумерованы от 0 (наша солнечная система) до n1. Каждая червячная дыра описывается в отдельной строке и содержит три целых числа x, y и t. Эти числа указывают на возможность передвижения из звездной системы с номером x в звездную систему с номером y, при этом время изменяется на t (-1000t1000) лет.

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

Cтрока содержит информацию, возможно ли в заданном множестве систем попасть в минус бесконечность во времени используя червячные дыры. Выводить следует строку «possible» или «not possible«.

Тесты:

Входные данные Выходные данные
3 3
0 1 1000
1 2 15
2 1 -42
possible
4 4
0 1 10
1 2 20
2 3 30
3 0 -60
not possible
3 3
0 1 -100
1 2 1
2 1 0
not possible

Решение:

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

Решение данной задачи сводится к нахождению отрицательного цикла в ориентированном графе. Необходимо воспользоваться алгоритмом Форда-Беллмана. Создадим вектор на [latex]n[/latex] элементов и заполним его нулями. Алгоритм основан на том, что если в графе размерностью [latex]n[/latex] элементов нет отрицательных циклов, то после [latex]n-1[/latex] прохождения, изменения в массива кратчайших расстояний не будет. Поэтому, будем выполнять следующее [latex]n[/latex] раз:

  1. Возьмем первое ребро из вектора [latex]canals[/latex], и проведем сравнение: если исходная длина пути конца данного ребра из исходного вектора [latex]distance[/latex] больше, чем сумма длины пути начала вектора и стоимости прохода по данному ребру [latex]canals[].t[/latex], то изменим в векторе [latex]distance[/latex] элемент с номером конца исходного ребра, и изменим индикатор изменений [latex]x[/latex], чтобы показать, что в ходе данного прохода были внесены изменения.
  2. Переходим к следующему ребру.

Если после во время последнего прохода ни разу не была изменена переменная [latex]x[/latex], то это значит, что в графе нет циклов отрицательной длины, и тогда выводим «not possible». Иначе, выводим «possible».

Засчитанное решение на e-olymp.com.

Код решения на ideone.com.

e-olymp 1948. Топологическая сортировка

Условие:
Дан ориентированный невзвешенный граф. Необходимо топологически отсортировать его вершины.

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

В первой строке содержатся количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100000) и количество рёбер [latex]m[/latex] (1 ≤[latex]m[/latex] ≤ 100000) в графе. В следующих [latex]m[/latex] строках перечислены рёбра графа, каждое из которых задаётся парой чисел — номерами начальной и конечной вершины.

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

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, то вывести -1.

Тесты:

Входные данные Выходные данные
6 6
1 2
3 2
4 2
2 5
6 5
4 6
4 6 3 1 2 5
2 2
1 2
2 1
-1
4 5
1 2
1 3
3 4
2 4
1 4
1 3 2 4
4 5
1 2
1 3
3 4
2 4
4 1
-1

Решение:

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

Для решения данной задачи необходимо было воспользоваться алгоритмом топологической сортировки, посредством поиcка в глубину. Чтобы применить данный алгоритм, необходимо было проверить граф на ацикличность с помощью алгоритма поиска в глубину. Это было реализовано функцией [latex]cyclic[/latex], которая проходила по всему графу в поиске цикла. Если цикл был найден, то функция меняла значение переменной [latex]cycle_st[/latex]. Далее, если цикл был найден, то программа выводить -1, иначе применяется алгоритм топологической сортировки, реализованный в двух функциях:

и

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

Засчитанное решение на e-olymp.com.

Код решения на ideone.com.

A298

Условие взято со сборника задач С.Абрамова и др.

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex],[latex]b_1,\ldots,b_n[/latex]. Преобразовать последовательность [latex]b_1,\ldots,b_n[/latex] по правилу: если [latex] a_i \leq 0[/latex], то [latex]b_i[/latex] увеличить в 10 раз, иначе [latex]b_i[/latex] заменить нулем [latex](i=1,\ldots,n[/latex]). Данные принимать до конца входного потока.

Тесты:

Входные данные Выходные данные
1 -1 0 12 4 5 0 1 2 3 4 5 6 -1 0 12 4 5 0 10 20 0 0 0 60
2 0 2147483647 0 21474836470
3 1 2 3 4 5 6 7 8 0 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 90 100

Решение:

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

При решении данной задачи был использован тип данных [latex]long long[/latex], так как было необходимо охватить как можно больший диапазон значений. Заданные последовательности чисел будем хранить в одном векторе [latex]a[/latex], где последним элементов первой последовательности будем элемент под номером [latex]a.size()/2-1[/latex]. Отсюда, в цикле будем просматривать каждый элемент первой последовательности. Если данный элемент не положителен, то увеличим в 10 раз соответствующий элемент второй последовательности, иначе, присвоим ему значение нуля. Номер в векторе соответствующего элемента из второй последовательности можно найти по формуле [latex]a.size()/2+i[/latex], где [latex]i[/latex] — это номер элемента из первой последовательности. После прохода по всей первой последовательности, выведем весь вектор на экран.

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

MLoop 8

Условие:

Вычислите с точностью [latex]\varepsilon[/latex] значение функции [latex]f(x)=e^x[/latex]. При вычислениях допустимо использовать только арифметические операции.

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

В единственной строке указаны два числа, разделенные пробелом: аргумент функции [latex]x[/latex] и точность [latex]\varepsilon[/latex].

Тесты:

Входные данные Выходные данные
[latex]x[/latex] [latex]\varepsilon[/latex] Результат
1 0.1 2.70833
1 0.001 2.71825
12 0.072 2.4155e+07

Решение:

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

Для нахождения значения функции [latex]f(x)=e^x[/latex] (экспоненты) с точностью [latex]\varepsilon[/latex] воспользуемся формулой разложения Тейлора: [latex]f(x)=e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots =\sum_{n=0}^{x^n}, x\in \mathbb{C}[/latex]. Запишем рекуррентное соотношение для нахождения каждого последующего члена: [latex]x_{n}=x_{n-1}\cdot\frac{x}{n}[/latex].Для нахождения искомого результата, будем прибавлять к значению [latex]result[/latex] новые члены до тех пор, пока они по модулю не станут меньше, чем [latex]\varepsilon[/latex].

Ссылка на код.

 

e-olymp 2034. WERTYU

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

Обычная ошибка при наборе состоит в том, что вы помещаете ваши руки на клавиатуру на один ряд правее верной позиции. Тогда «Q» печатается как «W«, «J» печатается как «K» и т.д. Ваша задача состоит в расшифровке сообщения, напечатанного таким образом.

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

Входные данные состоят из нескольких строк текста. Каждая строка может содержать цифры, пробелы, прописные буквы (кроме Q, A, Z) и знаки препинания, показанные выше [кроме обратной кавычки (`)]. Клавиши, обозначенные словами [Tab, BackSp, Control и т.д.], не представлены во входных данных.

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

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

Тесты:

Входные данные Выходные данные
O S, GOMR YPFSU/ I AM FINE TODAY.
JS;=0— HAL-9000
OY OD S MOVR MOHJY GPT VPFOMH IT IS A NICE NIGHT FOR CODING

Решение:

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

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

Для каждой строки будем просматривать все символы, и для каждого из них будем использовать следующий алгоритм:

  1. Если данный символ пробел — то выведем его на экран.
  2. Иначе, с помощью функции [latex]find[/latex]_[latex]first[/latex]_[latex]of()[/latex] найдем номер вхождения данного символа в проверочном массиве [latex]y[/latex], и выведем предыдущий элемент из этого массива.
  3. Повторяем пункты 1, 2 до тех пор, пока не дойдем до конца строки [latex]x[/latex]. После этого перейдем на новую строку с помощью команды [latex]endl[/latex].

Условие задачи на сайте e-olymp.com можно найти здесь.

Решение, что зашло на 100%.

Код решения можно проверить здесь.

Mif 17.18

Gresh
Условие:

Принадлежит ли точка ([latex]x[/latex];[latex]y[/latex]) фигуре на рисунке? Вариант 18.

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

Два числа — координаты точки.

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

Слово «Yes», если точка принадлежит фигуре, в противном случае -«No».

Тесты:

[latex]x[/latex] [latex]y[/latex] Result
6 0 Yes
0 0 Yes
5 2 No
-6 1 No

 

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

Точка будет принадлежит фигуре тогда и только тогда, когда будут выполняться группы условий: или оба числа не отрицательные и их сумма не превышает 6, или оба числа не положительные, и их сумма не меньше 6. если одно из этих условий выполняется, то выводим «Yes», а иначе — «No».

Здесь решенная задача на сайте ideone.com.

Ю2.30. Отрезки на плоскости

Задача взята со сборника задач Юркина А. Г.

Условие:

Найти расстояние между двумя произвольно заданными на плоскости отрезками.

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

8 чисел, пары координат каждого конца отрезков.

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

Минимальное расстояние между отрезками.

Тесты:

[latex]x_1[/latex] [latex]y_1[/latex] [latex]x_2[/latex] [latex]y_2[/latex] [latex]x_3[/latex] [latex]y_3[/latex] [latex]x_4[/latex] [latex]y_4[/latex] Минимальное расстояние
0 0 2 2 1 1 0 3 0
1 2 3 2 2 1 2 0 1
1 1 3 1 1 2.5 3 2.5 1.5
1 -1 3 -1 1 2.5 3 3.5 3.5

Решение:

 

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

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

1.Нахождение расстояния между концами двух отрезков.

2.Нахождение длины перпендикуляров, опущенных с концов одного отрезка на другой. 

1.Расстояние между двумя точками [latex]M_1(mx_1,my_1), M_2(mx_2,my_2)[/latex] находится по формуле [latex]\sqrt{(mx_2-mx_1)^2+(my_2-my_1)^2}[/latex]. Сначала, переменной [latex]mini[/latex] присваиваем значение расстояния между первой парой концов отрезков:

Далее, для всех остальных пар концов отрезков находим расстояние между ними, и если оно меньше чем [latex]mini[/latex], то меняем его значение.

После 4 проверок получаем минимальное расстояние между концами двух отрезков.

После этого переходим к пункту 2.

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

Продемонстрируем решение для отрезка с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex], и точки с координатами [latex](x_3, y_3)[/latex]

Первое уравнение имеет вид [latex](x-x_1)/(x_2-x_1)=(y-y_1)/(y_2-y_1)[/latex], а второе : [latex]-(x_2-x_1)/(y_2-y_1)*(x-x_3)=y-y_3[/latex]. Решив эту систему, получаем, что

и

Если делитель в [latex]x[/latex] равен нулю, то это означает, что проекция лежит на начале перпендикуляра, то есть они совпадают, и в таком случае присваиваем координатам проекции значения координат точки, с которой опускался перпендикуляр.

Получили абсциссу и ординату проекции точки на отрезок. Необходимо проверить, принадлежит ли эта проекция отрезку, для этого воспользуемся функциями [latex]min[/latex] и [latex]max[/latex], чтобы определить большие из координат отрезка, и операций сравнения:

Если условия выполняются, то находим длину перпендикуляра по аналогии с расстоянием между концами отрезков, и сравниваем с [latex]mini[/latex]. Если длина меньше, то меняем значение минимума.

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

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

Выводим его на экран и переходим на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

 

 

e-olymp 36. Змей Горыныч

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

Условие:

В некотором царстве жил Змей Горыныч. У него было [latex]N[/latex] голов и [latex]M[/latex] хвостов. Иван-царевич решил уничтожить губителя человеческих душ, для чего ему его кума Баба Яга подарила волшебный меч, так как только им можно убить Змея Горыныча. Если отрубить одну голову, то на её месте вырастает новая, если отрубить хвост, то вместо него вырастет 2 хвоста. Если отрубить два хвоста, то вырастает 1 голова, и только когда отрубить 2 головы, то не вырастет ничего. Змей Горыныч гибнет только в том случае, когда ему отрубить все головы и все хвосты. Определить минимальное количество ударов мечом, нужное для уничтожения Змея Горыныча.

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

Два числа [latex]N[/latex], [latex]M[/latex] ([latex]0[/latex] [latex]<=[/latex][latex]N[/latex], [latex]M[/latex][latex]<=[/latex][latex]1000[/latex]).

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

Единственное число – минимальное количество ударов мечом, или -1, если уничтожить Змея Горыныча невозможно.

Тесты:

N M Количество ударов
3 3 9
3 0 -1
0 9 12
0 0 0
3 2 3
19 114 95

Решение

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

При решении данной задачи было рассмотрено несколько случаев.

  • Змея Горыныча убить невозможно. Это возможно только в том случае, когда у него нечетное количество голов, и нет ни одного хвоста, так как при наличии хотя бы одного хвоста становится возможным увеличение количества хвостов и голов до необходимого, путем отрубания одного, или двух хвостов соответственно. Чтобы определить возможность уничтожения Змея, делаем проверку: если количество голов нечетное и хвостов нет, то выводим «-1». Если эти условия не выполняются, то переходим ко второму пункту решения.
  • Змей Горыныч может быть убит. Это означает, что у Змея есть хотя бы один хвост, или четное количество голов. В таком случае, мы работаем внутри цикла, при каждом проходе которого проверяется, выполняются ли описанные выше условия:

    Горыныча можно убить тогда и только тогда, когда при отрубании всех хвостов получается четное количество голов. Отсюда, необходимо, чтобы у Змея было четное количество хвостов, и сумма голов и количества хвостов, деленного на два, была четным числом. Поэтому будем работать по простому алгоритму:
  1. Если количество хвостов [latex]M[/latex] нечетное, то отрубаем один хвост, на месте которого вырастает два новых, и увеличиваем счетчик ударов [latex]count[/latex] на один.
  2. Если количество голов нечетное, и хвостов больше одного, то отрубаем два хвоста, тем самым увеличивая количество голов на 1, и увеличиваем счетчик.
  3. Если количество голов и хвостов четное, и если количество хвостов при делении на два дает четное число, то мы увеличиваем счетчик на  [latex]M/2+((N+M/2)/2)[/latex], и приравниваем количество голов и хвостов нулю.
  4. Если какое-то из условий пункта 3 не выполняется, то увеличиваем количество хвостов на 1, и увеличиваем счетчик ударов.
  5. Повторяем алгоритм до тех пор, пока не убьем Горыныча.

После выхода из цикла в счетчике [latex]count[/latex] находится минимальное число ударов, необходимое для уничтожения Змея Горыныча. Выводим его на экран, и переходим на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

Для перехода к странице на e-olimp с полностью выполненным данным заданием щелкните здесь.

ML 20

Задача

Найти площадь кольца, внутренний радиус которого равен [latex]r[/latex], а внешний – [latex]R[/latex] ([latex]r<R[/latex]).

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

В единственной строке указаны внешний и внутренний радиусы, разделенные пробелом.

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

Единственное число — площадь кольца.

Тесты:

R r Площадь кольца
3 2 15.708
12.921 7.903 328.28
25 3.5 1925.01
10.2531 1 327.122

Решение:

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

При решении данной задачи использовались две переменные типа [latex]double[/latex]. Так как в постановке задачи не было указано, какими могут быть числа, то для обхвата наибольшего диапазона чисел разумно использовать именно этот тип данных. Помимо этого, была использована константа из математической библиотеки [latex]cmath[/latex], а именно, константа числа [latex]\pi[/latex]: [latex]M[/latex]_[latex]PI[/latex].

Чтобы найти площадь кольца, образованного двумя окружностями, необходимо найти площадь круга, образованного внешним радиусом кольца, по формуле [latex]\pi\cdot R^2[/latex], и площадь круга, образованного внутренним радиусом кольца, по формуле [latex]\pi\cdot r^2[/latex]. Затем, из площади большего круга вычесть площадь меньшего.

Получаем формулу: [latex]\pi\cdot R^2 — \pi\cdot r^2[/latex]. Подставляя в формулу переменные и константы, получаем:

После выполнения всех операций перейдем на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

e-olymp 906. Произведение цифр

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

Условие

Задано трицифровое число. Определить произведение его цифр.

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

В единственной строке заданное трицифровое число.

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

В единственной строке произведение цифр заданного числа.

Тесты

# Входные данные Результат
1 235 30
2 106 0
3 111 1

Решение

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

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

Для разбиения на цифры воспользуемся формулой:

В данной формуле в первом множителе мы получаем первую цифру, во втором — вторую, и в третьем соответственно третью.

После выполнения всех операций перейдем на новую строку с помощью команды endl.

Для перехода к странице на e-olimp с полностью выполненным данным заданием щелкните здесь.