Здравствуйте, извините за очередную оффтопную тему. Сегодня мне стало интересно, как много спортивных программистов смотрят Дом 2, и если такие есть(кроме меня :D), как вы считаете, искренние ли чувства у Андрея Черкасова к Анне Кручининой?

Здравствуйте!

Меня очень интересует, с помощью каких комбинаций (место на олимпиаде (olympiads.ru); экзамены) украинец может попасть в МФТИ(ФИВТ) и МГУ(ВМК)? И вообще, можно ли поступить в МГУ иностранцу?

Добрый день комьюнити) В Украине среди школьников проводится конкурс МАН, который заключается в написании научных работ, я придумал тему, и хотел бы узнать, будет ли это сильно баян... Пожалуйста, сильно не агртесь, т.к. это работа школьника. Собственно, работа (еще не написанная) будет посвящена структуре данных) Структура позволяет добавлять, находить и удалять элемент x в множестве S, за O(log(x)). Так же на множестве можно поддерживать все ассоциативные операции, такие как: min, max, gcd, xor и прочие (как в сете минимум)... Для этого, воспользуемся бинарным деревом (двоичный бор) и каждому ребру припишем 0 или 1, в зависимости от того левый это ребенок или правый. Предположим нам надо добавить число 116, тогда его двоичное представление 1110100, значит из корня мы идем вдоль ребер 0->0->1->0->1->1->1 и там ставим флаг, что такое число есть. Т.е. так будет выглядеть рекурсивный код:

class node
{
    node()
    {
        next[0] = next[1] = exist = 0;
    }
    node *next[2]; //левый и правый сын
    bool exist;
};

void includeElem(int addNum, node *current) //addNum - добавляемое число, current текущая вершина
{
    if (addNum == 0)
    {
        current->exist = 1;
        return;
    }    
    if (current->next[addNum & 1] == 0)
        current->next[addNum & 1] = new node();
    includeElem((addNum >> 1), current->next[addNum & 1]);
}

В силу того что структура не перестраивается, т.е. корню (и другим вершинам, в которые ведут ребра с пометкой 1) всегда будет соответствовать одно число (корню — 0), то можно ввести функцию на поддереве, как в дереве отрезков, т.е. собирать информацию с детей. Тогда если мы добавляем элемент, то значение этой функции может поменяться только на пути от добавляемой вершины, до корня, значит, когда мы будем возвращаться назад, то на всем пути нам просто надо будет обновить функцию f.

class node
{
    node()
    {
        next[0] = next[1] = exist = valueOfFunc = 0;
    }
    void update(int number) //число соответствующее этой вершине
    {
        **valueOfFunf = f(f(next[0]->valueOfFunf, next[0]->valueOfFunf), number); //тут еще надо проверить, существует ли вообще next[0/1], и если в эту вершину ведет ребро с пометкой нуль, тогда number хорошо бы поставить нейтральным элементом**
    }
    int valueOfFunc;
    node *next[2]; //левый и правый сын
    bool exist;
};

void includeElem(int addNum, node *current) //addNum - добавляемое число, current текущая вершина
{
    if (addNum == 0)
    {
        current->exist = 1;
        return;
    }    
    if (current->next[addNum & 1] == 0)
        current->next[addNum & 1] = new node();
    includeElem((addNum >> 1), current->next[addNum & 1]);
    **current->update();**
}

Так же памяти эта структура будет занимать O(n*log(maxNum)), где n — это количество элементов множества, а maxNum — это максимальное число в нем. Это не трудно заметить из того, что за одно добавление числа x мы добавляем O(log(x)), новых вершин, а т.к. добавлений n — то выходит итоговая асимптотика. Собственно, я бы хотел узнать, имеет ли эта тема на существовании в МАНе?