В этой задаче Вам предлагается решение для задачи Клики.
Данное решение, естественно, не получает Accepted, но работает все же за время O(2^N) .
// i - текущая вершина, p - текущее множество вершин long long go( int i, long long p ) { if (p == 0) // если множество p пусто return 1; counter++; // время работы программы while (((p » i) 1) == 0) // лежит ли вершина i в множестве p i++; p ^= 1LL « i; // исключить вершину i из множества p if ((p c[i]) == p) // c[i] - множество вершин, соединенных // с вершиной i ребром return 2 * go(i, p); // p c[i] - пересечение множеств p и c[i] return go(i, p) + go(i, p c[i]); } counter = 0; // обнуляем время работы программы result = go(0, (1LL « n) - 1); // запускаемся от множества всех вершин
Ваша задача — построить тест, на котором это решение не уложится в Time Limit. То, сколько работает программа, определяется значением переменной counter.
Число N — количество вершин в графе, который Вам требуется построить.
Всего в задаче 2 теста.
Первый тест содержит N = 20. На нем переменная counter к концу работы программы должна быть не меньше 5000.
Второй тест содержит N = 40. На нем переменная counter к концу работы программы должна быть не меньше 50000000.
Выведите тест. Тест должен соответствовать формату входных данных задачи Клики.