eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

В этой задаче Вам предлагается решение для задачи Клики.

Данное решение, естественно, не получает Accepted, но работает все же за время 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.

Input data

Число N — количество вершин в графе, который Вам требуется построить.

Всего в задаче 2 теста.

Первый тест содержит N = 20. На нем переменная counter к концу работы программы должна быть не меньше 5000.

Второй тест содержит N = 40. На нем переменная counter к концу работы программы должна быть не меньше 50000000.

Output data

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

Examples

Input example #1
20
Output example #1
20
00111111111111111111
00011111111111111111
10001111111111111111
11000111111111111111
11100011111111111111
11110001111111111111
11111000111111111111
11111100011111111111
11111110001111111111
11111111000111111111
11111111100011111111
11111111110001111111
11111111111000111111
11111111111100011111
11111111111110001111
11111111111111000111
11111111111111100011
11111111111111110001
11111111111111111000
11111111111111111100
Author Sergey Kopeliovich
Source Winter School, Kharkov, 2011, Day 5