Тест до задачі про Кліки#1879

Тест до задачі про Кліки

1 секунда

64 мегабайти

Середня

У цьому завданні вам надане розв'язання задачі Кліки.

Це розв'язання не отримує статусу Accepted, проте працює з часовою складністю $O (2^{N})$ 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$ N = 20. У цьому тесті змінна counter наприкінці виконання програми має бути не меншою за $5000$ .

У другому тесті $N = 40$ N = 40. У цьому тесті змінна counter наприкінці виконання програми має бути не меншою за $50000000$ .

Вихідні дані

Виведіть тест. Тест має відповідати формату вхідних даних задачі Кліки.

Приклади

Приклад 1