e-olymp 2171. Поиск набора образцов

Задача. Напишите программу, которая для каждой строки из заданного набора [latex]S[/latex] проверяет, верно ли, что она содержит как подстроку одну из строк из набора [latex]T[/latex].

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

Первая строка содержит натуральное число [latex]n (n\leq100)[/latex] — количество строк в наборе [latex]T[/latex]. Каждая из следующих [latex]n[/latex] строк содержит непустую строку длины не более [latex]80[/latex]-ти символов.

Оставшаяся часть файла содержит строки из набора [latex]S[/latex]. Каждая строка состоит из ASCII символов с кодами от [latex]32[/latex] до [latex]126[/latex] включительно. Строка может быть пустой; гарантируется, что длины строк не превышают [latex]250[/latex]-ти символов.

Гарантируется, что размер входного файла не превышает [latex]1[/latex] Мбайт.

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

Выведите все строки из набора [latex]S[/latex] (в том порядке, в котором они находятся во входном файле), содержащие как подстроку по крайней мере одну строку из набора [latex]T[/latex].

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

Тесты

Test Input Output
1 3
gr
sud
abc
lksh
sudislavl
kostroma
summer
group b
sudislavl
group b
2 4
a
b
+ +
xxx
ababa
dfs
c + +
qwerty
xxxx
ababa
c + +
xxxx
3 1
a
a
b
a
c
a
d
a
a
a
4 2
bab
aba
aabba
w w w

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

Алгоритм

Мы последовательно перебираем все строки [latex]s[/latex] из набора [latex]S[/latex]. Для каждой из них найдем вхождение хотя бы одной строки [latex]t[/latex] из набора [latex]T[/latex]. Для этого мы воспользуемся алгоритмом Рабина-Карпа. Он заключается в следующем: мы сравниваем подстроки [latex]s[/latex] длины [latex]\left | t \right |[/latex]  со строкой [latex]t[/latex], предварительно закодировав их с помощью хеша. Если после мы перебрали все подстроки, но так и не получили равенство,  строка [latex]t[/latex] не является подстрокой  [latex]s[/latex] и мы переходим к следующему образцу.

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

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

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

e-olymp 982. Связность

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

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

В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex]  каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].

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

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Тесты, взятые с e-olymp.com

Test Input Output
1 3 2
1 2
3 2
YES
2 3 1
1 3
NO

Мои тесты

Test Input Output
1 4 2
1 2
3 4
NO
2 4 5
1 2
2 1
2 4
2 4
4 2
NO
3 5 4
1 2
5 1
3 5
4 3
YES

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

Алгоритм

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

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

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

A295

Задача. Даны целые числа [latex]a_{1},\ldots, a_{n}[/latex]. Наименьший член последовательности [latex]a_{1}, \ldots, a_{n}[/latex] заменить целой частью среднего арифметического всех членов, остальные члены оставить без изменения. Если в последовательности несколько членов со значением min [latex](a_{1}, \ldots, a_{n})[/latex], то заменить последний по порядку.

Тесты

Test Input Output
1 2 4 8 16 2 4 2 4 8 16 6 4
2 1 1 1 1 1 1 1 1
3 -5 5 -10 10 -10 5 5 -5 5 -10 10 0 5 5
4 2 6 9 -4 -5 7 13 2 6 9 -4 4 7 13
5 0 0 0 0 0 1 0 0 0 0 0 1
6 0 1 0 0 2 0 25 0 1 0 0 2 4 25

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

 

Алгоритм

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

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

e-olymp 1077. Java против C++

Задача. Сторонники языков Java и C++ часто спорят о том, какой язык лучше для решения олимпиадных задач. Одни говорят, что в Java есть масса полезных библиотек для работы со строками, хорошо реализованы механизмы чтения и вывода данных, а так же радует встроенные возможности для реализации длинной арифметики. С другой стороны, С++ является классическим языком, скорость выполнения программ благодаря существующим компиляторам (например, Intel Compiler 10.0) гораздо выше, чем у Java.

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

В языке Java принято первое слово, входящее в название переменной записывать с маленькой латинской буквы, следующее слово идет с большой буквы (только первая буква слова большая), слова не имеют разделителей и состоят только из латинских букв. Например, правильные записи переменных в Java могут выглядеть следующим образом: javaIdentifier, longAndMnemonicIdentifier, name,nEERC.

В языке C++ для описания переменных используются только маленькие латинские символы и символ «_», который отделяет непустые слова друг от друга. Примеры: java_identifier, long_and_mnemonic_identifier, name, n_e_e_r_c.

Вам требуется написать программу, которая преобразует переменную, записанную на одном языке в формат другого языка.

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

Во входном файле задано наименование переменной длиной не более [latex]100[/latex] символов.

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

В выходной файл требуется вывести аналог имени переменной в другом языке. Т.е. если переменная представлена в формате Java, то следует перевести в формат C++ и наоборот. В том случае, когда имя переменной не соответствует ни одному из вышеописанных языков, следует вывести «Error!«.

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

Тесты

Test Input Output
1 java_word javaWord
2 cppWorD cpp_wor_d
3 simpleword simpleword
4 two__underscores Error!
5 _underscore_in_the_beginning Error!
6 underscore_in_the_end_ Error!
7 UppercaseInTheBeginning Error!
8 mixed_Style Error!

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

 

Алгоритм

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

Для удобства я изобразила этот алгоритм в виде схемы:

MMMMEWWWWWW

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

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

Когда мы считываем очередной символ, мы переходим в другое состояние либо остаемся в предыдущем. В состояние Error(отмечено красным) мы переходим, если считаем какую-любо последовательность символов, не подходящую ни под один из стандартов.

Отдельно следует поговорить о состоянии CPP delimeter. Оно используется для контроля количества подчеркиваний. Если в нашей предполагаемой С++ переменной встречается подчеркивание, ей сразу же присваивается данное состояние, чтобы, при наличии второго подчеркивания сразу же перевести ее в состояние Error in CPP.

Финальные состояния отмечены зеленым цветом. В них мы переходим только после окончания строки непосредственно из предыдущего состояния.  Переход в состояние Universal означает, что исходная строка состоит исключительно из маленьких букв и подходит как для языка Java, так и для C++.

Определив стандарт, к которому принадлежит переменная, мы вызываем блок перевода. Результат всегда записываем в отдельную переменную. В случае Java мы снова последовательно перебираем все символы строки и заменяем каждую встретившуюся большую букву на подчеркивание и эту же букву в маленьком регистре. Размер строки в этом случае увеличивается на количество больших букв в ее исходном варианте.  В случае же С++ мы удаляем каждое подчеркивание, сдвигая все последующие символы, а первый из них переводим в большой регистр. Очевидно, что размер строки в этом случае будет уменьшен на количество подчеркиваний.

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

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

Mloops 21

Задача.Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n>0[/latex] (количество столбцов) и [latex]m>0[/latex] (количество строк).
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

1+12+33+64+105+156+217+288
12+33+64+105+156+217+288+1
33+64+105+156+217+288+1+12
64+105+156+217+288+1+12+33
105+156+217+288+1+12+33+64
156+217+288+1+12+33+64+105
217+288+1+12+33+64+105+156

Тесты

[latex]m[/latex] [latex]n[/latex] Результат
1 5 13 1+12+33+64+10
12+33+64+105+
33+64+105+1+1
64+105+1+12+3
105+1+12+33+6
2 8 11 1+12+33+64+
12+33+64+1+
33+64+1+12+
64+1+12+33+
1+12+33+64+
12+33+64+1+
33+64+1+12+
64+1+12+33+
3 11 20 1+12+33+64+105+156+2
12+33+64+105+156+217
33+64+105+156+217+1+
64+105+156+217+1+12+
105+156+217+1+12+33+
156+217+1+12+33+64+1
217+1+12+33+64+105+1
1+12+33+64+105+156+2
12+33+64+105+156+217
33+64+105+156+217+1+
64+105+156+217+1+12+

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

 

Алгоритм

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

[latex]n^2+4\cdot(n^2-n)[/latex]

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

В каждой следующей строке мы сдвигаем последовательность на одно число влево.

Чтобы число столбцов [latex]n[/latex] соответствовало числу символов в каждой строке, мы выводим числа по одному, каждый раз проверяя, не превысила ли общая длина строки заданное число [latex]n[/latex]. Если длина все-таки получается больше, мы выводим то количество символов, которое помещается в данную строку, а остальные отбрасываем.

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

MLoop 2

Задача. Используйте метод хорд для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] все действительные корни уравнения  [latex]\frac{x}{2 \cdot \sin x +1}=\tan(\ln(x^2+1))[/latex].  Для подготовки необходимых графиков воспользуйтесь этим ресурсом.

Тесты(найдено с помощью математической системы WolframAlpha):

[latex]A[/latex] [latex]B[/latex] [latex]x\approx[/latex]
-20 20  -11.6945378230838209122818536587051434153…


-1.25741503276862309237205903178504130394…

0


0.547316310185252929580383582338832450320…

10.9948442206261587135425985750810372810…

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

 

Алгоритм

Для начала запишем данное нам уравнение в виде функции [latex]y=f(x)[/latex] и построим ее график:

[latex]y=\frac{x}{2 \cdot sin x +1}-tan(ln(x^2+1))[/latex]

 

save (4)

Задача о нахождении приближённых значений действительных корней уравнения [latex]f(x)=0[/latex] предусматривает предварительное отделение корня, то есть установление интервала, в котором других корней данного уравнения нет.

Метод хорд предусматривает замену функции на интервале на секущую, и поиск ее пересечения с осью [latex]OX[/latex]. На заданном интервале [latex][a,b][/latex] с точностью [latex]\varepsilon[/latex] корень будет вычисляться согласно итерационному выражению, которое имеет вид:

[latex]x_{i+1}=x_{i-1}-\frac{f(x_{i-1}) \cdot (x_{i}-x_{i-1})}{f(x_{i})-f(x_{i-1}) ) }[/latex]

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

  1. В точке, где находится предполагаемый корень, имеется разрыв второго рода. Здесь метод хорд обнаруживает перемену знака и начинает сужать отрезок. Однако расстояние между крайними точками  отрезка не уменьшается, а увеличивается. А именно увеличивается проекция отрезка на ось [latex]OY[/latex]. И чем ближе мы находимся к точке разрыва, тем она больше, а в самой точке стремится к бесконечности. В качестве примера приведем функцию [latex]\frac{(x-5)^2}{x-4}[/latex], имеющую разрыв второго рода в точке [latex]x=4[/latex].
    save

  2. Аналогичный случай — точка разрыва первого рода, где наша хорда стремится к некоторой константе — величине разрыва. Пример — функция [latex]\frac{\sin x\cdot(x-2.5)}{\left | x-2,5 \right |}[/latex], имеющая разрыв первого рода в точке [latex]x=2,5[/latex].
    save (1)

  3. Функция не является разрывной и даже имеет корень, однако в точке корня производная стремится к бесконечности. Например, функция [latex]\sqrt[3]{x-1,2}[/latex], имеющая корень в точке [latex]x=1,2[/latex]. Для функций подобного рода длина проекции отрезка на ось [latex]OY[/latex] будет очень медленно меняться, вследствие чего для разумного числа итераций она будет превосходить заранее выбранную точность [latex]\varepsilon[/latex].

save (2)

  1. Функция равна нулю или очень близка к нулю на некотором интервале(например, функция [latex]y=rect(x-1,5)\cdot(x-1)\cdot(x-2)^2[/latex]). Здесь метод хорд найдет пересечение с осью [latex]OX[/latex]  в интервале, где находятся корни(одна из сторон отрезка будет корнем), но все последующие итерации будут выдавать эту же точку. Поэтому хорда не будет уменьшаться, и даже этот один корень не будет найден(если будет использоваться стандартная [latex]\delta[/latex]-оценка точности по оси [latex]OX[/latex]).

save (3)

  1. Функция вида [latex]y=x^{2k}[/latex] или ей подобная, например, [latex]y=1+\sin x[/latex], к которой метод хорд вообще не применим, так как нарушается начальное условие применимости этого метода. Здесь нужно ввести дополнительную проверку. Изменим значение функции на небольшую константу — нашу точность [latex]\varepsilon[/latex] и повторим процедуру поиска корней. В результате мы получим [latex]2k[/latex] корней, каждую пару из которых мы можем считать краями интервала, в котором лежит настоящий корень.

save (6)

К счастью, в данной нам функции присутствует только один из этих случаев, а именно разрыв второго рода. Аналитически рассмотрев нашу функцию, мы обнаружили, что корни следует искать в окрестности точек[latex]\sqrt{e^{\frac{\pi}{2}+\pi \cdot k}-1}[/latex] с отклонением [latex]\pm\pi[/latex]. В корнях функции ее производная быстро растет с ростом [latex]k[/latex].

Критерием отбрасывания кандидата на корень будет рост длины хорды при сужении интервала. Критерием останова будет сужение интервала до заданной точности [latex]\delta[/latex].
Код программы

Mif 15

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

Тесты

(1)

[latex]A_0[/latex] [latex]A_1 [/latex] [latex]A_2[/latex] [latex]A_3[/latex] [latex]B_0[/latex] [latex]B_1[/latex] [latex]B_2[/latex] [latex]B_3[/latex]
1  1 0 0 0 2 0 0 0
2  1 0 0 0 3 0 0 0
3  -1 1 0 6 -2 -1 1 6
4  1 1 1 1 2 2 2 2
5  1 1 1 2 8 5 7 10
6  1 1 0 0 1 0 1 1
7  3 4 7 8 9 5 6 2
8  1 2 2 3 1 4 8 9

(2)

[latex]C_0[/latex] [latex]C_1[/latex] [latex]C_2[/latex] [latex]C_3[/latex] [latex]D_0[/latex] [latex]D_1[/latex] [latex]D_2[/latex] [latex]D_3[/latex] [latex]r[/latex]
1  1 1 0 0 2 1 0 0 1.000000
2  2  4  0  0 2 4 3 0 4.000000
3  -1 -1  0 6 2 1 1 6 1.154701
4  -9 -9 -9 -9 -5 -5 -5 -5 12.000000
5  8 0  0 0 2 1 1 1 1.414214
6  2  3 2 0 1 4 9 1 3.000000
7  7 4 11 15 15 5 12 9 9.000000
8  5 7 2 23 4 8 8 21 13.000000

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

Алгоритм и его обоснование

Расстояние между отрезками в четырехмерном пространстве находится по-разному, в зависимости от взаимного расположения этих отрезков. Тут мы можем выделить два основных случая:

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

Чтобы выяснить, с каким случаем мы имеем дело, рассмотрим общую картину взаимного расположения отрезков и опишем ее математически:
PICTURE1
По условию нам заданы 4 точки: [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] — концы двух отрезков. Для удобства представления уравнений и точек, связанных с ними, обозначим их [latex]P_0[/latex], [latex]P_1[/latex], [latex]Q_0[/latex] и [latex]Q_1[/latex] соответственно. Через эти пары точек мы можем провести 2 прямые [latex]p[/latex] и [latex]q[/latex], параметрические уравнения которых имеют вид:

[latex]

\begin{matrix}
\vec p = P_0 + \vec u \cdot s \\
\vec q = Q_0 + \vec v \cdot t
\end{matrix}

[/latex],

где векторы:

[latex]

\begin{matrix}

\vec u = P_1 — P_0\\

\vec v = Q_1 — Q_0

\end{matrix}

[/latex],

а   [latex]s[/latex]   и   [latex]t[/latex]   — параметры. При [latex]s=0[/latex]   или   [latex] t=0[/latex]   мы получаем начальную точку соответствующего отрезка, а при [latex]s=1[/latex]   или [latex]t=1[/latex]   — конечную. При произвольном значении параметра мы получаем произвольную точку на прямой.

Рассмотрим вектор [latex]\vec w = Q — P[/latex] , соединяющий 2 произвольные точки на этих прямых. Легко показать, что вектор [latex]\vec w[/latex]   соединяет 2 ближайшие точки  [latex]Q_c[/latex]   и   [latex]P_c[/latex]   при условии:

[latex]\vec w \perp p[/latex] и [latex]\vec w \perp q[/latex].

Этому условию соответствует система из двух уравнений:

[latex]
\begin{cases}
\vec u \cdot \vec w = 0\\
\vec v \cdot \vec w = 0
\end{cases}

[/latex]

Распишем ее для   [latex]\vec w = Q_0 — P_0 + \vec v \cdot t — \vec u \cdot s = \vec w_0 + \vec v \cdot t — \vec u \cdot s[/latex] :
[latex]

\begin{cases}
\vec u \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0\\
\vec v \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0
\end{cases}

[/latex]

Введем вспомогательные скалярные переменные:
[latex]

\begin{matrix}

a&=&\vec u \cdot \vec u\\
b&=&\vec u \cdot \vec v\\
c&=&\vec v \cdot \vec v\\
d&=&\vec u \cdot \vec w_0\\
e&=&\vec v \cdot \vec w_0

\end{matrix}

[/latex]

Теперь наша система будет выглядеть так:

[latex]

\begin{cases}
d — a \cdot s + b \cdot t = 0 \\
e — b \cdot s + c \cdot t = 0
\end{cases}
[/latex]

Перепишем систему в удобном для нас виде:

[latex]
\begin{cases}
a \cdot s — b \cdot t = d \\
b \cdot s — c \cdot t = e
\end{cases}
[/latex]

Решение этой системы мы можем получить, например, методом Крамера.

Главный определитель системы:   [latex]D = b^2 — a \cdot c[/latex]

Два вспомогательных определителя:
[latex]
\begin{matrix}
D_1 = b \cdot e — c \cdot d\\
D_2 = a \cdot e — b \cdot d\\
\end{matrix}
[/latex]
Если [latex]D \neq 0[/latex],   то существует единственное решение:

[latex]

\begin{cases}
s_c = \frac{D_1}{D} \\
t_c = \frac{D_2}{D}
\end{cases}
[/latex]

Если же мы получаем   [latex]D = 0[/latex],   легко показать, что отрезки параллельны. То есть мы имеем дело со случаем 1.

Тогда:

а) Если хотя бы одна точка одного отрезка проецируется на другой отрезок, то расстояние между отрезками равняется расстоянию между прямыми.

Найдем проекцию точки   [latex]P_0[/latex]   на линию   [latex]q[/latex]. Для этого сначала найдем вектор, который является проекцией вектора   [latex]\vec w_0[/latex]   на линию   [latex]q[/latex].

[latex]\vec w_q=(\vec w_0 \cdot \vec v) \cdot \frac{\vec v}{v^2}[/latex].
Конец полученного вектора находится в точке   [latex]Q_0[/latex],   а начало в новой точке   [latex]P_{0q}=Q_0-\vec w_q[/latex]. Соединим точки   [latex]P_0[/latex]   и   [latex]P_{0q}[/latex] вектором [latex]\vec w_p = P_{0q} — P_0[/latex]. Длина полученного вектора и будет искомым расстоянием:   [latex]r = \left| P_0 P_{0q} \right|[/latex].

RESULT

Для проверки условия а) необходимо получить проекции остальных исходных точек на отрезки:
[latex]
\begin{matrix}
P_{1q} = P_{0q} + \vec u\\
Q_{0p} = P_0 + \vec w_q\\
Q_{1p} = Q_{0p} + \vec v
\end{matrix}
[/latex]

Если точка   [latex]P_{0q}[/latex]   лежит на прямой   [latex]q[/latex],    задаваемой уравнением:
[latex]\vec q = Q_0 + \vec v \cdot t[/latex],
то определить, принадлежит ли точка [latex]P_{0q}[/latex]   отрезку [latex]Q_0 Q_1[/latex]   можно, решив уравнение:
[latex]P_{0q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q + \vec v \cdot t[/latex].
Домножив обе части скалярно на вектор   [latex]\vec v[/latex],   мы получим уравнение: [latex] 0 = e + c \cdot t[/latex], отсюда   [latex]t = \frac{-e}{c}[/latex].

Если [latex]t \in \left[0,1\right][/latex], то точка [latex]P_{0q}[/latex] лежит на отрезке [latex]Q_0 Q_1[/latex]. Если же нет, переходим к аналогичной проверке следующих точек:

[latex]P_{1q}:[/latex]
[latex]P_{1q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q — \vec u + \vec v \cdot t[/latex].
Опять домножив обе части скалярно на вектор   [latex]\vec v[/latex],   мы получим уравнение:

[latex] 0 = e — b + c \cdot t[/latex],
отсюда   [latex]t = \frac{-e+b}{c}[/latex].
[latex]Q_{0p}:[/latex]
[latex]Q_{0p} = P_0 + \vec u \cdot s[/latex].
[latex]0 =-\vec w_q + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор   [latex]\vec u[/latex],   мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} + a \cdot s[/latex],
отсюда   [latex]s = \frac{e \cdot b}{c \cdot a}[/latex].
[latex]Q_{1p}:[/latex]
[latex]Q_{1p} = P_0 + \vec u \cdot s[/latex].
[latex] 0 = -\vec w_q — \vec v + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор   [latex]\vec u[/latex],   мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} — b + a \cdot s[/latex],
отсюда   [latex]s = \frac{(e — c) \cdot b}{c \cdot a}[/latex].
б) В противном случае, расстояние между отрезками равняется минимальному расстоянию между их концами. Здесь задача предельно упрощается. Мы находим длины отрезков, попарно соединяющих 4 исходные точки, и выбираем наименьший из них.

Если же исходные отрезки лежат на пересекающихся либо на скрещивающихся прямых, мы также рассматриваем 2 случая:

а) Оба конца кратчайшего отрезка, соединяющего прямые, лежат на соответствующих исходных отрезках:
[latex]P_c \in P_0 P_1[/latex]   и   [latex]Q_c \in Q_0 Q_1[/latex].

В этом случае пара параметров   [latex](s_c, \; t_c)[/latex]   принадлежит области:   [latex](s,t):\left[0,1\right]\times \left[0,1\right].[/latex]

То есть, решение тривиально: ответом будет дина вектора   [latex]\vec w_c[/latex]

б) Хотя бы один из концов кратчайшего отрезка, соединяющего прямые, не лежит на исходном отрезке, то есть:
[latex]P_c \not\in P_0 P_1[/latex] или [latex]Q_c \not\in Q_0 Q_1[/latex],
что соответствует значениям параметров   [latex]s_c \not\in \left[0,1\right][/latex]   или   [latex]t_c \not\in \left[0,1\right][/latex].

В этом случае минимальное расстояние между отрезками определяется на границе области:   [latex](s,t):\left[0,1\right]\times \left[0,1\right][/latex]   (см. рисунок ниже):

elipsoid

Здесь решением является длина кратчайшего отрезка.

Длину отрезка, соединяющего 2 прямые, можно оценивать по квадрату длины вектора   [latex]\vec v[/latex]: [latex]w^2=(\vec w)^2=(\vec w_0 — \vec u \cdot s + \vec v \cdot t)^2[/latex].

В частности, минимум   [latex]w^2[/latex] достигается в точке   [latex](s_c,t_c)[/latex].
Однако в случае б) мы должны найти минимум расстояния на границе нашей области, то есть решить задачу нахождения минимума при ограничениях (решить задачу условной минимизации). В нашем случае ограничения имеют очень простой вид — оси координат, и две линии, параллельные им. Поэтому мы можем решить на четырех границах 4 упрощенные задачи минимизации, а затем выбрать наименьшее решение.

Замечание: В пространстве параметров функция [latex]w^2(s,t)[/latex] представляет из себя эллиптический параболоид. Однако для простоты мы выше изобразили его линии уровня в виде окружностей. Типичный вид эллиптического параболоида и его линий уровня представлен на рисунках ниже:
3dellipticparabolloid
2dmap_ellipticparabolloid

Рассмотрим поочередно все 4 ограничения и решим задачу для них:

(1) Пусть [latex]t=t_1=0[/latex].

Тогда: [latex]{w^2\mid_{t_1=0}} = (\vec w_0-\vec u \cdot s_1)^2[/latex].

Для определения экстремума приравняем производную к нулю:[latex]
\begin{array}{r}
\frac{d}{ds_1}{(\vec w_0-\vec u \cdot s_1)^2}=0\\
2 \cdot (\vec w_0-\vec u \cdot s_1) \cdot (- \vec u)=0\\
-d +a \cdot s_1=0\\
s_1=\frac{d}{a}
\end{array}
[/latex]

Легко показать, что при [latex]s_1>1[/latex] мы должны присвоить ему значение [latex]s_1=1[/latex], а если [latex]s<0[/latex] — значение [latex]s_1=0[/latex], так как мы не должны выходить за границы исходных отрезков.

Подставим полученное значение [latex]s[/latex] в уравнение прямой [latex]p[/latex] для точки [latex]P_c[/latex]:[latex]P_c = P_0 + \vec u \cdot s.[/latex]

А точка [latex]Q_c[/latex] совпадает с точкой [latex]Q_0[/latex]. Тогда первый минимум равен: [latex]r_1 = Q_0 P_c[/latex].

Аналогично найдем три остальных минимума [latex]r_2, r_3, r_4[/latex], приравняв [latex]s[/latex] к нулю, а затем [latex]t[/latex] и [latex]s[/latex] к единице. Наименьший из них и есть искомое расстояние [latex]r[/latex].

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

Mif 17.9

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

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

Тесты

[latex]x[/latex] 0 3 0 6 6 -1000
[latex]y[/latex] 0 2 6 0 6 48000
Результат  NO  YES  YES  YES NO  NO

Алгоритм

По рисунку видно, что заданная фигура ограничена осями координат и двумя прямыми: [latex] y = 6 — x [/latex] сверху и [latex] y = 4 — 2 \cdot x [/latex] снизу.  То есть, решением является пересечение решений неравенств:
[latex]x \geq 0, y \geq 0, y \leq 6 — x, y \geq 4 — 2 \cdot x[/latex]

Если координаты точки удовлетворяют всем этим условиям, программа выводит «YES», в противном случае — «NO».

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

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

e-olymp 128. Счастливые билеты

Задача.  Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N(N \leq 27)[/latex].

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

Тесты

Число [latex]N[/latex] 3 27 26 1 10
Количество билетов 100 1 9 9 3969

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

Алгоритм

Любой шестизначный номер мы можем представить как 2 трехзначных номера.

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

Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c \cdot c[/latex].

Решение

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

e-olymp 138. Банкомат

Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 1000001)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.

Тесты

Сумма 130 999 7360 3 80 123450 567 440
Число купюр 3 -1 18 -1 3 249 -1 4

 

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

Алгоритм

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

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

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

 

Решение

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

ML15

Задача. Определить силу притяжения [latex]F[/latex] между телами массы [latex]m_1[/latex] и [latex]m_2[/latex], находящимися на расстоянии [latex]r[/latex] друг от друга.

Тесты

Масса первого тела(кг) Масса второго тела(кг) Расстояние(м) Сила притяжения
2e15 1.5e10 1e3 2.00215e+09 Н
3e20 2.5 1e5 4.00430e+05 Н
7e-1 9 2 1.05113e-10 Н
3e20 0 1e5 0.00000e+00 Н
20 50 9e5 8.23931e-20 Н

Алгоритм

Задача состоит в том, чтобы успешно применить формулу закона всемирного тяготения. Мы должны вычислить силу притяжения между двумя телами, если известны их массы, а также расстояние между ними. Это легко найти без дополнительных преобразований по следующей формуле:

[latex]F=G\cdot \frac{m1\cdot m2}{r^2}[/latex],

где [latex]m_1[/latex], [latex]m_2[/latex] — массы тел,  [latex]r[/latex] — расстояние, а [latex]G[/latex] — гравитационная постоянная, значение которой задается в виде константы. Остальные значения вводятся с клавиатуры,  в системе СИ.

Результат программы выводится в стандартном виде. Точность мантиссы по умолчанию равна пяти знакам после запятой.

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

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

e-olymp 1. Простая задача

Задача. Программа считывает двузначное число и выводит через пробел каждую цифру отдельно.

Тесты

Ввод 10 12 45 99
Вывод 1  0 1 2 4 5 9 9

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

Алгоритм

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

Решение

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