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