Тест до задачі про Кліки
У цій задачі Вам пропонується розв'язок для задачі Кліки.
Даний розв'язок, звичайно, не отримує 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.
Вихідні дані
Виведіть тест. Тест повинен відповідати формату вхідних даних задачі Кліки.