Məsələlər
Тест к задаче про Клики
Тест к задаче про Клики
В этой задаче Вам предлагается решение для задачи \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}{Клики}.
Giriş verilənləri #1
20
Çıxış verilənləri #1
20 00111111111111111111 00011111111111111111 10001111111111111111 11000111111111111111 11100011111111111111 11110001111111111111 11111000111111111111 11111100011111111111 11111110001111111111 11111111000111111111 11111111100011111111 11111111110001111111 11111111111000111111 11111111111100011111 11111111111110001111 11111111111111000111 11111111111111100011 11111111111111110001 11111111111111111000 11111111111111111100