Структура олимпиадной задачи, вырожденные примеры, файловый ввод-вывод

  • {o} — тема по Linux

  • <!> ­— необязательная тема

Домашнее задание

  • {i} — теоретическое задание

  • {*} — новая тема

  1. {i} Две книжки (есть тут):

    • Брудно А.Л., Каплан Л.И. Московские олимпиады по программированию. – М.: Наука, 1990. – 208 с.
    • Московские олимпиады по информатике / Под ред. Е.В. Андреевой, В.М. Гуровица и В.А. Матюхина. – М.: МЦНМО, 2006. – 256 с.
  2. Любопытная Варвара. Любопытная Варвара ходит по базару и повсюду суёт свой нос. Она заметила, что под прилавками продавцы прячут воздушные шары различной формы и расцветки, приготовленные для праздника весеннего равноденствия. Когда Варвара обнаруживает очередной шар, тот улетает высоко в небо, скрываясь из виду. Варвара знает, что больше половины шаров — одинаковые, закупленные на средства местного олигарха. Помоги Варваре узнать, какие шары закупил олигарх. Варвара может запомнить тип и количество нескольких виденных шаров, но не всех сразу.

    • Задание: решить задачу; определить, какая «именная» задача скрывается за занимательной формой.

      • Примечание: это не задача, а упражнение, поэтому решения и ответа на вопрос здесь публиковать не надо

  3. Реализовать генерацию непроходимого лабиринта путём параллельного прохода со входа и выхода
  4. Найти последовательность из N нулей и единиц, в которой никакой отрезок не повторяется три раза подряд. Напечатать НЕТ, если такой последовательности не существует.
    • Например, в искомой последовательности нигде не должны встречаться такие отрезки, как 000, или 101010, или 101101101.

      no_3.py

  5. {*} Задача о рюкзаке. Вор забрался в Оружейную палату и раскрыл свой рюкзак. Ему нужно набить его так, чтобы он не порвался, а суммарная стоимость украденного была максимальной. Итак, дан список пар вида стоимость_предмета, объём_предмета. Определить максимально дорогой набор предметов, суммарным объёмом не более N.

    • решить задачу пребором, убедиться в непригодности этого решения
    • почитать, как решать эту задачу методом динамического программирования


CategoryClass CategoryVmsh

LecturesVMSH/2010-12-15 (последним исправлял пользователь PavelSutyrin 2010-12-22 19:25:46)