eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

У цій задачі Вам пропонується розв'язок для задачі \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 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
20
Вихідні дані #1
20
00111111111111111111
00011111111111111111
10001111111111111111
11000111111111111111
11100011111111111111
11110001111111111111
11111000111111111111
11111100011111111111
11111110001111111111
11111111000111111111
11111111100011111111
11111111110001111111
11111111111000111111
11111111111100011111
11111111111110001111
11111111111111000111
11111111111111100011
11111111111111110001
11111111111111111000
11111111111111111100
Автор Сергій Копеліович
Джерело Зимова Школа, Харків 2011, День 5