====== JFiZO - Zadanie 09.113 ======

===== Dobre rozwiązanie =====
$f(x) = \cases{
n &
\mathrm{jeśli} \; 2|n \wedge 2^n = x \cr
2\cdot(x-\left|\{k: 2|k \wedge 2^k < x\}\right|)+1 & \mathrm{w} \; \mathrm{p.p.}
}$

$f$ jest obliczalna w wielomianowym czasie, natomiast $f^{-1}$ nie jest.

===== Złe rozwiązanie =====

$f: \{0,1\}^* \rightarrow \{0,1\}^*$ - obliczalna w wielomianowym czasie. Czy $f^{-1}$ obliczalna w wielomianowym czasie.

Ponumerujmy ciagi zerojedynkowe.

Niech $n = f(m)$. Wtedy $f^{-1}(n)$ obliczymy w nastepujacy sposob:
  for (i = 0; ;i++) {
    if (f(i) == n)
      return i;
  }
Funkcja ta oblicza sie w czasie m*zlozonosc_f. BULLSHIT