ݺߣ

ݺߣShare a Scribd company logo

Разбор задач

•Download as PPT, PDF•
•
M
Mikhail Kormyshov

Второй тур школьного этапа Всероссийской олимпиады школьников по информатике 2012

1 of 15
Download to read offline
Разбор задач 2 тура школьного этапа Кормышов Михаил http://krasprog.ru
Задача А. Кольцо Условие Заданы площадь кольца и радиус внешней окружности. Требуется определить радиус внутренней окружности. Ограничение R < 101
Задача А. Кольцо Решение Из условия получаем, что S = πR2 – πr2 Выражаем r = sqrt(R2-S/π). Где π = 3.1415. Такой точности будет достаточно, так как R < 101.
Задача В. Числа без одинаковых цифр Условие Найти N-ое по счёту число без одинаковых цифр. Ограничение N < 104 + 1
Задача В. Числа без одинаковых цифр Решение Учитывая серьёзные ограничения на N, будем перебирать числа в порядке возрастания и для каждого из них смотреть из каких цифр оно состоит.
Задача В. Числа без одинаковых цифр Решение Проверять из каких цифр состоит число можно в цикле, деля его на 10. while (a) if (++m[a%10] > 1) return false; else a /= 10; return true;
Задача В. Числа без одинаковых цифр Оценка времени работы Функция проверки работает за O(lg a), а если быть точным, то не более 6 шагов. Пробный запуск показывает, что для N = 104 ответ равен 26057.
Задача С. Котлеты Условие Требуется поджарить N котлет с обеих сторон, но умещается только K. Какое наименьшее время потребуется? Ограничение N < 30001
Задача С. Котлеты Решение Разработаем схему действий, чтобы в каждый момент времени на сковороде было как можно больше котлет.
Задача С. Котлеты 1. Жарим по K котлет с одной стороны, это займёт T = N / K операций, 2. Жарим остальные котлеты с одной стороны, заполняя сковороду максимально возможным количеством уже прожаренных. Это ещё одна операция,
Задача С. Котлеты 3. Осталось R = N – min(T * K, K – N % K) котлет, прожаренных с одной стороны. С ними можно справиться за (R + K – 1) / K операций, 4. Суммируем, умножаем на М и выводим.
Задача D. Губернатор Условие Для N зданий известны эффективность и расходы на содержание. Определить оптимальный порядок постройки зданий. Ограничение N < 104 + 1
Задача D. Губернатор Анализ взаимного расположения Рассмотрим строительство двух зданий в различном порядке: (Ka1 – b1)a2 – b2 = Ka1a2 – b1a2 – b2 (Ka2 – b2)a1 – b1 = Ka1a2 – b2a1 – b1
Задача D. Губернатор Решение Первый план более предпочтителен, если b1a1 + b2 < b2a1 + b1. Упорядочим здания по этому критерию. Так как N до 104 нам понадобится быстрая сортировка.
Спасибо за внимание Ваши вопросы?

More Related Content

Разбор задач

  • 1. Разбор задач 2 тура школьного этапа Кормышов Михаил http://krasprog.ru
  • 2. Задача А. Кольцо Условие Заданы площадь кольца и радиус внешней окружности. Требуется определить радиус внутренней окружности. Ограничение R < 101
  • 3. Задача А. Кольцо Решение Из условия получаем, что S = πR2 – πr2 Выражаем r = sqrt(R2-S/π). Где π = 3.1415. Такой точности будет достаточно, так как R < 101.
  • 4. Задача В. Числа без одинаковых цифр Условие Найти N-ое по счёту число без одинаковых цифр. Ограничение N < 104 + 1
  • 5. Задача В. Числа без одинаковых цифр Решение Учитывая серьёзные ограничения на N, будем перебирать числа в порядке возрастания и для каждого из них смотреть из каких цифр оно состоит.
  • 6. Задача В. Числа без одинаковых цифр Решение Проверять из каких цифр состоит число можно в цикле, деля его на 10. while (a) if (++m[a%10] > 1) return false; else a /= 10; return true;
  • 7. Задача В. Числа без одинаковых цифр Оценка времени работы Функция проверки работает за O(lg a), а если быть точным, то не более 6 шагов. Пробный запуск показывает, что для N = 104 ответ равен 26057.
  • 8. Задача С. Котлеты Условие Требуется поджарить N котлет с обеих сторон, но умещается только K. Какое наименьшее время потребуется? Ограничение N < 30001
  • 9. Задача С. Котлеты Решение Разработаем схему действий, чтобы в каждый момент времени на сковороде было как можно больше котлет.
  • 10. Задача С. Котлеты 1. Жарим по K котлет с одной стороны, это займёт T = N / K операций, 2. Жарим остальные котлеты с одной стороны, заполняя сковороду максимально возможным количеством уже прожаренных. Это ещё одна операция,
  • 11. Задача С. Котлеты 3. Осталось R = N – min(T * K, K – N % K) котлет, прожаренных с одной стороны. С ними можно справиться за (R + K – 1) / K операций, 4. Суммируем, умножаем на М и выводим.
  • 12. Задача D. Губернатор Условие Для N зданий известны эффективность и расходы на содержание. Определить оптимальный порядок постройки зданий. Ограничение N < 104 + 1
  • 13. Задача D. Губернатор Анализ взаимного расположения Рассмотрим строительство двух зданий в различном порядке: (Ka1 – b1)a2 – b2 = Ka1a2 – b1a2 – b2 (Ka2 – b2)a1 – b1 = Ka1a2 – b2a1 – b1
  • 14. Задача D. Губернатор Решение Первый план более предпочтителен, если b1a1 + b2 < b2a1 + b1. Упорядочим здания по этому критерию. Так как N до 104 нам понадобится быстрая сортировка.
  • 15. Спасибо за внимание Ваши вопросы?