e-olymp
Məsələlər

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

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

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

Данное решение, естественно, не получает Accepted, но работает все же за время O(2N) .

// 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.

Входные данные

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

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

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

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

Выходные данные

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


Пример входных данных
Пример выходных данных

20

20
01100010101101010001
10010010111010001111
10000010011111000001
01000000000000100100
00000011100111001011
00000000011011011101
11101001101011010101
00001010010000000101
11001010000101110110
01100101001001010010
11100110010000010011
10101000100001100001
01101110000000101110
10101110110100100000
00010000100111010101
10000110111000101100
01001100000010010110
01010111100010111011
01001000111010001100
11101111001100100100

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
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
Müəllif Сергей Копелиович
Mənbə Зимняя школа, Харьков 2011, День 5