Mif 11

Задача

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

Тесты

 Входные данные Результат работы программы
 1 1
1 7
5 3
1 6
0
5 6
8 8
2 2
5 4
 2
 1 -1
1 -3
2 -2
4 -1
 1
 -5 -1
-5 -3
-2 -1
-3 -2
 2
 -1 1
-1 3
-4 2
-3 5
2.52982
 1 4
3 6
3 4
5 4
 1.41421

 

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

 

Решение

Основная идея состоит в том, что расстояние между непересекающимися отрезками [latex]AB[/latex] и [latex]CD[/latex] — это минимальная из длин, соединяющих вершины разных отрезков, и длин перпендикуляров, проведенных из вершины на противоположный отрезок. Подробнее о математической части поиска перпендикуляра тут. Кроме этого, отрезки могут пересекаться, что проверяется отдельно. В таком случае, расстояние между ними равно нулю.

Чтобы проверить, пересекаются ли отрезки, нужно сначала проверить, не параллельны ли они.Если они не параллельны, нужно найти точку пересечения прямых, на которых лежат отрезки, а затем проверить принадлежит ли она обоим отрезкам. Отрезки пересекаются тогда и только тогда, когда они лежат на пересекающихся прямых, точка пересечения которых принадлежит обоим отрезкам. Координаты точки пересечения находятся из системы уравнений прямых, на которых лежат отрезки.
[latex] \begin{cases} A_{1}x + B_{1}y + C_{1} = 0 \\ A_{2}x + B_{2}y + C_{2} = 0 \end{cases} [/latex]

Из первого уравнения: [latex]x = \frac{-B_{1}y-C_{1}}{A_{1}}[/latex]

Подставим  [latex]x[/latex] во второе уравнение:

[latex] \frac{A_{2}}{A_{1}}(-B_{1}y-C_{1}) + B_{2}y + C_{2} = 0[/latex]             [latex](*)[/latex]

Решив уравнение [latex](*)[/latex] получим:

[latex]y = \frac{C_{1}A_{2}-C_{2}A_{1}}{A_{1}B_{2}-A_{2}B_{1}}[/latex].

Тогда

[latex]x = \frac{C_{2}B_{1}-C_{1}B_{2}}{A_{1}B_{2}-A_{2}B_{1}}[/latex]

 

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

AL1

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

Вводится последовательность, состоящая из [latex]N[/latex] пар символов [latex](a_i, b_i)[/latex]. Каждая пара определяет порядок предшествования символов, например, пара [latex](b, c)[/latex] означает, что символ [latex]b[/latex] предшествует символу [latex]c[/latex]. Из порядка [latex](b, c)[/latex] и [latex](c, a)[/latex] следует порядок [latex](b, a)[/latex]. Необходимо определить, является ли введенная последовательность:

а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку [latex]A_{1},A_{2}, \cdots ,A_{s}[/latex] в порядке предшествования;

б) противоречивой, т.е. для некоторых символов [latex]x,y[/latex] можно получить одновременно порядок как [latex](x, y)[/latex] так и [latex](y, x)[/latex];

Тесты

Входные данные Результат
4
a b
b c
c d
b d
полный порядок
3
2 a
8 c
c b
порядок неполный
3
2 a
8 c
a 8
полный порядок
4
2 a
8 c
c 2
a c
Порядок противоречив
10
a 5
5 4
b 3
3 4
5 3
b 5
a b
4 *
* 0
4 0
полный порядок

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

Решение

Общая идея решения

Эта часть решения взята отсюда

Пусть при записи этих [latex]N[/latex] пар встретилось всего [latex]K[/latex] различных символов, которые образуют множество [latex]X[/latex].

Идея решения задачи состоит в последовательном присвоении каждому символу [latex]s[/latex] из [latex]X[/latex] номера, который определяет количество [latex]P(s)[/latex] элементов, предшествующих ему, с учетом свойства транзитивности (из [latex](c, b)[/latex] и [latex](b, a)[/latex] следует [latex](c, a)[/latex]). Это осуществляется следующим образом:

Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. [latex]P(s)=0[/latex] для любого [latex]s[/latex].

При просмотре очередной пары [latex](x, y)[/latex] символу y присваивается большее из значений [latex]P(x)+1, P(y)[/latex].

Очевидно, что при первом просмотре всех пар из входной последовательности определятся все упорядоченные цепочки длины 2, т.е. состоящие из 2 элементов. Поэтому номера некоторых элементов будут как минимум 1. При каждом из следующих просмотров входной строки возможно несколько вариантов.

  1. Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до [latex]K-1[/latex], то эта нумерация определяет полный порядок. Иначе порядок неполный.
  2. Номер некоторого символа превысил [latex]K-1[/latex]. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.

Легко понять, что число просмотров не превысит [latex]N[/latex].

Некоторые аспекты реализации

Нам необходимо будет несколько раз просматривать все пары, поэтому их не получится обрабатывать поточно. Будем хранить их в отдельном двумерном массиве.

Воспользуемся тем фактом, что символы воспринимаются компьютером, как числа. Заведем для номеров символов в последовательности массив chars на 256 элементов, поскольку тип данных char может принимать значения от 0 до 255. Это позволит обращаться к элементу массива, соответствующий какому-то символу напрямую, а не используя ассоциативный массив.  Это дает выигрыш в скорости, хотя и с некоторым увеличением расхода памяти.

Изначально каждый элемент массива chars пусть будет равен -1. Затем, пройдя все пары, присвоим каждому символу номер 0 в этом массиве. Таким образом, мы в дальнейшем сможем определить, что символ входит в нашу последовательность, поскольку его номер неотрицательный.

Если при очередном просмотре входной строки не произошло изменений, отсортируем массив номеров и проверим каждый ли предыдущий неотрицательный меньше следующего на 1.

ссылка на код на ideone

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

А282в

Задача

Даны действительные числа [latex]a_{1}, a_{2}, \cdots, a_{2n}.[/latex] Получить [latex]a_{1}+a_{2n}, a_{2}+ a_{2n-1}, \cdots, a_{n}+a_{n+1}.[/latex]

Тесты

Входные данные Выходные данные
 2 4 6 2 2 9 7 5 7 11 15 4
1 2 2 1 1 4
139 64 15 20 10 5 6 1 140 70 20 30
 111111 22222 33333 11 25 4 111115 22247 33344
15 7 6 9 24 13
2 2 4
138 56 78 3 141 134

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

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

Считаем все числа [latex]a_{1}, \cdots, a_{2n}[/latex] в ранее объявленный вектор, пока есть, что считывать. Поскольку мы используем класс vector и цикл  while (cin >> b)  и метод push_back(), в числе [latex]n[/latex] нет необходимости, а во входых данных присутствуют только сами числа [latex]a_{1}, \cdots, a_{2n}[/latex]. Далее, чтобы узнать количество элементов в векторе, будем использовать метод size(). Остается только выводить в цикле сумму двух текущих чисел, начиная с краев вектора и сдвигаясь в каждом витке на элемент ближе к центру вектора, пока не дойдем до центра.

Ссылки

Задача взята из задачника С. Абрамова;
Ссылка на код на ideone.com.

e-olymp 6124. Стек неограниченного размера

Задача

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

push n

Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из стека последний элемент. Программа должна вывести его значение.

back

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

size

Программа должна вывести количество элементов в стеке.

clear

Программа должна очистить стек и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и popпрограмма должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.

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

Описаны в условии.

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

Описаны в условии.

Тесты:

 ввод  вывод ввод вывод
push 7
clear
push 4
back
push 1151
back
pop
back
size
exit
ok
ok
ok
4
ok
1151
1151
4
1
bye
 push 2
push 7
back
pop
pop
back
push 1
back
pop
exit
ok
ok
7
7
2
error
ok
1
1
bye
pop
push 42
back
size
pop
size
push 17
push 19
push 24
back
size
clear
size
exit
error
ok
42
1
42
0
ok
ok
ok
24
3
ok
0
bye
back
size
clear
size
back
pop
push 2
pop
push 1
size
back
exit
error
0
ok
0
error
error
ok
2
ok
1
1
bye

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

Решение

В данном решении стек состоит из объектов, далее именуемых звеньями, каждый из которых состоит из массива, переменной, отвечающей свободному месту в массиве, ссылки на следующее звено. Кроме того, у звена есть метод для его создания, методы push и pop. В этих методах, кроме их прямой функции, отслеживается количество свободного места в звене. С этим всем работает сам стек. В самом стеке есть указатель на первое звено (звено, в которое был добавлен последний элемент, который все еще есть в стеке) и переменная S, отвечающая количеству элементов в стеке. Еще есть такие методы, как создание и удаление звена, а также все методы указанные в условии.  Создается звено, если нужно что-то добавить в стек и в текущих звеньях уже нет свободного места, а удаляется, если после извлечения чего-то из стека первое звено пустое (или при методе clear). Для этого и нужна переменная отвечающая свободному месту в звене.

Теперь немного о методах, указанных в условии. Во-первых, все методы, меняющие число элементов в стеке, соответственно влияют на переменную, этому числу отвечающую, а size ее просто возвращает. Методы push и pop непосредственно для выполнения своей функции обращаются к своим аналогам в первом звене. Методы pop и back проверяют в начале, не пуст ли стек, через переменную S. Back получает значение последнего элемента, работая непосредственно с массивом первого звена. exit вообще не создан, как метод, а обрабатывается непосредственно в функции Main().  Собственно, сама эта функция только принимает и обрабатывает через условные операторы запросы, а потому описывать ее нет смысла (см. код программы).

Немного слов для обобщения. Если бы стек бы основан просто на массиве, для неограниченности пришлось бы каждый раз, когда в текущем массиве заканчивается место, копировать уже имеющиеся данные в новый массив большего размера. Кроме того, возникла бы необходимость в очень большом цельном участке памяти. Если бы в этой реализации стека вообще не использовались массивы, а просто у каждого элемента была ссылка на следующий, это бы очень увеличило затраты памяти, т.к. эти ссылки в количестве, равном количеству элементов в стеке, нужно где-то хранить.  В данном же решении нужно какое-то количество цельных, но не таких больших участков памяти, не так много памяти под ссылки на следующее звено, а при заполнении имеющихся массивов ничего не приходится переписывать — просто добавляется еще один. Примечание: эффективность для разных задач зависит от размеров массива в звене.

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

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

ссылка на код на ideone

 

MLoop14

Задача

 

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

Тесты

Аргумент функции Точность Результат программы Результат сайта wolframalpha
1,6 0,000001 -0,029212 -0.0292120
0,5 0,001 1,83 1,83049
2 0,00001 -0,45766 -0,45765155….
-0,4 0,0001 -2,3652 -2,36522
-1 0,0001 -0,6421 -0,64209261…

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

 

Решение

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

Ряд Маклорена для синуса: [latex]\sin{x}= [/latex] [latex] x — \frac{x^{3}}{3!} + \frac{x^{5}}{5!} — [/latex] …

Ряд Маклорена для косинуса: [latex]\cos{x}= [/latex] [latex]1 — \frac{x^{2}}{2!} + \frac{x^{4}}{4!} — [/latex] …

Отсюда видно, что [latex]n[/latex]-е слагаемое ряда для синуса равно [latex] n[/latex]-ому слагаемому ряда для косинуса, умноженному на [latex] \frac{x}{2 \cdot n+1} [/latex]. Запускаем цикл, работающий, пока модуль разности между предыдущим и следующим значением котангенса больше заданной точности, в котором каждый раз прибавляем к рядам их следующие слагаемые.

В функции int main() считаем количество знаков числа, которое нам нужно вывести, через цикл, а затем пользуемся функцией precision и выводим результат.

Примечание: Поскольку в условии разрешается пользоваться только арифметическими операциями, а модуль не совсем является таковой, я не стал пользоваться стандартной функцией Abs(), а вписал в программу ее замену. 

ссылка на код на ideone

MLoops12

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел n > 0 (количество столбцов) и m > 0 (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр k < n.
Замечание 2. Многоточие означает продолжение последовательности
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться  Онлайн-энциклопедией целочисленных последовательностей.

 

Тесты

n m k Результат
15 9 4
 10  7  3
 12  5  2
 25  15  7

 

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

Решение

Закономерности в таблице

  1. Через каждые [latex]k[/latex] строк, начиная с нулевой, встречается строка, в которой нулевой и каждый [latex]k[/latex]-й символы — «+», а остальные — «-«. Такие строки разделяют одинаковые [latex]k[/latex]-местные блоки строк.
  2. Каждая строка блока строк содержит, в свою очередь, [latex]k[/latex]-местные блоки символов (эти блоки уже разные), разделенные символами «|». В каждой строке из блока два вида блоков символов (далее блок 1 и блок 2). Все нечетные блоки имеют вид блока 1, четные — блока 2.
  3. Блок 1 содержит числа по возрастанию, начиная с номера строки в блоке строк, до [latex]k[/latex] включительно, т.е. числа из сегмента [latex][i ; k][/latex], где [latex]i[/latex] — номер строки в блоке строк. После них в блоке записаны числа от [latex]1[/latex]  до номера строки в блоке, не включая сам этот номер, т.е. числа из полусегмента [latex][1 ; i)[/latex].
  4. Блок 2 каждой строки содержит те же числа, что и блок 1, но записанные в противоположном порядке.

Реализация

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

ссылка на код на ideone