ݺߣ

ݺߣShare a Scribd company logo

Разбор задач

•Download as PPT, PDF•
•
M
Mikhail Kormyshov

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

1 of 17
Download to read offline
Разбор задач 1 тура школьного этапа Кормышов Михаил http://krasprog.ru
Задача А. Хоккей Условие Сколько существует вариантов распределения комплекта медалей? Ограничения N < 104 + 1
Задача А. Хоккей Решение Золотые медали могла получить любая из N команд. Серебряные – любая из оставшихся, то есть N-1 вариант. Бронзовые – N-2 команды. Итого: N*(N-1)*(N-2)
Задача А. Хоккей Особые случаи При N = 1 ответ 1 При N = 2 ответ 2
Задача В. Игра со спичками Условие Можно брать одну, две или тысячу спичек. Выигрывает последний. Кто выиграет при N спичках? Ограничения N < 104 + 1
Задача В. Игра со спичками Идея решения Воспользуемся теорией игр. Будем отмечать “+” выигрышные состояния, а “-” - проигрышные. Состояние с 0 спичек является для игрока проигрышным, так как его соперник уже выиграл на прошлом ходе, забрав последние спички.
Задача В. Игра со спичками Отмечаем состояние знаком “+”, если существует хотя бы один ход, ведущий в состояние “-”. Так как он заставит противника капитулировать. В противном случае отмечаем состояние знаком “-”.
Задача В. Игра со спичками 0 1 2 3 4 5 6 7 8 9 10 - + + - + + - + + - + Учитывая ограничения, можно реализовать этот алгоритм. Но нетрудно заметить закономерность, что в состояниях, кратных 3, стоит “-”. Обязательно необходимо проверить её и для больших чисел, когда можно будет брать по 1000 спичек.
Задача В. Игра со спичками Решение cin >> n; cout << (n%3 ? 1 : 2);
Задача С. Счастливые числа Условие Найти количество чисел, состоящих из 4 и 7, не превосходящих N. Ограничение N < 1032 + 1
Задача С. Счастливые числа Идея решения Динамика по цифрам числа, начиная с младших разрядов. Будем считать количество счастливых чисел, если использовано ровно j младших разрядов.
Задача С. Счастливые числа Пусть очередная цифра = Cj, ответ = Rj. Тогда: Cj < 4, то Rj = 0 Cj = 4, то Rj = Rj-1 Cj > 4 and Cj < 7, то Rj = 2j-1 Cj = 7, то Rj = Rj-1 + 2j-1 Cj > 7, то Rj = 2j
Задача D. Перетягивание каната Условие Дан граф из N вершин. Разделить вершины на две группы, чтобы количество рёбер между вершинами одной группы было максимально. Ограничение N < 25
Задача D. Перетягивание каната Идея решения Учитывая сильные ограничения на N. Решать задачу можно перебором всех вариантов. Всего количество вариантов = 2N. Это укладывается в ограничения, но для каждого из них необходимо посчитать сплочённость, итого получаем O(N2 2N)
Задача D. Перетягивание каната Оптимизация Пересчёт сплочённости можно выполнять за O(N), если перебор вести в порядке кодов Грея. Это пройдёт на хорошем сервере, но только не на acmp.
Задача D. Перетягивание каната Решение Для полного решения воспользуемся рекурсивным перебором с отсечением. void rec(int a, int k); где a – номер текущей вершины, k – количество человек в группе.
Спасибо за внимание Ваши вопросы?

More Related Content

Разбор задач

  • 1. Разбор задач 1 тура школьного этапа Кормышов Михаил http://krasprog.ru
  • 2. Задача А. Хоккей Условие Сколько существует вариантов распределения комплекта медалей? Ограничения N < 104 + 1
  • 3. Задача А. Хоккей Решение Золотые медали могла получить любая из N команд. Серебряные – любая из оставшихся, то есть N-1 вариант. Бронзовые – N-2 команды. Итого: N*(N-1)*(N-2)
  • 4. Задача А. Хоккей Особые случаи При N = 1 ответ 1 При N = 2 ответ 2
  • 5. Задача В. Игра со спичками Условие Можно брать одну, две или тысячу спичек. Выигрывает последний. Кто выиграет при N спичках? Ограничения N < 104 + 1
  • 6. Задача В. Игра со спичками Идея решения Воспользуемся теорией игр. Будем отмечать “+” выигрышные состояния, а “-” - проигрышные. Состояние с 0 спичек является для игрока проигрышным, так как его соперник уже выиграл на прошлом ходе, забрав последние спички.
  • 7. Задача В. Игра со спичками Отмечаем состояние знаком “+”, если существует хотя бы один ход, ведущий в состояние “-”. Так как он заставит противника капитулировать. В противном случае отмечаем состояние знаком “-”.
  • 8. Задача В. Игра со спичками 0 1 2 3 4 5 6 7 8 9 10 - + + - + + - + + - + Учитывая ограничения, можно реализовать этот алгоритм. Но нетрудно заметить закономерность, что в состояниях, кратных 3, стоит “-”. Обязательно необходимо проверить её и для больших чисел, когда можно будет брать по 1000 спичек.
  • 9. Задача В. Игра со спичками Решение cin >> n; cout << (n%3 ? 1 : 2);
  • 10. Задача С. Счастливые числа Условие Найти количество чисел, состоящих из 4 и 7, не превосходящих N. Ограничение N < 1032 + 1
  • 11. Задача С. Счастливые числа Идея решения Динамика по цифрам числа, начиная с младших разрядов. Будем считать количество счастливых чисел, если использовано ровно j младших разрядов.
  • 12. Задача С. Счастливые числа Пусть очередная цифра = Cj, ответ = Rj. Тогда: Cj < 4, то Rj = 0 Cj = 4, то Rj = Rj-1 Cj > 4 and Cj < 7, то Rj = 2j-1 Cj = 7, то Rj = Rj-1 + 2j-1 Cj > 7, то Rj = 2j
  • 13. Задача D. Перетягивание каната Условие Дан граф из N вершин. Разделить вершины на две группы, чтобы количество рёбер между вершинами одной группы было максимально. Ограничение N < 25
  • 14. Задача D. Перетягивание каната Идея решения Учитывая сильные ограничения на N. Решать задачу можно перебором всех вариантов. Всего количество вариантов = 2N. Это укладывается в ограничения, но для каждого из них необходимо посчитать сплочённость, итого получаем O(N2 2N)
  • 15. Задача D. Перетягивание каната Оптимизация Пересчёт сплочённости можно выполнять за O(N), если перебор вести в порядке кодов Грея. Это пройдёт на хорошем сервере, но только не на acmp.
  • 16. Задача D. Перетягивание каната Решение Для полного решения воспользуемся рекурсивным перебором с отсечением. void rec(int a, int k); где a – номер текущей вершины, k – количество человек в группе.
  • 17. Спасибо за внимание Ваши вопросы?