03月29, 2014

# URAL 2004 Scientists from Spilkovo (De Bruijn序列)

http://acm.timus.ru/problem.aspx?space=1&num=2004

``````2004. Scientists from Spilkovo
Time limit: 0.5 second
Memory limit: 64 MB
Misha and Dima are promising young scientists. They make incredible discoveries every day together with their colleagues in the Spilkovo innovative center. Now Misha and Dima are studying the properties of an amazing function F which is written as follows.
C++:
int F(int x, int n)
{
return (((x & ((1 << (n / 2)) - 1)) << ((n + 1) / 2)) | (x >> (n / 2)));
}
Pascal:
function F(x, n: integer): integer;
begin
F := (((x and ((1 shl (n div 2)) - 1)) shl ((n + 1) div 2)) or (x shr (n div 2)));
end;
The friends want to perform the following computational experiment.

All integers from 0 to 2n − 1 are written.
Each integer x is replaced by F(x, n).
Each integer obtained after step 2 is written as a binary string of length n (if the integer has less than n bits, some leading zeroes are added; if the integer has more than n bits, only last n bits are written).
The result of the experiment is a binary string of minimum length, that contains all the strings obtained after step 3 as its substrings.
If you can perform this experiment, maybe you are able to work in Spilkovo too!
Input
The only line contains an integer n (1 ≤ n ≤ 20).
Output
Output the required binary string. If there are several optimal solutions, you may output any of them.
Sample
input    output
1
10
Problem Author: Ilya Kuchumov
Problem Source: Ural Regional School Programming Contest 2013
Tags: none  (
hide tags for unsolved problems
)
``````

``````def de_bruijn(k, n):
"""
De Bruijn sequence for alphabet size k
and subsequences of length n.
"""
a =  * k * n
sequence = []
def db(t, p):
if t > n:
if n % p == 0:
for j in range(1, p + 1):
sequence.append(a[j])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return sequence

print de_bruijn(2, 3)
``````

``````#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<iomanip>
#include<bitset>
#include<sstream>
#include<fstream>
#define debug puts
#define pi (acos(-1.0))
#define eps (1e-8)
#define inf (1<<30)
using namespace std;
//k为元素值范围，n为串长度
void db(int n,int k,vector<int> &v,int a[],int t=1,int p=1)
{
if (t>n)
{
if (n%p==0)
for (int i=1; i<=p; i++)
v.push_back(a[i]);
}
else
{
a[t]=a[t-p];
db(n,k,v,a,t+1,p);
for (int i=a[t-p]+1; i<k; i++)
{
a[t]=i;
db(n,k,v,a,t+1,t);
}
}
}
vector<int> de_bruijn(int n,int k)
{
vector<int> v;
int a[n*k];
memset(a,0,sizeof(a));
db(n,k,v,a);
return v;
}
int main()
{
int n;
cin>>n;
vector<int> v=de_bruijn(n,2);
for (int i=0; i<v.size(); i++)
cout<<v[i];
for (int i=0; i<n-1; i++)
cout<<v[i];
return 0;
}
``````

UDPATE: 仔细学习图论之后才对这个问题有了更深刻的认识，在《图论与代数结构》（`ISBN 9787302018148`）中有个简单的例题，在此一并附上。   -- EOF --