Тест к задаче про Клики
Тест к задаче про Клики
В этой задаче Вам предлагается решение для задачи Клики.
Данное решение, естественно, не получает 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.
Input data
Число N — количество вершин в графе, который Вам требуется построить.
Всего в задаче 2 теста.
Первый тест содержит N = 20. На нем переменная counter к концу работы программы должна быть не меньше 5000.
Второй тест содержит N = 40. На нем переменная counter к концу работы программы должна быть не меньше 50000000.
Output data
Выведите тест. Тест должен соответствовать формату входных данных задачи Клики.
Examples
20
20 00111111111111111111 00011111111111111111 10001111111111111111 11000111111111111111 11100011111111111111 11110001111111111111 11111000111111111111 11111100011111111111 11111110001111111111 11111111000111111111 11111111100011111111 11111111110001111111 11111111111000111111 11111111111100011111 11111111111110001111 11111111111111000111 11111111111111100011 11111111111111110001 11111111111111111000 11111111111111111100