Информатика

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

Маша хочет найти участок с уровнем шума ровно 1 (тихий участок), который находится максимально далеко от шумных участков. Шумным считается участок с уровнем шума 7 или больше.

Необходимо написать программу, которая найдёт номер такого тихого участка и расстояние до ближайшего шумного участка.

Если таких участков несколько, выбрать участок с наименьшим номером.

Гарантируется, что есть хотя бы один тихий участок (уровень шума 1) и хотя бы один шумный участок (уровень шума ≥ 7).

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

• В первой строке натуральное число n (1 ≤ n ≤ 6 000 000)
• Во второй строке n чисел от 1 до 9 через пробел

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

• Номер участка и расстояние до ближайшего шумного (через пробел)

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

Пример: в последовательности 5 8 13 9 17 12 21 25 можно выбрать:

• 5 9 17 21 25 или 5 13 17 21 25 (остаток 1 при делении на 4, длина 5)
• 8 12 (остаток 0 при делении на 4, длина 2)

Максимальная длина = 5.

Напишите программу, которая находит эту максимальную длину.

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

• В первой строке число n (1 ≤ n ≤ 20000)
• Во второй строке n чисел через пробел

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

• Длина самой большой такой подпоследовательности

Размещением из \(n\) по \(k\) называется массив \(a[1..k]\), содержащий \(k\) различных натуральных чисел, каждое из которых находится в диапазоне от \(1\) до \(n\).

Пара подряд идущих элементов размещения \(a[i], a[i + 1]\) называется спуском, если \(a[i] > a[i+1]\). Спуск называется крутым, если \(a[i] > a[i + 1] + 1\).

По заданным \(n\) и \(k\) требуется вывести все размещения из \(n\) по \(k\) без крутых спусков. Размещения необходимо упорядочить по первому числу, при равенстве первого — по второму, затем по третьему и так далее.

Первая строка ввода содержит натуральное число \(n\), вторая строка ввода содержит натуральное число \(k\) (\(1 \le k \le n \le 13\)).

Выведите все размещения из \(n\) по \(k\) без крутых списков, по одному на строке. Внутри размещения разделяйте числа пробелами.

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

Будем рассматривать слова из строчных букв английского алфавита. Гласными считаются буквы <<a>>, <<e>>, <<i>>, <<o>>, <<u>>. Будем считать, что слово имеет женский род, если оно заканчивается на <<a>> (класс 1), либо на букву <<d>> (класс 2а), либо <<z>> (класс 2б), в этих двух случаях предпоследняя буква должна быть гласной, либо на буквосочетание <<ion>> (класс 3). В противном случае слово имеет мужской род.

Формат входных данных
На вход подана одна строка, содержащая слово, содержащее от 2 до 40 букв.

Формат выходных данных
Выведите <<f>>, если слово имеет женский род, либо <<m>>, если оно имеет мужской род.

Как изменение параметра minPts влияет на форму k-distance графика и выбор εε?

1. При увеличении minPts k-расстояния уменьшаются, и локоть смещается к нулю
2. minPts влияет только на итоговые кластеры и никак не связан с k-distance графиком
3. При увеличении minPts k-расстояния, как правило, возрастают, и локоть смещается вправо и вверх
4. Изменение minPts вообще не рекомендуется, он всегда фиксирован

Как выбор параметра k (количество соседей для k-distance) связан с параметром minPts в DBSCAN?

1. Часто выбирают k=minPts или k=minPts−1
2. Обычно выбирают k=1, независимо от minPts
3. Связи между k и minPts нет, они подбираются совершенно независимо
4. k всегда должен быть намного больше minPts

1. Чтобы разнесённые во времени наблюдения шли подряд
2. Чтобы визуально выделить резкий переход от плотных областей к шуму
3. Чтобы получить симметричный график относительно середины
4. Чтобы можно было напрямую прочитать индексы кластеров

На k-distance графике по оси абсцисс отложены отсортированные объекты датасета. Что обычно показывается по оси ординат?

1. Расстояние до ближайшего соседа k=1 для каждого объекта
2. Индекс объекта в исходном порядке выборки
3. Среднее расстояние от объекта до всех других объектов
4. Расстояние до k-го ближайшего соседа для каждого объекта

Реализуйте полный алгоритм DBSCAN. Напишите программу

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

n eps minPts : n - число точек (натуральное число не больше 100, eps - положительное вещественное число не больше 3, minPts - натуральное число не больше 5)

n строк: x y (координаты точек, вещественные числа, по модулю меньше 10**5 )

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

n строк: номер кластера для каждой точки:

• -1 для шума
• нумерация кластеров с 0

Учёный решил провести кластеризацию множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек), лежащих внутри прямоугольника высотой H и шириной W. Каждая звезда принадлежит ровно одному кластеру. Центроид кластера — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд этого кластера минимальна. Расстояние между звёздами вычисляется по формуле Евклида: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

Вам дан список координат звёзд и количество кластеров k. Известно, что все кластеры имеют размер \(H \times W\) и чётко разделены (расстояние между кластерами значительно больше их размера).

Необходимо:

1. Разделить звёзды на k кластеров

2. Найти центроид каждого кластера

3. Вычислить \(P_x\) — среднее арифметическое x-координат всех центроидов

4. Вычислить \(P_y\) — среднее арифметическое y-координат всех центроидов

5. Вывести результат в заданном формате

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

- Первая строка содержит два целых числа n и k (\(1 \le n \le 1000\), \(1 \le k \le 10\)) — количество звёзд и количество кластеров.

- Вторая строка содержит два вещественных числа H и W — размеры каждого кластера.

- Следующие n строк содержат по два вещественных числа \(x_i\)и \(y_i\) (\(-10^6 \le x_i, y_i \le 10^6\)) — координаты звёзд.

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

Выведите два целых числа через пробел:

- Целую часть от \(|P_x \times 10000|\)

- Целую часть от \(|P_y \times 10000|\)

где |x| обозначает абсолютное значение числа x.

1. Кластер 1 (C1)
2. Кластер 2 (C2)
3. На границе кластеров (равные расстояния)
4. Не относится ни к одному кластеру