ЕГЭ задание 27. Анализ данных
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой \( H \) и шириной \( W \). Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками \(A(x_1, y_1) \) и \(B(x_2, y_2) \) на плоскости, которое вычисляется по формуле:
\[ d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \]
В файле A хранятся данные о звёздах двух кластеров, где \(H=3 \), \(W=3 \) для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата \(x \), затем координата \(y \). Значения даны в условных единицах. Известно, что количество звёзд не превышает \( 1000 \).
В файле Б хранятся данные о звёздах трёх кластеров, где \(H=3 \), \(W=3 \) для каждого кластера. Известно, что количество звёзд не превышает \(10\ 000 \). Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x \) — среднее арифметическое абсцисс центров кластеров, и \(P_y \) — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения \(P_x \times 10\ 000 \), затем целую часть произведения \(P_y \times 10\ 000 \) для файла А, во второй строке — аналогичные данные для файла Б. Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна N километров. Нулевой и N-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплекты питания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна.
Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.
Входные данные
Даны два входных файла (файл А и файл в), каждый из которых в первой строке содержит число N \((1 \leqslant N \leqslant 10 000 000)\) - количество пунктов питания на кольцевой трассе. В каждой из следующих N строк находятся одно число - количество комплектов питания на пункте (все числа натуральные, количество комплектов питания на каждом пункте не превышает 1000). Числа указаны в порядке расположенияпунктов питания спортсменов на трассе, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем - для файла В.
Типовой пример организации данных во входном файле
6
8
20
5
13
7
19
При таких исходных данных, еслипункты питания установленына каждом километре трассы, необходимо открыть мобильный цех подготовки комплектов питания для спортсменов в пункте 6. В этомслучае сумма транспортных затрат составит: \( 1 \cdot 7 + 0 \cdot 19 + 1 \cdot 8 + 2 \cdot 20 + 3 \cdot 5 + 2 \cdot 13.\)
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Компания, ведущая мониторинг линии электропередач, получила N числовых значений измерений высоты растений (в мм) вдоль этой линии, которые выполнялись последовательно друг за другом.
Высоту растений с точки зрения безопасности линии электропередач оценивают на основе анализа сумм всех возможных непрерывных подпоследовательностей полученных числовых значений, среди которых требуется выбрать подпоследовательность с максимальной суммой, кратной k = 137. Среди таких непрерывных подпоследовательностей необходимо выбрать подпоследовательность с наибольшим количеством элементов, то есть ту, в которой суммируются числовые значения высот наибольшего количества растений. В ответе укажите её длину.
Входные данные
Дано два входных файла (файл А и файл В), каждый из которых в первой строке содержит число N \((1 \leqslant N \leqslant 10 000 000)\) - количество измерений высоты растений (в мм). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000 - числовое значение одного результата измерения.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем - для файла В.
Типовой пример организации данных во входном файле
7
100
300
400
9300
800
500
9500
При таких исходных данных при k = 5000 искомая максимальная сумма составляет 300 + 400 + 9300 или 500 + 9500 и равна 10000; ответом на вопрос задачи является число 3.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 11 м3. Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите минимальные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок.
Входные данные
Даны два входных файла (файл \( A \) и файл \( B \)), каждый из которых в первой строке содержит два числа \( N \), \( K \) \( (1 \leqslant N \leqslant 10 000 000, 1 \leqslant K \leqslant 10 000 000) \) — соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих \( N \) строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.
Запишите в ответе два числа: сначала значение искомой величины для файла \( A \), затем — для файла \( B \).
Типовой пример организации данных во входном файле
6 40
2 1
9 5
16 20
25 2
32 22
40 6
При таких исходных данных и вместимости бензовоза 3 м3 минимальные расходы на доставку топлива расположенного нефтехранилища составят: \( 10 \cdot 1 + 17 \cdot 2 + 16 \cdot 7 + 7 \cdot 1 + 0 \cdot 8 + 8 \cdot 2 \).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
По каналу связи передаётся последовательность целых чисел - показания прибора. В течение \( N \) мин. (\( N \) - натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передаёт его на сервер.
Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее \( K \) мин., а сумма этих трёх чисел была максимально возможной. Запишите в ответе найденную сумму.
Входные данные
Даны два входных файла (файл \( A \) и файл \( B \)), каждый из которых в первой строке содержит натуральное число \( K \) - минимальное количество минут, которое должно пройти между моментами передачи показаний, а во второй строке - количество переданных показаний \( N \) \( (1 \leqslant N \leqslant 10 000 000, N > K) \). В каждой из следующих \( N \) строк находится одно целое число, по модулю не превышающее 10 000 000, которое обозначает значение напряжения в соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла \( A \), затем - для файла \( B \).
Типовой пример организации данных во входном файле
2
6
5
7
3
1
3
9
При таких исходных данных искомая величина равна 17 - это сумма значений, зафиксированных на второй, четвёртой и шестой минутах измерений.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
По каналу связи передаётся последовательность целых чисел - показания прибора. В течение \( N \) мин. (\( N \) - натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передаёт его на сервер.
Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее \( K \) мин., а сумма этих трёх чисел была максимально возможной. Запишите в ответе найденную сумму.
Входные данные
Даны два входных файла (файл \( A \) и файл \( B \)), каждый из которых в первой строке содержит натуральное число \( K \) - минимальное количество минут, которое должно пройти между моментами передачи показаний, а во второй строке - количество переданных показаний \( N \) \( (1 \leqslant N \leqslant 10 000 000, N > K) \). В каждой из следующих \( N \) строк находится одно целое число, по модулю не превышающее 10 000 000, которое обозначает значение напряжения в соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла \( A \), затем - для файла \( B \).
Типовой пример организации данных во входном файле
2
150
-150
20
-200
-300
При таких исходных данных искомая величина равна 170 - это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла В не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.