Задачі
Тест до задачі про Кліки
Тест до задачі про Кліки
У цій задачі Вам пропонується розв'язок для задачі \href{/problems/1880}{Кліки}.
Даний розв'язок, звичайно, не отримує Accepted, але працює все ж за час \textbf{O}(\textbf{2^N}) .
// i - поточна вершина, p - поточна множина вершин \textit{\textbf{long long go( int i, long long p ) \{ if (p == 0)}} // якщо множина p порожня \textit{\textbf{return 1;}} \textit{\textbf{counter++;}} // час роботи програми \textit{\textbf{while (((p >> i) & 1) == 0)}} // чи лежить вершина i у множині p \textit{\textbf{ i++;}} \textbf{p ^= 1LL << i;} // виключити вершину i з множини p \textit{\textbf{if ((p & c\[i\]) == p)}} // c\[i\] - множина вершин, з'єднаних // з вершиною i ребром \textbf{return 2 * go(i, p);} // p & c\[i\] - перетин множин p і c\[i\] \textbf{return go(i, p) + go(i, p & c\[i\]); } \} \textit{\textbf{counter = 0;}} // обнуляємо час роботи програми \textit{\textbf{result = go(0, (1LL << n) - 1);}} // запускаємось від множини усіх вершин
Ваша задача --- скласти тест, на якому цей розв'язок не вкладеться у \textit{Time Limit}. Те, скільки працює програма, визначається значенням змінної \textit{counter}.
\InputFile
Число \textbf{N} --- кількість вершин у графі, який Вам потрібно побудувати.
Всього у задачі \textbf{2} тести.
Перший тест містить \textbf{N = 20}. На ньому змінна \textit{counter} на кінець роботи програми повинна бути не менша \textbf{5000}.
Другий тест містить \textbf{N = 40}. На ньому змінна \textit{counter} на кінець роботи програми повинна бути не менша \textbf{50000000}.
\OutputFile
Виведіть тест. Тест повинен відповідати формату вхідних даних задачі \href{/problems/1880}{Кліки}.
Вхідні дані #1
20
Вихідні дані #1
20 00111111111111111111 00011111111111111111 10001111111111111111 11000111111111111111 11100011111111111111 11110001111111111111 11111000111111111111 11111100011111111111 11111110001111111111 11111111000111111111 11111111100011111111 11111111110001111111 11111111111000111111 11111111111100011111 11111111111110001111 11111111111111000111 11111111111111100011 11111111111111110001 11111111111111111000 11111111111111111100