Еще интересных задачек. С решениями.

Оригинал.

Есть лошади, которые бегают с разной скоростью и никогда не устают. Лошади могут учавствовать в забегах, в одном забеге может участвовать не более N лошадей. Результатом забега является очередность, в которой лошади дошли до финиша, то есть на выходе - список, на каком месте была какая лошадь в забеге.
Всего лошадей N^2.
Спрашивается - за какое минимальное количество забегов можно найти M лучших их них?

Разбиваем на N групп. В каждой проводим забег. Итого N забегов. Берем из каждой группы победителя. Проводим среди них забег. Победитель есть абсолютный победитель. Запоминаем, победителя удаляем, добавляем второго из его группы. Проводим еще один забег...короче M+N

Есть односвязный список, у которого в каждом элементе есть еще один указатель на некоторый элемент этого списка. То есть, кроме next в ноде есть еще один мембер, который указывает на любой элемент списка. Может сам на себя, могут несколько таких указателей указывать на один элемент, как угодно. Хочется создать копию этого списка, разумеется, со скопированными ссылками в элементах. За линейное время и без дополнительной памяти, кроме как на саму копию.

Код (всякие мелкие очевидные фукнции я убрал, rlist->n - следующий элемент, rlist->r - случайный элемент, предполагается что в исходном списки r!=0 никогда)

rlist* rrcopy(rlist* base_head)

{

    rlist* copy_head = clone_rlist(base_head);

    rlist* b,*c,*t;

 

    for(b=base_head,c=copy_head;b;b=b->n){

        t=c->n;

        c->r=b->r;

        c->n=b->r;

        b->r=c;

        c=t;

    }

 

    for(b=base_head;b;b=b->n){

        c=b->r;

        c->r=c->n->r;

    }

 

    for(b=base_head;b;b=b->n){

        c=b->r;

        t=c->n;

        c->n=b->n?b->n->r:0;

        b->r=t;

    }

    return copy_head;

}

Даны три массива целых положительных чисел длиной N.
Нужно выбрать из каждого из них по одному числу так, чтобы сумма равнялась некоторому данному C.
С константными затратами памяти и сложностью O(N^2).

Хинт - если два массива отсортировать то для двух таких массивов задачу можно решить за O(N). Соответственно вместе с третьим получается O(N^2)
Если массивы сортировать нельзя - не знаю :)