Антитест

Вам дана реализация декартова дерева. Ошибок тут нет, не волнуйтесь. Есть одна особенность: вместо y-ков в операции Merge используется rnd.next(2) (функция возвращает случайное число от 0 до 1). Утверждается, что построенное таким образом дерево может иметь слишком большую глубину. Ваша задача — найти последовательность из не более чем 3000 операций, создающую дерево глубины не менее 1000 (дерево из одной вершины имеет глубину 1).

1 typede f struct tree * ptree;

2 struct tree { ptree l, r; i n t x; };

3 ptree root, a, b, c;

4

5 // comment: l = {y < x}, r = {y >= x}

6 void Split( ptree t, ptree l, ptree r, int x ) {

7 if (t == 0) l = r = 0;

8 else if (t->x >= x) Split(t->l, l, t->l, x), r = t;

9 else Split(t->r, t->r, r, x), l = t;

10 }

11 void Merge( ptree t, ptree l, ptree r ) {

12 if (l == 0) t = r;

13 else if (r == 0) t = l;

14 else if (rnd.next(2)) t = l, Merge(t->r, t->r, r);

15 else t = r, Merge(t->l, l, t->l);

16 }

17 void Add( i n t x ) {

18 b = new tree(x),

19 Split(root, a, c, x);

20 Merge(a, a, b);

21 Merge(root, a, c);

22 }

23 void Del( i n t x ) {

24 Split(root, a, b, x);

25 Split(b, b, c, x + 1);

26 Merge(root, a, c);

27 }

Входные данные

Вам предоставлен абсолютно пустой файл. Дерево изначально также пусто.

Последовательность операций вида ADD x и DEL x.

ADD x вызывает функцию Add(x) (см. реализацию)

DEL x вызывает функцию Del(x) (см. реализацию)

Примеры

Примечание

В чекере используется Random не зависящий от времени. Т.е. одинаковые решения всегда получают одинаковый результат. Если вы получили PE, ваш вывод не является корректной последовательностью из не более чем 3000операций. Если вы получили WA, последовательность операций корректна, а получившееся дерево имеет глубину меньше 1000.