1. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление

Помогите кто сможет написать прогу на с++.

Тема в разделе "С и С++", создана пользователем ned, 21 дек 2005.

Статус темы:
Закрыта.
  1. ned

    ned Гость

    Репутация:
    0
    Помогите кто сможет написать прогу на с++.
    Задача следующего содержания: Вася положил на стол N выпуклых K-гранников и N различных типов наклеек, каждой по K штук . Кто-то наклеил наклейки на грани, по одной на грань. Расставить многогранники так, чтобы наклейка каждого типа была видна pовно K-1 раз.
    Всем откликнувшимся респект и уважуха, и естественно вознаграждение. Заранее спасибо.
     
  2. KmeT

    KmeT Гость

    Репутация:
    0
    Так как, не определенны условия видимости, примем вырожденный случай- не видна только грань, на котрой стоит многогранник.

    Условие не опеределяет количество наклеек каждого типа и не гарантирует что на каждом многограннике не может быть несколько наклеек одного типа.

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

    Далее проверяем только эти полученные коотдинаты на других типах и постепеноо отсеивам не подходящие.

    Найдеюсь данный флуд будет полезен, если бы не сессия, может быть и запостил исходник
     
  3. DAle

    DAle Гость

    Репутация:
    0
    <!--QuoteBegin-ned+21:12:2005, 16:45 -->
    <span class="vbquote">(ned @ 21:12:2005, 16:45 )</span><!--QuoteEBegin-->Помогите кто сможет написать прогу на с++.
    Задача следующего содержания: Вася положил на стол N выпуклых K-гранников и N различных типов наклеек, каждой по K штук . Кто-то наклеил наклейки на грани, по одной на грань. Расставить многогранники так, чтобы наклейка каждого типа была видна pовно K-1 раз.
    Всем откликнувшимся респект и уважуха, и естественно вознаграждение. Заранее спасибо.
    [snapback]28643" rel="nofollow" target="_blank[/snapback]​
    [/quote]

    Переформулируем задачу.
    ...Расставить многогранники таким образом, чтобы все многогранники стояли на гранях с наклейками различных типов.

    Построим двудольный граф. Первая доля графа - многогранники, вторая - типы наклеек. Если на многогранник i наклеена наклейка типа j, то строим ребро между вершиной i первой доли и вершиной j второй доли графа.
    Теперь находим совершенное паросочетание в построенном двудольном графе. То есть паросочетание мощности N. Его ребра и будут являться ответом задачи.

    Построение максимального паросочетания в двудольном графе задача стандартная и избитая, так что google в руки.
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей