Задача A. Группировка выборки

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Из генеральной совокупности извлечена выборка {xi}ni = 1 объёма n. Требуется представить выборку в виде вариационного ряда:

x1x2xk
m1m2mk
w1w2wk
Где xj(j = 1,2,...,k) — уникальные элементы из выборки {xi}ni = 1, отсортированные в порядке возрастания, mj - частота, т.е. количество элементов xj в исходной выборке, wj = mj / n — относительная частота (частость) элемента xj.

Порядок выполнения:

1) На первом этапе статистической обработки производят ранжирование выборки, т.е. упорядочивание чисел x1, x2, …, xk по возрастанию. Каждое наблюдаемое значение xj называется уровнем (вариантой).

2) Подсчитывается mj частота каждого уровня;

3) Подсчитываются относительные частоты wj.

Формат входного файла

Входные данные содержат число n, за которым следует n целых чисел.

Формат выходного файла

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

Ограничения

1 < n < 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
0 1 0 1
0 1
2 2
0.5 0.5
2
10
1 4 2 2 4 3 4 4 3 3
1 2 3 4
1 2 3 4
0.1 0.2 0.3 0.4

Задача B. Среднее арифметическое

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

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

Формат входного файла

Входные данные содержат число n, за которым следует n положительных вещественных чисел.

Формат выходного файла

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

Ограничения

1 < n < 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 3 5
3

Задача C. Среднее гармоническое

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

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

Формат входного файла

Входные данные содержат число n, за которым следует n положительных вещественных чисел.

Формат выходного файла

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

Ограничения

1 < n < 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 3 5
1.957

Задача D. Средние взвешенные

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

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

Формат входного файла

Входные данные содержат число n, за которым следует n строк, состоящих из пар чисел: вещественное число xi и соответствующая ему частота mi (т.е. количества элементов xi в исходной выборке).

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 300, 1 ≤ mi ≤ 5, 0 < xi < 3

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
2 4
3 4
2.5 2.4 2.449

Задача E. Центральный момент

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Задана выборка {xi} объёма n. Требуется вычислить выборочный центральный момент k-го порядка.

Формат входного файла

Входные данные содержат числа n и k, за которыми следует n вещественных чисел разделённых пробелом.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 105, 1 ≤ k ≤ 5

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 1
1 4 5 4 4 5 1 5 2 3
0
2
10 2
7 8 -2 -8 8 -3 9 -6 1 -2
36.16

Задача F. Гистограмма

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть имеется выборка {xi}ni = 1. Для построения гистограммы необходимо разбить выборку на интервалы равной длины [b1, b2), [b2, b3) … [bk, bk + 1], b1 = mini xibk + 1 = maxi xi.

Число k - оптимальное количество интервалов - вычисляется согласно формуле Стёрджеса k = 1 + ⌊log2 n, где ⌊ ...⌋ — антье.

Формат входного файла

Входные данные содержат число n, за которым следует n вещественных чисел.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
0 1 2
1 2
2
6
8 9 2 1 2 0
4 0 2
3
6
8 9 1 2 0 10
3 0 3

Задача G. Корреляция

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

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

Формат входного файла

Первая строка входных данных содержит целые числа N и M — количество и длину выборок соответственно. Каждая из последующих N строк содержит по M вещественных чисел.

Формат выходного файла

Выходные данные должны содержать матрицу размером N× N — матрицу коэффициентов корреляции. Вещественные числа необходимо вывести с точностью не менее трёх знаков после запятой.

Ограничения

2 ≤ N < 50, 1 < M < 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 10
6 -10 10 -5 -8 -4 4 -5 0 4
4 -5 3 10 -2 -1 -6 -2 2 -8
1 0.075
0.075 1
2
3 10
2 -3 -6 -3 0 0 -7 6 -1 -8
-5 5 4 1 13 10 -10 -1 9 2
4 -2 4 3 5 4 -1 0 3 4
1 0.158 0.01
0.158 1 0.462
0.01 0.462 1

Задача H. Ранговая корреляция

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

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

Формат входного файла

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

Формат выходного файла

Выходные данные должны содержать матрицу размером n× n — матрицу коэффициентов корреляции. Вещественные числа необходимо вывести с точностью не менее трёх знаков после запятой.

Ограничения

2 < n < 5, 1 < m < 103

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 4
1 2 3 4
4 3 2 1
1 -1
-1 1
2
2 7
1 2 3 4 5 6 7
7 6 4 5 3 2 1
1 -0.905
-0.905 1

Задача I. Линейная регрессия

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Требуется написать программу, которая вычисляет коэффициенты линейной регрессии y = a⋅ x + b. Коэффициенты предполагается вычислять методом наименьших квадратов.

Формат входного файла

Первая строка входных данных содержит целое число N — длину выборки. 2 последующие строки содержат по N вещественных чисел: первая строка содержит значения независимой переменной X, вторая — значения зависимой переменной Y.

Формат выходного файла

Выходные данные должны содержать 2 числа a и b — коэффициенты регрессии с точностью не менее трёх знаков после запятой.

Ограничения

1 < N < 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
3 4
1 2
2
5
1 2 3 4 5
6 3 5 3 -3
-1.8 8.2

Задача J. Интервальная оценка

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть имеет место уравнение линейной регрессии  = β0 + β1 x. Требуется написать программу, вычисляющую интервальные оценки параметров β0 и β1 с уровнем доверия α.

Для вычисления t-распределения рекомендуется использовать класс scipy.stats.t.

Использовать формулы (4.13), (4.19) и (4.7) из учебника В. С. Мхитаряна.

Формат входного файла

Первая строка входных данных содержит два числа n, α — длину выборки и уровень доверия. Две последующие строки содержат по n вещественных чисел: первая строка содержит значения независимой переменной X, вторая — значения зависимой переменной Y.

Формат выходного файла

Выходные данные должны содержать 4 числа — границы интервальных оценок параметров β0 и β1 соответственно с точностью не менее трёх знаков после запятой.

Ограничения

3 ≤ n ≤ 105, 0.5 < α 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 0.95
1 2 3 4 5
6 3 5 3 -3
4.872 11.528 -4.153 0.553

Задача K. Оценка матожидания

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Известно n значений {xi}ni = 1 случайной величины X, распределённой по нормальному закону: XN(μ, σ2), где μ — математическое ожидание, σ2 — дисперсия. По данной выборке найти границы доверительного интервала, покрывающего математическое ожидание случайной величины X с уровнем доверия α. Рассмотреть два случая: а) при известной генеральной дисперсии; б) при неизвестной генеральной дисперсии.

В программе рекомендуется использовать модуль scipy.stats.

Формат входного файла

Первая строка входных данных содержит три вещественных числа n, α, σ2 — длину выборки, уровень доверия и дисперсию, при этом если σ20, то дисперсия считается неизвестной. Вторая строка содержит n вещественных чисел — выборку {xi}ni = 1.

Формат выходного файла

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

Ограничения

3 ≤ n ≤ 105, 0.5 < α 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 0.95 1
-0.406647 1.15391 -1.01899 -1.45092 -0.492494
-1.32 0.433
2
5 0.95 -1
-0.406647 1.15391 -1.01899 -1.45092 -0.492494
-1.814 0.928

Задача L. Критерий согласия хи-квадрат

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Требуется написать программу, которая вычисляет значение p-value критерия согласия хи-квадрат.

Для вычисления p-value можно использовать, например, scipy.stats.chi2.

Формат входного файла

Первая строка входного файла содержит число n — количество уровней. Вторая строка содержит n целых чисел ci — частоту уровня i. Третья строка содержит n вещественных чисел pi — ожидаемую вероятность уровня i.

Формат выходного файла

Выходные данные должны содержать одно вещественное число — p-value критерия согласия хи-квадрат с точностью до 3 знаков после запятой.

Ограничения

2 ≤ n ≤ 10000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6
5 8 9 8 10 20
0.16666666 0.16666666 0.16666666 0.16666666 0.16666666 0.16666666
0.02

Задача M. Вероятность

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Требуется написать на языке Python функцию probability(pdf, a, b), которая принимает функцию плотности распределения (функция, принимающая один аргумент и возвращающая число от 0 до 1) и интервал и возвращает вероятность попадания случайной величины в этот интервал.

Формат выходных данных

Код решения должен содержать только определение и реализацию функции. Он не должен ничего выводить.


Задача N. Собственные значения и векторы

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Требуется написать программу, вычисляющую собственные значения и соответствующие им векторы квадратной матрицы {ai,j}ni,j = 1.

Формат входного файла

Первая строка входного файла содержит целое число n — размер матрицы. Следующие n строк содержат по n вещественных чисел — элементы матрицы ai,j. Элементы матрицы заданы таким образом, что собственные значения и векторы матрицы являются вещественными.

Формат выходного файла

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

Ограничения

2 ≤ n ≤ 200

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
2 1
1 2
1 3
1 -1
1  1

Задача O. СЛАУ. Метод Гаусса

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Требуется написать программу, вычисляющую решение системы линейных алгебраических уравнений Ax = b, используя метод Гаусса, где A = {ai,j}ni,j = 1, x = {xi}ni = 1, b = {bi}ni = 1.

Формат входного файла

Первая строка входного файла содержит целое число n — размер матрицы. Следующие n строк содержат по n целых чисел — элементы матрицы ai,j. Последняя строка файла содержит n целых чисел — элементы вектора bi.

Формат выходного файла

Первая строка выходного файла должна содержать n вещественных чисел — элементы вектора xi с точностью не менее трёх знаков после запятой. Если система не имеет единственного решения необходимо вывести единственное число  − 1.

Ограничения

2 ≤ n ≤ 75

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
3 2 -1
2 -2 4
-1 1 -1
1 -2 0
0.4 -0.6 -1
2
3
1 2 3
4 5 6
7 8 9
1 2 3
-1

Задача P. Сингулярное разложение

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Требуется написать программу, вычисляющую сингулярное разложение матрицы A размерности n× m.

Формат входного файла

Первая строка входного файла содержит 2 целых числа n, m — размерность матрицы. Следующие n строк содержат по m вещественных чисел — элементы матрицы ai,j.

Формат выходного файла

В выходном файле должны содержаться матрицы сингулярного разложения матрицы A = UΣ V * , где матрица U имеет размерность n× n, Σ — n× m, V *  — m× m (рекомендуется использовать метод numpy.savetxt)

Ограничения

2 ≤ nm ≤ 75

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 5
1 0 0 0 2
0 0 3 0 0
0 0 0 0 0
0 4 0 0 0
0 0 1 0
0 1 0 0
0 0 0 -1
1 0 0 0

4 0 0 0 0
0 3 0 0 0
0 0 2.236 0 0
0 0 0 0 0

0 1 0 0 0
0 0 1 0 0
0.447 0 0 0 0.894
0 0 0 1 0
-0.894 0 0 0 0.447

1.164s 0.016s 43