Разбор задач 2-го этапа Республиканской олимпиады школьников

На прошлой неделе буквально одновременно с V Международной Жаутыковской олимпиадой прошел 2-й этап Республиканской олимпиады школьников, для Алматы являющийся районным. Задачи были довольно несложные, но для полного решения требовалась некоторая сообразительность. Условия задач, тесты к ним и решения как всегда можно найти в правильном месте.

Задача A. Окружность

Во-первых, будем считать, что A1 < B1 и A2 < B2 (если это не так, то добьемся этого поменяв числа в соответствующей паре местами). Далее, нарисовав один-два случая можно заметить, что хорды будут пересекаться или касаться только в трех случаях:

• они совпадают, то есть обе вершины общие:

  ((A1 == A2) && (B1 == B2))

• одна вершина общая:

  ((A1 == A2) || (A1 == B2) || (A2 == B1) || (A2 == B2))

• вершины разные, и для каждой хорды выполняется следующее условие: если окружность разрезать по этой хорде, то вершины другой хорды должны быть в разных частях окружности:

  ((A1 < A2) && (A2 < B1) != (A1 < B2) && (B2 < B1))

Все решение заключается в проверке этих трех условий.

Задача B. Делители

Пусть число Z имеет делитель X. Это значит, что существует такое целое положительное Y, что Z = X * Y. Однако, отсюда следует, что и Y является делителем Z. То есть для любого делителя X < sqrt(Z) найдется также делитель Y > sqrt(Z) и наоборот. Получаем, что наличие у числа Z делителя не равного sqrt(Z) не влияет на четность количества делителей. Осталось два случая:

• sqrt(Z) – целое число (соответственно, являющееся делителем Z), тогда ко всем парным делителям добавляется один непарный, и количество делителей получается нечетным;
• sqrt(Z) – нецелое число, тогда количество делителей не изменяется и остается четным.

Таким образом, задача сводится к определению, является ли Z квадратом целого числа. Ну а проверить это можно, десятком различных способов: от взятия вещественного корня до бинарного поиска.

Задача C. Выгода

Интуиция просто умоляет отсортировать оба массива по убыванию и вывести сумму A[i] * B[i] для всех i от 1 до min(N, M) в качестве ответа.И, как ни странно, это решение будет правильным.

Понятно, почему нужно брать наибольшие min(N, M) чисел из каждого массива. Докажем, почему произведения нужно брать именно в таком порядке.

Оставим в каждом массиве по K = min(N, M) наибольших чисел. Затем отсортируем массив A по убыванию. Теперь нужно расставить числа в массиве B так, чтобы сумма A[i] * B[i] была оптимальным ответом.

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

В нашем конкретном случае:

A[i] * B[i] + A[i + 1] * B[i + 1] > A[i] * B[i + 1] + A[i + 1] * B[i]
 
B[i] * (A[i] - A[i + 1]) > B[i + 1] * (A[i] - A[i + 1])

помня, что A[i] > A[i + 1], разделим обе части на A[i] – A[i + 1]:

B[i] > B[i + 1]

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

Задача D. Лень

Пусть ученик выучит X вопросов. Тогда в худшем случае N – A из них ему не попадутся на экзамене. Ну а остальных должно быть не меньше B чтобы получить пятерку. В общем, получается нужно выучить N – A + B вопросов.

Задача E. Спираль

Стандартная и довольно известная задача на реализацию. Нужно просто сделать то, что просят в задаче.

Задача F. Степень

Самая интересная задача и контеста. Во-первых, понятно, что нужно использовать быстрое возведение в степень. Но возникает проблема – при возведении в степень нужно считать промежуточные произведения довольно больших чисел, которое не вмещается в int64. В качестве обходного пути можно предложить посчитать произведение двух чисел, используя алгоритм быстрого возведения в степень. Более точно смотрите статью о вычислении A * B % C.

Собрались делать ремонт? Заменить старые окна поможет www.oknamaster.ru – компания предлагает производство и монтаж пластиковых окон в Москве.

А вы знали, что бывает лицензия на вывоз мусора? Разобраться с этим и другими видами лицензий поможет Юркомсити.