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

e-olymp 901.Количество операций

Задача.

Определить общее количество операций сложения (+), вычитания () и умножения (*) в заданном арифметическом выражении.

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

В единственной строке задано арифметическое выражение, не содержащее скобок и пробелов. Количество символов в выражении не превышает 250.

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

Единственное число — количество указанных операций.

Тесты:

входящая строка результат первой программы результат второй программы результат третей программы
-5+20-a+2*c 4 4 4
20+40-a 2 2 2
-2+2+2+2-a*4*6-2*5- 8 8 8
2+6*6 2 2 2

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

Первый способ. Потоковая обработка символов.

Второй способ. c-string.

Третий способ. Класс string.

 

Решение.

Чтобы подсчитать количество операций, указанных в условии, необходимо подсчитать символы которые соответствуют этим операциям и находятся между переменными или числами. проверять только предыдущий и следующий символ на то, является ли он буквой (значит, он является частью переменной или переменная) или цифрой (значит, он является частью числа или числом). В первой программе это осуществляется потоковой обработкой символов с запоминанием последующего и предыдущего, во второй — созданием массива символов c-string и использованием функции strpbrk, в третей — созданием объекта класса string и использованием функций find_first_of, find_last_of.

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

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

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

Первый способ

Второй способ

третий способ

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

Первый способ

Второй способ

третий способ

e-olymp 474. Максимум

Задача.

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

Он предложил Васе находить суммы цифр последовательных чисел — 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 — и так далее, пока Васе не надоест. Вася оказался в восторге от идеи и принялся за работу. За вчерашний день Вася нашёл суммы цифр каждого из чисел от 1 до 115. Посмотрев на результаты младшего брата, Петя заметил, что суммы цифр последовательных чисел не являются случайными, часто они идут подряд, но полностью закономерность он так и не понял.

Чтобы найти закономерности, Петя решил исследовать крайние случаи, например, какое из чисел даёт максимальную сумму цифр. Данных для чисел до 115 оказалось недостаточно для окончательных выводов, и Пете пришла в голову идея для ускорения вычислений использовать вместо братика компьютер. Поскольку сам он в программировании не очень силён, он обратился за решением этой задачи к Вам.

.

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

В первой строке входных данных находится число N (1 <= N <= 2 147 483 647).

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

Выведите число от 1 до включительно с максимальной суммой цифр. Если чисел с максимальной суммой цифр несколько, выведите наибольшее из них.

Тесты:

число N результат
1 1
98 98
13759 9999
999756 998999
2147483647 1999999999

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

 

Решение.

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

Сумму цифр и их количество в числе считают две простых в написании функции, степени (i-я и i+1-я)десятки считаются непосредственно в основном цикле.

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

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

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

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

примечание: ссылка на код может выдавать старый вариант кода, где [latex]a[/latex] и [latex]b[/latex] считаются отдельно, а не [latex]b[/latex] выражается через [latex]a[/latex], как в этом коде, в связи с техническими проблемами на ideone. Этот вариант тоже проходит все тесты, однако является несколько менее эффективным. 

Mif 17.7

Задача.

Принадлежит ли точка ([latex]x[/latex];[latex]y[/latex]) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Новый текстовый документ1

Тесты:

[latex]x[/latex] [latex]y[/latex] Результат
 -6  3 принадлежит
 0 0  не принадлежит
 2 -4  не принадлежит
 — 1 2 принадлежит
 -5 -2  принадлежит

 

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

Решение.

В данной задаче необходимо проверить подходят ли координаты точки под условия, описывающие фигуру. В этом варианте фигуру можно разбить на 2 прямоугольника. Тогда вышеуказанные условия выглядит так: [latex]-6<=x<=-1[/latex] и [latex]2<=y<=7[/latex] (это первый прямоугольник) или [latex]-6<=x<=-3[/latex] и [latex]-3<=y<=2[/latex] (соответственно, второй прямоугольник).

Здесь находится условие задачи

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

ML11

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

Определить время падения камня на поверхность земли с высоты h.

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

Для начала оговорим трактовку условия задачи.

  1. Поскольку в условии ничего не говорится про начальную скорость камня, будем считать ее равной нулю.
  2. Аналогично в условии ничего не говорится про точность результата.  От этого зависит как округление до определенного количества знаков после запятой в выводе, так и то, с какой точностью следует указать ускорение свободного падения, поскольку каноны физики требуют, чтобы ответ на физическую задачу указывался с точностью наимение точно указанного в условии данного. В данном решении я взял значение [latex]g[/latex] свойственное Одессе с точностью 4 значка после запятой. Соответственно, ответ будет выводиться с такой же точностью.
  3. Предполагается что высота и время должны указываться в СИ

Тогда наша рабочая формула выглядит следующим образом: [latex]\sqrt{\frac{2 \cdot h}{g}}[/latex], где [latex] g=9.8075 \frac{m}{s^2}[/latex]. Вводить в программе [latex] g [/latex], как отдельную переменную или константу нет смысла, т.к. она используется только раз. Поэтому в коде вместо [latex] g [/latex] стоит просто ее значение.

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

 

 

Тесты

Для тестов я выбирал такие числа, чтобы было удобно считать для [latex]g=10\frac{m}{s^2}[/latex]. Тогда первый результат, полученный при выполнении программы, должен при округлении быть равен результату подсчета вручную при [latex]g=10\frac{m}{s^2}[/latex]

Высота (м) время (сек)
0 0
5 1.0098
20 2.0195
80 4.0391

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

e-olymp 918. Какая четверть?

Задача. Задана точка с координатами [latex]x[/latex] и [latex]y[/latex]. Определить, в какой координатной четверти она расположена.

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

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

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

Единственное число — номер соответствующей четверти, либо [latex]0[/latex], если однозначно определить четверть невозможно.»

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

Тесты

[latex]x[/latex] [latex]y[/latex] четверть [latex]x[/latex] [latex]y[/latex] четверть
2 -2 4 0 54 0
5 7 1 -3 4 2
-3 0 0 -3 -8 3
0 0 0

Поскольку в любом случае мы обращаемся к оператору вывода, имеет смысл вложить условия в этот оператор.  Сначала мы проверяем, не равна ли хотя бы одна переменная нулю. Если да — выводим [latex] 0[/latex], если нет — проверяем, больше ли [latex]x[/latex] нуля. Если да — это будет первая или четвертая четверть, если нет — вторая или третья. Внутри проверки [latex]x[/latex] проверяем [latex]y[/latex]. Если y больше нуля — это первая или вторая четверть, если меньше — вторая или третья.