| Gadgets powered by Google

# Блог Артема Игликова

программирование, соревнования, операционные системы и все такое

- Главная
- Об авторе
- Проекты
- Сейчас…

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

Январь 22, 2009 – 21:41

На прошлой неделе буквально одновременно с 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 - компания предлагает производство и монтаж пластиковых окон в Москве.

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

Разделы: Олимпиады

## Комментарии (12)

1. ZhVoid, Янв 26, 2009, 03:22

   Даа… интересно сколько человек решило задачу со степенями на 100%

   Ответить

   admin, Янв 26, 2009, 10:39

   Мне тоже интересно… На моих выложенных тестах, которые довольно слабые, наверное, далеко не все. Ну а на местах, где, скорее всего, было от силы 5 ручных тестов, думаю, многие :)

   Ответить

2. Александр, Апр 2, 2009, 16:02

   А решить и откоментировать задачи третьего этапа слабо :)?

   Ответить

   admin, Апр 2, 2009, 22:52

   всему свое время

   Ответить

   tinker, Апр 3, 2009, 12:36

   а когда будут известны участники которые прошли на 5 тур?

   Ответить

   admin, Апр 3, 2009, 12:40

   понятия не имею. но точно перед началом 5-го тура :)

   Ответить

   N'aix, Апр 3, 2009, 14:58

   а когда будет 5 тур?

   Ответить

   admin, Апр 3, 2009, 22:00

   насколько я знаю с 15 по 20 апреля

   Ответить

   Александр, Апр 4, 2009, 11:29

   Уважаемый admin.
   Соревнования без результатов бессмысленны и бесполезны.

   Ответить

   admin, Апр 4, 2009, 12:23

   это вы к чему?

   Ответить

3. narik, Апр 27, 2009, 13:47

   Уважаемый Артем! а можете ли вы опубликовать решения задач городской олимпиады 2009 ?
   и просьба можете ли вы опубликовать некоторые задачи на языке Паскаль?(просто я еще не понимаю С++)

   Ответить

   admin, Апр 27, 2009, 14:55

   разборы опубликую, как только будет время. решения на pascal вроде есть на olympiads.kz

   Ответить

## Оставить комментарий

Имя (обязательно):

E-mail (не публикуется, обязательно):

Вебсайт:

Уведомлять о новых комментариях по e-mail

Отмена