e-olymp 7368. Средний балл для фигуристов

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

Задача

Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей[latex]\left( 0 \lt n \leqslant 10, 0 \lt m \leqslant 100 \right)[/latex] для каждого из фигуристов.

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

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 4
7 8 9 8 10
6 5 5 4 7
9 9 10 7 7
7 7 10 9 8
8.33 5.33 9.00 8.50
2 3 4
1 2 3
3 5 2
7 1 6
9 8 3
2.00 3.00 6.00 8.00
3 10 2
1 2 3 4 5 6 7 8 9 10
1 1 1 2 2 2 3 3 3 4
5.50 2.50

Код программы (Потоковая обработка)

Решение

Читая каждую оценку:

  1. Добавляем оценку к общей сумме;
  2. Если введенная оценка равна минимальной, то добавляем ее к сумме минимальных и увеличиваем счётчик количества минимальных.
  3. Если введенная оценка меньше минимальной, то минимальной становится введённая оценка. Счетчик количества минимальных равен [latex]1.[/latex] Сумма минимальных равна введённой оценке.
  4. Если введенная оценка равна максимальной, то добавляем ее к сумме максимальных и увеличиваем счётчик количества максимальных.
  5. Если введенная оценка больше максимальной, то максимальной становится введённая оценка. Счетчик количества максимальных равен [latex]1.[/latex] Сумма максимальных равна введённой оценке.

Тогда после введения всех [latex]n[/latex] оценок имеем:

  •  [latex]sumMax[/latex] — сумма максимальных оценок.
  •  [latex]sumMin[/latex] — сумма минимальных оценок.
  •  [latex]countMax[/latex] — количество максимальных оценок.
  •  [latex]countMin[/latex] — количество минимальных оценок.
  •  [latex]sumGl[/latex] — общая сумма оценок.

Для нахождения среднего арифметического значения оценок, соответствующего условию будем применять формулу:  [latex]S_с = \frac{sumGL-sumMin-sumMax}{n-countMin-countMax}[/latex]

Код программы (Массивы)

Решение

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

Ссылки

Условие задачи на e-olymp

Код программы на ideone (Потоковая обработка)

Код программы на ideone (Массивы)

e-olymp 5282. Седловые точки

Задача. Седловые точки

Задана матрица $K$, содержащая $n$ строк и $m$ столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.

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

Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.

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

Выведите количество седловых точек.

Тесты

Ввод Вывод
1 2 2
0 0
0 0
4
2 2 2
1 2
3 4
1
3 5 5
100 -100 100 1000 110
10 -1000 100 -1000 110
100 -1000 100 100 110
1000 -1000 1000 1000 100
1000 -1000 1000 1000 -1000
1
4 4 4
1000 1000 100 100
1000 1000 1000 1000
100 100 100 1000
100 1000 1000 1000
4
5 2 3
1 -1 1
0 -1 0
2
6 5 1
-1
0
-1
0
-1
2
7 4 2
1 2
-2 1
-1 2
-2 -1
1
8 3 3
5 1 3
3 1 2
1 1 2
3
7 3 3
5 2 3
3 4 2
1 8 2
0

Решение

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

Вариант решения за $O\left(n^2\right)$

Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.

Вариант решения за $O\left(n\log n\right)$

В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.

e-olymp 8529. Преобразование Капрекара

Задача

Индийский математик Д. Р. Капрекар известен своими работами по теории чисел. Одна из его работ посвящена так называемому преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число $x$. Пусть $M$ — наибольшее число, которое можно получить из $x$ перестановкой его цифр, а $m$ — наименьшее число (это число может содержать ведущие нули). Обозначим как $K(x)$ разность $M$ — $m$, дополненную при необходимости ведущими нулями так, чтобы число цифр в ней было равно числу цифр в $x$.

Например $K(100) = 100 — 001 = 099$, $K(2414) = 4421 — 1244 = 3177$.

Капрекар доказал, что если начать с некоторого четырехзначного числа $x$, в котором не все цифры равны между собой, и последовательно применять к нему эту операцию (вычислять $K(x)$, $K(K(x))$, . . . ), то рано или поздно получится число $6174$. Для него верно равенство $K(6174) = 7641 — 1467 = 6174$, поэтому на нем процесс зациклится.

Ваша задача состоит в том, чтобы написать программу, вычисляющую $K(x)$ по числу $x.$

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

Одно целое число без ведущих нулей $x$ ($1$ ≤ $x$ ≤ $10^9$).

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

Выведите $K(x)$.

Тесты

Входные данные Выходные данные
100 099
1000000000 0999999999
2414 3177
6174 6174
5 0
7272 5445
142857 750843
495 495
55 00
56 09
554 099
12345 41976

 

Решение

Объяснение

Поскольку нужно находить минимальную и максимальную комбинацию из цифр числа, удобно в самом начале записать это число в виде массива и отсортировать. Далее найти, собственно, искомые числа, и получить из них само $K(x)$. Потом остаётся проверить количество цифр и вывести, при недостатке, соответствующее количество нулей.

Код на ideone
Зачтено на e-olymp

e-olymp 3867. Ленивый Мишка

Задача. Ленивый Мишка

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

  • На мытье посуды уйдет [latex]t_1[/latex] секунд
  • Пропылесосить квартиру можно за [latex]t_2[/latex] секунд
  • Процесс игры с Маринкой займет [latex]t_3[/latex] секунд

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

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

Три целых числа [latex]t_1[/latex], [latex]t_2[/latex], [latex]t_3[/latex] ([latex]1 ≤ t_1, t_2, t_3 ≤ 1000[/latex]).

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

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

Тесты

Ввод Вывод
1 1 7 2 1
2 100 45 1 1
3 66 9 888 9
4 5 800 4 4
5 25 46 25 25
6 13 10 12 10
7 999 995 1000 995

Решение 1

Мишка выбирает мамино поручение, что занимает наименьшее количество времени. Нам дано время за которое Мишка выполнит данные поручения. Найдём из них наименьшее и выведем на экран. Воспользуемся функцией int min (int, int); из библиотеки cmath.

Код 1

Решение 2

Для нахождения минимума трёх чисел заведём переменную min и воспользуемся логическим ветвлением.

Код 2

Ссылки

Первое решение

Второе решение

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

Компиляция первого решения

Компиляция второго решения

e-olymp 7368. Средний балл для фигуристов

Задача

Спортсменам — фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n ≤ 10, 0 < m ≤ 100)[/latex] для каждого из фигуристов.

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

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

Тесты

# Входные данные Выходные данные
1 5 4
7 8 9 8 10
6 5 5 4 7
9 9 10 7 7
7 7 10 9 8
8.33 5.33 9.00 8.50
2 6 3
6 7 6 5 4 3
9 8 5 5 6 5
7 6 4 1 2 2
5.25 7.00 3.50
3 4 5
6 7 8 6
9 8 5 4
7 6 7 5
4 3 9 3
7 8 7 6
7.00 6.50 6.00 4.00 7.00
4 4 4
7 7 2 3
9 8 3 3
5 4 9 7
4 3 2 6
3.00 8.00 6.00 3.50
5 8 5
4 5 6 7 7 4 9 8
3 5 6 6 7 8 5 9
7 6 3 9 3 7 9 7
5 6 4 3 7 7 5 7
9 8 4 6 7 9 9 4
6.60 6.17 6.75 5.00 7.00

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

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

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные [latex]a[/latex] и [latex]b[/latex] — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной [latex]x[/latex], и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле [latex]n-a-b[/latex]. А затем вычисляем среднее арифметическое для оставшихся значений по формуле [latex]\frac{sum}{n-a-b}[/latex] и выводим результат.

Ссылка на e-olymp

Ссылка на ideone

e-olymp 7457. Max-Min в двійковій системі счислення

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом [latex]N[/latex] знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

[latex]N = 13_{10}[/latex], в двійковій системі числення — [latex]1101_2[/latex], найбільше число [latex]1110_2[/latex] = [latex]14_{10}[/latex], найменше число [latex]0111_2[/latex] = [latex]7_{10}[/latex]. [latex]14-7=7[/latex].

Вхідні дані

В єдиному рядку записане число N ([latex]N<2^{31}[/latex]).

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані Вихідні дані
$2$ $1$
$15$ $0$
$86$ $105$
$1000$ $945$
$40$ $45$

Код програми

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

  1. За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа [latex]n[/latex].
  2. Створимо функцію [latex]max\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
  3. Створимо функцію [latex]min\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
  4. Виведемо на екран різницю підрахованих функціями [latex]max\_number[/latex] та [latex]min\_number[/latex] значень.

Посилання

Код програми на ideone
Умова на сайті E-Olymp

e-olymp 695. Range Variation Query

Условие

Задача взята отсюда.

Последовательность [latex]a_n[/latex] задается следующей формулой: [latex]a_n = n^2 \mod 12345 + n^3 \mod 23456[/latex].

Требуется много раз отвечать на запросы следующего вида:

  • найти разность между максимальным и минимальным значением среди элементов [latex]a_i, a_{i+1}, \ldots, a_j[/latex];
  • присвоить элементу [latex]a_i[/latex] значение [latex]j[/latex].

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

Первая строка содержит натуральное число [latex]k[/latex] [latex](k \leq 10^5)[/latex] — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_i[/latex], [latex]y_i[/latex].

Если [latex]x_i > 0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{xi}, a_{xi+1}, \ldots, a_{yi}[/latex]. При этом [latex]1 \leq x_i \leq y_i \leq 10^5[/latex].

Если [latex]x_i < 0[/latex], то требуется присвоить элементу [latex]a_{-xi}[/latex] значение [latex]y_i[/latex]. При этом [latex]-10^5 \leq x_i \leq 1[/latex] и [latex]|y_i| \leq 10^5[/latex].

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

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

Тесты

Входные данные Выходные данные
1 7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3
34
68
250
234
1
2  4
1 100000
100000 100000
-100000 42000
1 100000
35753
0
41998
3 13
1 17
-5 -400
-3 500
3 5
1 17
-2 345
2 345
2 3
2 5
-1 -100000
-2 100000
1 2
1 100000
5200
900
5602
35813
155
900
200000
200000

Код

Решение

Задача решается с помощью стандартного Дерева Отрезков (подробно про ДО прочитать можно, например, на сайте Е-maxx, ссылка ниже). Отметим особенности построения данного дерева. В вершинах дерева хранить будем не по одному, а по два значения — соответственно максимум и минимум на отрезке. Тогда при построении дерева, спускаясь до листа, будем считать элемент последовательности по формуле, данной в условии, и это значение будет как минимумом, так и максимум для отрезка из одного элемента. Для остальных элементов имеем:

Где элементы с номерами [latex]pos * 2[/latex] и [latex]pos * 2 + 1[/latex] — левый и правый потомок соответственно. Для удобства, дерево нумеруется с единицы.

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

Функция обновления рекурсивно спускается от корня до соответствующего элемента, меняя его значение, а потом обновляет значения всех вершин, для которого этот элемент является подотрезком, в направлении от элемента до корня (формула пересчета та же, что использовалась при построении дерева).

Таким образом, в самой программе мы просто строим дерево, а потом в цикле отвечаем на запросы, выполняя необходимые действия (как описано в условии). При запросе типа [latex]1[/latex] [latex](x_i > 0)[/latex] выводим разницу между полученными максимумом и минимумом.

Ссылки

  • Засчитанное решение на сайте e-olymp.
  • Рабочий код на Ideone.
  • Статья про Дерево Отрезков на e-maxx.

A299

Условие

Дана последовательность действительных чисел [latex]a_1, a_2, \dots, a_n[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]a_1 \geq 0[/latex], в противном случае — на квадрат наибольшего.

Решение

Для решения воспользуемся стандартным классом vector. Для этого заведем переменную данного типа, заполним её числами со входного потока. Далее, в зависимости от первого (нулевого) элемента вектора, воспользуемся стандартной функцией min_element() или max_element() (библиотека algorithm). Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.

Тесты

Входные данные Выходные данные
1 -2 2 43 5 -10 12 0 -1 -3698 3698 79507 9245 -18490 22188 0 -1849
2 0 100 99 0 -1 1 0 100 99 0 -1 1
3 42 1 1 1 0 -1 24 -24 -42 74088 1764 1764 1764 0 -1764 42336 -42336 -74088

Код

Замечание

Перед изменением значения членов последовательности и их выводом нам необходимо найти минимум или максимум, для чего необходимо знать значения всех её членов. В связи с этим, решить задачу в формате «считал — вывел» (потоковой обработкой) невозможно.

Ссылки

Код на ideaone (vector).

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].

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

А410е

Дана целочисленная матрица [latex][a_{ij}], ij=1,\ldots,n.[/latex] Получить [latex]b_{1},\ldots,b_{n}[/latex], где [latex]b_{i}[/latex] — это: [latex]\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}[/latex].

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex]-го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1}= 2[/latex], [latex]b_{2}= 4[/latex].

Для нахождения максимума  [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ji}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

 Тесты:

Матрица порядка [latex]n[/latex], где [latex]n[/latex]: [latex]a[i][j][/latex]: Результат: Комментарий:
2 [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] 2 4 Пройден.
3 [latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex] 3 -8 -6 Пройден.

 

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

Ю11.15

Метод парабол. Найти минимум заданной функции [latex]y=f(x)[/latex], двигаясь от заданной точки [latex]x_{0}[/latex] по методу парабол:

[latex]x_{i+1}=x_{i}-\frac{h}{2}\frac{f\left( x_{i}+h\right)-f\left( x_{i}-h\right)}{f\left( x_{i}+h\right)-2f\left( x_{i}\right)+f\left( x_{i}-h\right)}, i=0,1,\ldots[/latex], пока не будет достигнута заданная точность.

Функция [latex]x^{3}+10\sin (5x)[/latex]:

Безымянный

[latex]x_{0}[/latex] [latex]\varepsilon[/latex] Точка минимума по графику. Точка минимума по программе. Комментарий.
0 0,001 -0,315353 -0,315353 Тест пройден.
1 0,0001  0,932048 0,932048 Тест пройден.
2 0,0001  2,14327 2,14327 Тест пройден.
-3 0,01 -2,93616 -2,93616 Тест пройден.
-2 0,0001  -1,6017 -1,6017 Тест пройден.

Код программы (C++):

Для функции [latex]x^{3}+10\sin (5x)[/latex] (функцию всегда можно изменить, достаточно исправить строку 6):

Java:

 

Чтобы сделать программу, я почитала “Численные методы” Н. Н. Калиткина, где и было сказано, что в качестве вспомогательного шага [latex]h[/latex] при расчётах на ЭВМ обычно выбирают значение 0,001.

Далее пользователю предоставляется возможность ввести значение [latex]x_{0}[/latex] и задать точность [latex]\varepsilon[/latex].  Корень [latex]x[/latex] является минимумом функции тогда и только тогда, когда вторая производная этой функции больше 0. Поэтому мы запускаем цикл, который будет сдвигать наше [latex]x_{0}[/latex] в положительном направлении оси [latex]x[/latex], пока вторая производная функции не будет удовлетворять условию задачи.

Далее мы вычисляем значение [latex]x_{i+1}[/latex], и запускаем цикл, который будет продолжаться до тех пор, пока разница между [latex]x_{i}[/latex] и [latex]x_{i+1}[/latex]  не будет меньше заданной погрешности [latex]\varepsilon[/latex].

Затем на экран выводится сама точка минимума функции.

Программу можно посмотреть здесь (C++) и здесь (Java).

А170

Задача. Даны натуральные числа [latex]n, a_{1}, a_{2},\ldots, a_{n} (n\geq 4)[/latex]. Числа [latex]a_{1}, a_{2},\ldots , a_{n}[/latex] — это измеренные в сотых долях секунды результаты [latex]n[/latex] спортсменов в беге на [latex]100[/latex] м. Составить команду из четырёх лучших бегунов для участия в эстафете [latex]4\times100[/latex], т.е. указать одну из четверок натуральных чисел [latex]i, j, k, l[/latex], для которой [latex]1\leq i\leq j\leq k\leq l\leq n[/latex] и [latex]a_{i} + a_{j}+a_{k} + a_{l}[/latex] имеет наименьшее значение.

Тесты

      n         c Результаты бега спортсменов Номера спортсменов, избранных для команды Комментарий
6 3 11.77 12.34 12.14 11.15 11.16 11.40 4 5 6 Пройден
6 4 11.68 0 12.15 11.54 11.26 11.00 Введен отрицательный или нулевой результат Не пройден
6 2 11.68 -12.34 12.14 11.55 11.29 11.00 Введен отрицательный или нулевой результат Не пройден

 

Код программы на C++:

В этой задаче необходимо было найти номера лучших бегунов, для создания из них команды. Размер команды вводим сразу же после общего количества бегунов с клавиатуры. Для нахождения номеров бегунов нам потребуется функция mini, которая находит минимальный элемент массива и возвращает его значение, а также  функция team, вызывающая функцию mini. В функции team уже создан массив номеров бегунов, в который мы вначале  введем данные и отсортируем его по возрастанию. Также будем выводить номер этого минимального элемента на экран, прибавляя 1 (как бы считая бегунов с 1, а не с 0),  и присваивать этому (найденному) элементу массива какое-то большое значение для того, чтобы при следующей проверке программа не считала его минимальным элементом, а находила следующий минимальный.

В строках

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

В конечном итоге, применяем функцию team и получаем, собственно, ответ.

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

 

Horse-racing Duals

Horses2

Задача

Рассмотрим последнюю задачу уровня Easy с сайта codingame.com. Некоторое количество лошадей участвует в скачках и у каждой есть некая характеристика, выраженная целым числом. Формат скачек — парные заезды — и организаторы хотят, чтобы в заезде участвовали две лошади, различие между которыми (т.е. разность их характеристик) минимальна.

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

Первая строка: число  n  — количество лошадей.

Следующие  n  строк — в каждой указано одно целое число — характеристика соответствующей лошади.

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

Наименьшая положительная разность характеристик.

Решение

Пусть задана конечная последовательность целых чисел  a. В исходной формулировке задачи, без каких-либо оптимизаций, от нас требуют найти  [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right|[/latex]. Если решать задачу  в лоб, нам понадобятся два цикла: один пробегает все значения по   i, а другой — все значения по  [latex] j > i [/latex]. На каждом шаге внешнего цикла будет проделано  [latex] n — i [/latex] шагов внутреннего. Итого получаем приблизительную оценку сложности такого алгоритма:  [latex] n\left( n — i \right)[/latex], что асимптотически эквивалентно  [latex] n^2 [/latex].

Оказывается, можно решить задачу «проще». Как утверждают авторитетные источники, сложность встроенного в стандартную библиотеку алгоритма сортировки составляет  [latex] O(n \cdot \log \left( n \right) [/latex], что при больших значениях  n  лучше, чем  [latex] n^2 [/latex]. Пусть  b  —  конечная последовательность, в которой элементы последовательности  a  расположены по возрастанию. Поскольку множество значений у этих последовательностей одинаково, имеем: [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right| [/latex]. Однако нам уже не нужен двойной цикл. Благодаря монотонному возрастанию последовательности  b,  при любом   [latex] i [/latex]   имеем  [latex] b_{i+1} — b_{i} > 0 [/latex] и при любых  [latex] i,j [/latex]  если  [latex]i < j[/latex], то  [latex] b_{j} — b_{i} \geq b_{i+1} — b_{i}[/latex].

Значит, [latex] D = min_{1 \leq i \leq n} \left( b_{i+1} — b_{i} \right) [/latex], а эту проверку можно провести за  n  действий. Таким образом, новая сложность составит примерно  [latex] n \cdot log(n) + n [/latex], что асимптотически эквивалентно  [latex] n \cdot log(n) [/latex]  и, значит, для больших значений лучше «безоптимизационного» подхода.

Код на С++

Код на Java

Подтверждение

Horses3

Horses

 

Temperatures

Температуры

Задача взята с сайта codingame.com

Задача.

Задан набор целых чисел (значения температуры за различные моменты времени). Нужно вывести из них ближайшее к нулю.

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

Задан набор целых чисел (значения температуры за различные моменты времени). Нужно вывести из них ближайшее к нулю.

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

Вывести нуль, если  [latex] N = 0[/latex]. В противном случае вывести число, ближайшее к нулю, причём если два числа разных знаков одинаково близки к нулю, нужно вывести положительное.

Решение.

Сначала отфильтруем случай, когда  [latex] N = 0[/latex]. В этом случае, как от нас и требуют, напечатаем нуль.

Если же  [latex] N > 0 [/latex], прибегнем к уже знакомому нам приёму. Введём новую переменную — min — и присвоим ей первое число. Затем в цикле for будем эту переменную менять, если наткнёмся число, более близкое к нулю, чем хранящееся в min. Вот основной вопрос: когда нам нужно менять min? «Число  [latex] a [/latex]  ближе к нулю, чем число  [latex] b [/latex]»  означает, что  [latex] a [/latex] по модулю меньше, чем   [latex] b [/latex]. Значит, если число, прочитанное на текущем шаге цикла, по модулю строго меньше, чем число, хранящееся в min, переменную min нужно обновить. Но есть ещё один случай, когда переменную min следует обновить — это тот случай, когда текущее число положительно и столь же близко к нулю, как и число, хранящееся в min. Это действие даёт нам гарантию того, что если два числа разных знаков одинаково близки к нулю, будет выведено положительное.

Код на С++

Код на Java

 

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

А35б

Даны действительные числа [latex]x,y,z[/latex].Вычислить [latex]min^2(x+y+\frac{z}{2},xyz)+1[/latex]

x y z m
4.8 5.7 2.1 134.40250
0 0 0 1
-3.21 2.89 4.25 1555.47453

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

Код на Java:

 

Вводим числа [latex]x,y,z[/latex]. Вычисляем [latex]a=x+y+\frac{z}{2}[/latex]. Вычисляем [latex]b=xyz[/latex].Сравниваем два числа и присваиваем [latex]min[/latex] минимальное из значений.
Вычисляем  [latex]m=min^2+1[/latex].

Запустить код на С++ и проверить тесты можно тут.
Запустить код на Java и проверить тесты можно тут.

Ю2.21

Задача: Имеются три раствора полезного вещества с концентрациями [latex]p_{1}, p_{2}, p_{3}[/latex] каждый и стоимостью [latex]s_{1}, s_{2}, s_{3}[/latex] соответственно. Можно ли смешать их так, чтобы получить раствор с заданной концентрацией [latex]p[/latex] наименьшей стоимости [latex]s[/latex]?
Указание. Пусть [latex]\alpha_{1}, \alpha_{2}, \alpha_{3}[/latex]- долевые содержания растворов в смеси. Тогда для получения заданной концентрации [latex]p[/latex] необходимо [latex]p_{1}\alpha_{1} + p_{2}\alpha_{2} + p_{3}\alpha_{3}=p[/latex].
Кроме того, нужно учесть условие «комплектности смеси»: [latex]\alpha_{1} + \alpha_{2} + \alpha_{3} = 1[/latex]; [latex]\alpha_{1} \ge 0; \alpha_{2} \ge 0; \alpha_{3} \ge 0;[/latex]
При этих условиях необходимо найти наименьшее значение линейной функции: [latex]s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }[/latex].
С учётом ограничений задача сводится к минимизации линейной функции одного переменного на отрезке, однако искомые выражения и условия получаются достаточно громоздкими. Можно показать, что в решении будут участвовать не более двух растворов. Тогда достаточно среди вариантов:
а) [latex]\alpha_{1} = 0[/latex];
б) [latex]\alpha_{2} = 0[/latex];
в) [latex]\alpha_{3} = 0[/latex];
Выбрать оптимальный, и затем провести необходимые расчеты.
Тесты

1 2 3 p s Комментарий
[latex]p_{i}[/latex] 0 0 0 0 10 Пройден
[latex]s_{i}[/latex] 10 12 14
[latex]p_{i}[/latex] 0 10 30 0 10 Пройден
[latex]s_{i}[/latex] 10 20 30
[latex]p_{i}[/latex] 15.3 49.2 51.6 37.4 29.56 Пройден
[latex]s_{i}[/latex] 40 10 20
[latex]p_{i}[/latex] 30 30 30 40 Impossible Пройден
[latex]s_{i}[/latex] 25 14 40
[latex]p_{i}[/latex] 20.3 20.3 20.3 20.3 30 Пройден
[latex]s_{i}[/latex] 30 40 50
[latex]p_{i}[/latex] 30 40 50 20 Impossible Пройден
[latex]s_{i}[/latex] 19 31 22
[latex]p_{i}[/latex] 20 60 80 40 40 Пройден
[latex]s_{i}[/latex] 60 20 100
[latex]p_{i}[/latex] 20 50 90 50 15.71 Пройден
[latex]s_{i}[/latex] 10 80 20
[latex]p_{i}[/latex] 10 60 90 62.5 62.5 Пройден
[latex]s_{i}[/latex] 190 10 20

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

Метод решения:
Задача сводится к решению системы уравнений:
[latex]\begin{cases} p_{1} \alpha_{2} + p_{2} \alpha_{2} + p_{3} \alpha_{3} = p,\\ \alpha_{1} + \alpha_{2} + \alpha_{3} = 1,\\ s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }; \end{cases}[/latex]

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

Аналитическое решение в данном случае тривиально:
[latex]\begin{cases} p_{i} \alpha_{i} + p_{j} \alpha_{j} = p,\\ \alpha_{i} + \alpha_{j} = 1; \end{cases} \Rightarrow \begin{cases} \alpha_{i} = \frac { p-p_{i} } { p_{j}-p_{i} },\\ \alpha_{j} = 1-\alpha_{i}; \end{cases} s = s_{i} \alpha_{i} + s_{j} \alpha_{j};[/latex]

Для большей наглядности применяется функция c_price (calculate price), в теле которой рассмотрены крайние случаи:
1) Если [latex]p_{1}=p_{2}=p[/latex], то нужно выбрать раствор наименьшей стоимости.
2) Если [latex]p_{1}=p_{2} \ne p[/latex], то решений нет.
3) Если [latex]p_{1}=p \ne p_{2}[/latex], то [latex]s = s_{1}[/latex]. Аналогично в случае [latex]p_{2}=p \ne p_{1}[/latex].
4) Если доля раствора в смеси [latex]\alpha 1[/latex], то решений нет.

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

Протестировать работу программы можно по ссылке.
Реализация на Java: http://ideone.com/qTQpMX