Entrada : uma ou duas cadeias de '0 e' 1 '. Se houver 2, eles serão separados por um espaço. Todas as cadeias de comprimento têm pelo menos 1.

Saída : Se uma string foi inserida, 2 são produzidas. Se 2 foram inseridos, 1 é emitido. As cadeias de saída pode ser o que quiser, mas se executar o seu programa com a entrada A dá-lhe B, em seguida, executá-lo com B deve dar uma (se introduzir 111 11dá 00000, em seguida, introduzir 00000deve dar 111 11).

Isso significa que, se você canalizar seu programa para si mesmo, deverá recuperar tudo o que inserir. Se o seu programa se chama foo, você pode testar isso da seguinte maneira:

>echo 101 101|foo|foo
101 101

Para impedir o uso de técnicas de força bruta, seu código deve ser capaz de executar com seqüências de 1000 dígitos em menos de 10 segundos. Minha solução python para isso leva menos de 1 segundo em seqüências de 10.000 dígitos, portanto isso não deve ser um problema.

O menor código vence.

Python, 183

A joia é armazenada em cache no disco.

x=raw_input()
try:d=eval(open('d').read())
except:d={'':'','1 ':'1 '}
t='1 '*not' 'in x
if x not in d:
 while t in d:t+=`(id(t)/9)%2`
 d[t]=x;d[x]=t
 open(*'dw').write(`d`)
print d[x]

edit: Opa, parece que essa não é a primeira resposta inteligente. O meu é consistente entre as corridas!

Python, 326

s=lambda i,l:bin(i)[2:].zfill(l)
f=lambda n:2**n*(n-3)+4
g=lambda n:2**n-2
i=raw_input()
if' 'in i:
 a,b=i.split();n=len(a+b);r=f(n)+int(a+b,2)*(n-1)+len(a)-1;l=1
 while g(l+1)<=r:l+=1
 print s(r-g(l),l)
else:
 n=len(i);r=g(n)+int(i,2);l=2
 while f(l+1)<=r:l+=1
 r-=f(l);p=r%(l-1)+1;w=s(r/(l-1),l);print w[:p],w[p:]

Exemplos de entradas / saídas:

     input | output
-----------+-----------
         0 | 0 0
       0 0 | 0
     10 10 | 10101
     10101 | 10 10
0000000000 | 101 0100
  101 0100 | 0000000000

Perl 5, 197 caracteres

sub n{'0'x$_[0].sprintf'%b',$_[1]}sub N{/0*(?=.)/;length$&,oct"0b$'"}$_=<>;print/ /?n map{($a,$b)=N;($a+$b)*($a+$b+1)/2+$b}split:"@{[map{$w=int((sqrt(8*$_+1)-1)/2);$y=$_-($w*$w+$w)/2;n$w-$y,$y}N]}"

Com algumas quebras de linha:

sub n{'0'x$_[0].sprintf'%b',$_[1]}
sub N{/0*(?=.)/;length$&,oct"0b$'"}
$_=<>;print/ /?n map{
  ($a,$b)=N;($a+$b)*($a+$b+1)/2+$b
}split:"@{[map{
  $w=int((sqrt(8*$_+1)-1)/2);$y=$_-($w*$w+$w)/2;n$w-$y,$y
}N]}"

Este programa opera compondo duas bijections:

• Um par de números naturais pode ser mapeado para uma cadeia binária convertendo um em um número de base 2 e o outro em zeros iniciais estranhos. né essa função e Né sua inversa (exceto que Nusa $_como parâmetro).

• Um par de números naturais pode ser mapeado para um único número natural usando a função de emparelhamento Cantor . O primeiro mapbloco é essa função e o segundo é o inverso.

Assim, duas cadeias binárias são divididas em quatro números, combinadas em dois números e, em seguida, combinadas em uma cadeia binária - ou vice-versa.

Testado em 100 entradas aleatórias de cada tipo com seqüências de caracteres de até 8 símbolos. Eu tenho encontrado muitas maneiras de tornar isso um pouco mais curto, mas vou parar e postar. Se houver espaço para otimizar ainda mais, provavelmente está nas expressões aritméticas.

Perl, 56 caracteres

adicionado +1 caractere para a -popção de linha de comando

$s.=1;$h{$h{$_}||=(split>1?$s:"$s $s").$/}=$_;$_=$h{$_}

Python, 394

Tenho certeza de que isso pode ser ainda melhor, mas esse monólito usa a Função de Emparelhamento Cantor e sua inversa.

import math
s=lambda n:n*(n+1)/2
p=lambda a:'0'*a[0]+bin(a[1])[2:]
q=lambda t:t.index('1')
B=raw_input().split()
def f(x,y):r=x+y+1;return s(r)-[y,x][r%2]-1
def g(z):r=int(math.ceil((2*(z+1)+1/4.)**(1/2.)-1/2.))-1;d=s(r+1)-z-1;return [(d,r-d),(r-d,d)][r%2]
if len(B)<2:a=[g(q(B[0])),g(int(B[0],2))];print p(a[0])+' '+p(a[1])
else:print p([f(q(B[0]),int(B[0],2)),f(q(B[1]),int(B[1],2))])

Explicação

Existe uma associação natural entre uma string binária e um par de números naturais: o primeiro número da imagem é o número de zeros à esquerda e o segundo é o valor inteiro do número binário. Sabendo que temos:

S ~ N^2

e com a joia do Cantor

N ~ N^2

Portanto:

S ~ N^2 ~ N^4 ~ S^2

S ~ S^2

Onde S é definido de todas as cadeias binárias. Esta solução implementa a bijeção entre S e S ^ 2.