Информатика ЕГЭ — ФИПИ тапсырмаларының жауаптарымен шешімдері

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

Разбить точки на кластеры. Так как размеры ограничивающих прямоугольников равны $H=6{,}0$ и $W=5{,}5$, точки одного кластера должны помещаться в одном таком прямоугольнике, а прямоугольники разных кластеров не должны пересекаться.

Разность элементов пары должна быть чётной, поэтому элементы пары должны иметь одинаковую чётность.

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

Пусть пункты пронумерованы от $0$ до $N-1$, а в пункте $i$ находится $a_i$ комплектов. Если цех расположен в пункте $k$, расстояние до пункта $i$ равно $\min(|i-k|, N-|i-k|)$.

Стоимость положения $k$ равна $F(k)=\sum_{i=0}^{N-1} a_i\min(|i-k|,N-|i-k|)$. Прямой перебор всех пар имеет сложность $O(N^2)$ и не подходит для файла B.

Так как 17 — простое число, произведение двух чисел делится на 17 тогда и только тогда, когда хотя бы один множитель делится на 17.$$17 \mid (a_i a_j) \Longleftrightarrow 17 \mid a_i \lor 17 \mid a_j$$

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

Для каждого ученика считываем фамилию, имя и три оценки. Средние баллы можно не вычислять: число экзаменов у всех одинаково, поэтому сравнение средних баллов эквивалентно сравнению сумм оценок.$$a_1+a_2+a_3$$

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

Сначала необходимо прочитать координаты точек из файлов А и Б и разделить точки на кластеры по условию о прямоугольниках заданных размеров.

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

Считать координаты и характеристики всех звёзд из файлов A и Б.

Разбить точки каждого файла на кластеры. Для каждой группы необходимо проверить, что все её точки можно разместить внутри прямоугольника со сторонами $6{,}0$ и $5{,}5$, допускающего произвольный поворот, и что прямоугольники разных…

Разность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность. Поэтому пары рассматриваются отдельно для чётных и нечётных чисел.$$a-b \equiv 0 \pmod 2 \Longleftrightarrow a \equiv b \pmod 2$$

В допустимой паре хотя бы одно число должно делиться на $17$. Для каждой чётности достаточно хранить два наибольших числа, кратных $17$, и два наибольших числа вообще. Любая максимальная допустимая пара будет состоять либо из двух чисел…

Для каждого числа достаточно знать два булевых признака: делится ли оно на $2$ и делится ли оно на $3$. Это определяет один из четырёх типов числа.

Произведение двух чисел делится на $6$, если среди двух чисел есть хотя бы один множитель $2$ и хотя бы один множитель $3$. Поэтому для очередного числа можно добавить к ответу количество уже обработанных чисел совместимых с его типом.

Считать координаты точек из файлов А и Б. Для файла Б временно рассматривать все точки, включая три аномалии.

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

Разность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность. Поэтому достаточно рассматривать отдельно пары чётных и пары нечётных чисел.

При обработке очередного числа $x$ возможная подходящая пара должна содержать либо само число $x$, если оно делится на 19, либо ранее встреченное число той же чётности, делящееся на 19.

Так как $26 = 2 \cdot 13$, произведение двух чисел делится на $26$, если в произведении присутствуют множители $2$ и $13$.$$26 = 2 \cdot 13$$

Число, кратное $26$, образует подходящую пару с любым другим числом. Поэтому при чтении такого числа к ответу добавляется количество всех уже прочитанных чисел.

Из файлов необходимо считать координаты и обозначения классов всех звёзд. Для звёзд класса светимости $VII$ спектральный класс и подкласс отсутствуют.

Разделить точки на кластеры. Для каждой пары точек можно использовать геометрическое условие принадлежности одному прямоугольнику со сторонами $6{,}0$ и $5{,}5$; гарантии задачи обеспечивают единственность разбиения.

Обозначим префиксную сумму через $P_i=a_1+a_2+\dots+a_i$, причём $P_0=0$. Сумма подпоследовательности $S(L,R)$ равна $P_R-P_{L-1}$.

Сумма $P_R-P_{L-1}$ чётна тогда и только тогда, когда $P_R$ и $P_{L-1}$ имеют одинаковую чётность.

Считать координаты и характеристики звёзд из файлов А и Б.

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

Загрузить координаты точек из файла A и разделить их на два кластера. Разбиение можно выполнить перебором или алгоритмом кластеризации с проверкой того, что каждый кластер помещается в прямоугольник со сторонами $6$ и $4{,}5$.

Для каждой точки каждого кластера вычислить сумму евклидовых расстояний до всех остальных точек этого кластера. Точка с минимальной суммой является центром кластера.$$S_i=\sum_{j\ne i}\sqrt{(x_j-x_i)^2+(y_j-y_i)^2}$$

Введём префиксные суммы $P_0=0$, $P_i=a_1+a_2+\dots+a_i$. Сумма подпоследовательности от $j+1$ до $i$ равна разности $P_i-P_j$.$$S(j+1,i)=P_i-P_j$$

Разность $P_i-P_j$ нечётна тогда и только тогда, когда префиксные суммы имеют разную чётность.

Для фиксированного среднего индекса $j$ выражение можно преобразовать:$$(S_j-S_i)+(S_j-S_k)=2S_j-S_i-S_k$$

При фиксированном $j$ для максимизации выражения необходимо выбрать минимальный элемент слева от позиции $j$ и минимальный элемент справа от позиции $j$.

Считать координаты точек из файлов А и Б. Для файла Б обнаружить и исключить три точки, которые не входят ни в один из трёх кластеров.

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

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

В каждом кластере для каждой точки вычисляется сумма расстояний до всех остальных точек. Точка с наименьшей суммой принимается за центр кластера.