• Авторизация
Дневник Мэн_в_чёрном Лента друзей - Дневник - Полная версия


Девочка Таня наряжает новогоднюю ёлку, задачка 27-12-2005 11:13 к комментариям - к полной версии - понравилось!


После того, как Дед Мороз, будучи в преступном сговоре с программистом Ромой, кинул девочку Таню на заклинание, бедное дитя, дабы утешиться, решило нарядить новогоднюю ёлку. Да не просто так, а чтобы красивее, чем у Деда Мороза и программиста Ромы вместе взятых
У ёлки 25 мест куда можно повесить игрушку. Чем это место выше и ближе к середине, тем красивее. Есть так же 3 вида игрушек по 8 штук каждого вида.
Красивость игрушки на определённом месте определяется как произведение коэффициента красивости места (от 1 до 9) на коэффициент красивости игрушки (1, 3 или 5), то есть может быть от 1 до 45.
Красивость яруса (они разными тонами покрашены) определяется как сумма красивостей всех игрушек на ярусе. Верхняя точка с коэффициентом 9 не считается за ярус, и должен быть пропущен - Таня нашла звездочку туда. Там где игрушки нет, засчитывается 0 красивости.
Красивость ёлки это сумма красивостей всех ярусов.

Естественно надо нарядить ёлку, причём:
1. Все ярусы были бы одинаково красивы.
2. Ёлка должна быть симметрично наряжена.
3. Елка в целом должна быть максимально красива.
4. верхний ярус не пропускается, в счет не входит.

А вот и ёлочка:
[544x443]

Помогите этой шалаве Таньке нарядить ее хренову елку!
Помогите милой девочке Тане решить ее задачу.

За решение посчитаю ответ с расстановкой или того лучше задачу в терминах линейного программирования (целевая функция + ограничения).
вверх^ к полной версии понравилось! в evernote
Комментарии (7):
Cuthbert 27-12-2005-18:11 удалить
По-моему это невозможно .
Условие : все ярусы должны быть одинаково красивыми ....
игрушки бывают с коэффициентами 1, 3, 5 .
если пытаться уравнивать первые два яруса (9 и 7, 8, 7) , то должно получится
9 * x = 7 * y + 8 * z + 7 * y (два y_а из условия симметричности) , где x , y, z - из множества { 1, 3, 5 }
9 * x = 14 * y + 8 * z
то есть слева нечетное число , справа - четное .
-----------------
может я условие не так понял ?
Обратиться - Ответить - К полной версии
Мэн_в_чёрном 27-12-2005-18:14 удалить
Cuthbert, ты правильно понял, это свойство выяснилось чуть позже, на верхнем ярусе будет просто звездочка, которая в учет не войдет.
Обратиться - Ответить - К полной версии
Cuthbert 28-12-2005-13:34 удалить
Тут можно симплекс метод замутить , но переменных многовато , лень . Поэтому на пальцах :

Елку переделаем , используя симметричность :

[ 8 x21 ] [ 14 x22 ]
[ 7 x31 ] [ 12 x32 ] [ 10 x33 ]
[ 6 x41 ] [ 10 x42 ] [ 8 x43 ] [ 6 x44 ]
[ 5 x51 ] [ 8 x52 ] [ 6 x53 ] [ 4 x54 ] [ 2 x55 ]

Тут все понятно . Оторвали правые ветки и приклеили к левым , удвоив их коэффициент . В каждом слоте указана переменная (x21 - x55) . Каждая такая переменная принимает значение из { 0, 1, 3, 5 } . Максимизируем целевую ф-цию

z = 8 * x21 + 14 * x22 +
+ 7 * x31 + 12 * x32 + 10 * x33 +
+ 6 * x41 + 10 * x42 + 8 * x43 + 6 * x44 +
+ 5 * x51 + 8 * x52 + 6 * x53 + 4 * x54 + 2 * x55

Исследуем красоту ярусов (каждое ур-ние заключаю в { } чтоб друг на друга не наезжали) :

{ 8 * x21 + 14 * x22 = 7 * x31 + 12 * x32 + 10 * x33 }
{ 7 * x31 + 12 * x32 + 10 * x33 = 6 * x41 + 10 * x42 + 8 * x43 + 6 * x44 }
{ 6 * x41 + 10 * x42 + 8 * x43 + 6 * x44 = 5 * x51 + 8 * x52 + 6 * x53 + 4 * x54 + 2 * x55 }

1-й = 2-й :

8 * x21 + 14 * x22 = 7 * x31 + 12 * x32 + 10 * x33

Получаем для сохранения четности x31 = 0 . Аналогично x51 = 0 . Перепишем систему (выкидываем нулевые переменные и делим на 2) :

{ 4 * x21 + 7 * x22 = 6 * x32 + 5 * x33 }
{ 6 * x32 + 5 * x33 = 3 * x41 + 5 * x42 + 4 * x43 + 3 * x44 }
{ 3 * x41 + 5 * x42 + 4 * x43 + 3 * x44 = 4 * x52 + 3 * x53 + 2 * x54 + x55 }

Теперь с четностью все в порядке . Берем первое уравнение , не ленимся и решаем его в числах из { 0, 1, 3, 5 } перебором .

4 * a + 7 * b = 6 * c + 5 * d

0 0 0 0
4 + 7 = 6 + 5
12 21 18 15
20 35 30 25

{ 0, 4, 12, 21, 7, 11, 19, 27, 21, 25, 33, 41, 35, 39, 47, 55 } = { 0, 6, 18, 30, 5, 11, 23, 35, 15, 21, 33, 45, 25, 31, 43, 55 }

Таким образом в качестве сумм слева и справа могут выступать числа : 0, 11, 21, 25, 33, 35, 55 .

Теперь берем нижний ярус :

4 * x52 + 3 * x53 + 2 * x54 + x55

Если все игрушки нижнего яруса взять по 5 , то его красота будет равна (4 + 3 + 2 + 1) * 5 = 50 , то есть с красотой ярусов по 55 ничего не получится в любом случае . Тогда попробуем красоту 35 .

1-й ярус :

4 * 0 + 7 * 5 = 35 (игрушки : 1 - 0 , 3 - 0 , 5 - 2)

2-й ярус :

6 * 5 + 5 * 1 = 35 (игрушки : 1 - 2 , 3 - 0 , 5 - 2)

3-й ярус :

3 * 0 + 5 * 3 + 4 * 5 + 3 * 0 = 35 (игрушки : 1 - 0 , 3 - 2, 5 - 2)

4-й ярус :

4 * 5 + 3 * 3 + 2 * 3 + 0 = 35 (игрушки : 1 - 0 , 3 - 4 , 5 - 2)

Всего израсходовано игрушек : 1 - 2 , 3 - 6 , 5 - 8

Теперь вспомним , что имели дело со сведенной системой и нарисуем все дерево в исходном виде :


                []

            [5] [0] [5]

        [1] [5] [0] [5] [1]

    [0] [5] [3] [0] [3] [5] [0]

[0] [3] [3] [5] [0] [5] [3] [3] [0]


Игрушки : 1 - 2 , 3 - 6 , 5 - 8 .
Красота яруса : 70 .
Красота елки : 280 .

Похоже , эта шалава милая девочка Таня сделала Деда Мороза )
Обратиться - Ответить - К полной версии
Мэн_в_чёрном 28-12-2005-18:00 удалить
Cuthbert, крут чувак! ;)
только как ты сказал симплекс метод не замутишь - задача целочисленная, хотя решается методом ветвей и границ в которой как подзадача запускается симплекс метод ;)
или следует доказать что матрица ограничений совершенно унимодулярна

а у меня была постановка такая для ЦЗЛП:


max(4x0)

2x1 + 4x2 +  6x3  +  8x4  + 5x5  - x0 = 0

      6x6 +  8x7  + 10x8  + 6x9  - x0 = 0

            10x10 + 12x11 + 7x12 - x0 = 0

                    14x13 + 8x14 - x0 = 0

2x1 + 2x2 + 2x3  + 2x4  + x5  +

      2x6 + 2x7  + 2x8  + x9  +

            2x10 + 2x11 + x12 +

                   2x13 + x14 <= 8(1+3+5)

x1..x14 in {0,1,3,5}, x0 >= 0

x0 - красивость яруса
х1..х14 - места. нумерация мест снизу вверх скраю до центра (сииметричную часть не считаем)
Обратиться - Ответить - К полной версии
Мэн_в_чёрном 28-12-2005-18:22 удалить
народ программу написал ;)


#include 

#include 

#include 

#include 

#include 



using namespace std;



const int NBRANCHES = 4;

const int MAX_BRANCH_LENGTH = 5;

const int BRANCH_LENGTH[NBRANCHES] = {2,3,4,5};

const int TREE[NBRANCHES][MAX_BRANCH_LENGTH] = 

{

    {7,8},

    {5,6,7},

    {3,4,5,6},

    {1,2,3,4,5}

};

const int BALL_TYPES_CNT = 3;

const int BALLS_COEF[BALL_TYPES_CNT+1] = {1,3,5,0}; 

const int BALLS_CNT = 8;

const int MAX_BRANCH_LEN = 5;

typedef vector > vbranches;

typedef map branches_map;







vector br_set(NBRANCHES);





void add_branch(int nbranch, const vector& branch)

{

    int sum = 0;

    for (int i = 0; i < BRANCH_LENGTH[nbranch]-1; ++i)

    {

        sum += BALLS_COEF[branch[i]] * TREE[nbranch][i];    

    }

    sum *= 2;

    sum += BALLS_COEF[branch[BRANCH_LENGTH[nbranch]-1]] * TREE[nbranch][BRANCH_LENGTH[nbranch]-1];    

    br_set[nbranch][sum].push_back(branch); 

}



void gen_branches(int nbranch, int pos, vector& branch)

{

    for (int i = 0; i < BALL_TYPES_CNT+1; ++i)

    {

        branch[pos] = i;

        if (pos < BRANCH_LENGTH[nbranch]-1)

        {

            gen_branches(nbranch, pos+1, branch);

        }

        else

        {

            add_branch(nbranch, branch);

        }

    }

}



bool correct_tree(int branchsum, const vector& branch)

{

    vector balls_cnt(BALL_TYPES_CNT+1,0);

    for (int i = 0; i < NBRANCHES; ++i)

    {

        for (int j = 0; j < BRANCH_LENGTH[i]; ++j)

        {

            int type = br_set[i][branchsum][branch[i]][j];

            int k = balls_cnt[type] += ((j < BRANCH_LENGTH[i]-1) ? 2 : 1);

            if (k > BALLS_CNT && type < BALL_TYPES_CNT) return false;

        }

    }

    return true;    

}



void output_tree(int branchsum, const vector& answer)

{

    cout << "\ntree beauty = " << branchsum*NBRANCHES << '\n';

    for (int i = 0; i < NBRANCHES; ++i)

    {

        for (int j = 0; j < BRANCH_LENGTH[i]; ++j)

        {

            cout << BALLS_COEF[br_set[i][branchsum][answer[i]][j]] << " ";

        }

        cout << '\n';

    }

    cout << endl;

}



void create_tree(int branchsum, int nbranch, vector& answer, bool& found)

{

    typedef vbranches::iterator iter;

    int pos = 0;

    for (iter i = br_set[nbranch][branchsum].begin(), 

            end = br_set[nbranch][branchsum].end(); i != end; ++i, ++pos)

    {

        answer[nbranch] = pos;

        if (nbranch < NBRANCHES-1)

        {

            create_tree(branchsum, nbranch+1, answer, found);

            if (found) return;

        }

        else if (correct_tree(branchsum, answer))

        {

            output_tree(branchsum, answer);

            //found = true;

            //return;

        }

    }

}



int main()

{

    for (int i = 0; i < NBRANCHES; ++i)

    {

        vector branch(MAX_BRANCH_LEN);

        gen_branches(i, 0, branch);

    }

    for (branches_map::iterator mi = br_set[0].begin(); 

         mi != br_set[0].end(); ++mi)

    {

        bool found = false;

        vector answer(NBRANCHES);

        create_tree(mi->first, 0, answer, found);

        cout << mi->first << endl;

    }



    return 0;

}
Обратиться - Ответить - К полной версии
Мэн_в_чёрном 28-12-2005-18:23 удалить 


        [0]

      [5,0,5]

    [1,5,0,5,1]

  [0,5,3,0,3,5,0]

[0,3,3,5,0,5,3,3,0]



       [0]

     [5,0,5]

   [1,5,0,5,1]

  [1,1,5,1,5,1,1]

[0,3,3,5,0,5,3,3,0]



        [0]

      [5,0,5]

    [1,5,0,5,1]

  [1,3,1,5,1,3,1]

[0,3,3,5,0,5,3,3,0]



        [0]

      [5,0,5]

    [1,5,0,5,1]

  [3,3,1,3,1,3,3]

[0,0,5,5,0,5,5,0,0]



        [0]

      [5,0,5]

    [1,5,0,5,1]

  [5,3,1,1,1,3,5]

[0,3,3,5,0,5,3,3,0]
Обратиться - Ответить - К полной версии


Комментарии (7): вверх^

Вы сейчас не можете прокомментировать это сообщение.

Дневник Девочка Таня наряжает новогоднюю ёлку, задачка | Мэн_в_чёрном - Мэн_в_чёрном | Лента друзей Мэн_в_чёрном / Полная версия Добавить в друзья Страницы: раньше»