h1(#kxorbonacci). 'Solutia':algoritmiada-2022/runda-1/solutii/kxorbonacci problemei 'Kxorbonacci':problema/kxorbonacci

h1(#kxorbonacci). 'Soluţia':algoritmiada-2022/runda-1/solutii/kxorbonacci problemei 'Kxorbonacci':problema/kxorbonacci

Observăm că un şir kxorbonacci generat de ( $v{~1~}$, $v{~2~}$, ..., $v{~n~}$ ) este periodic cu perioada $n + 1$. Deasemenea suma xor a orcăror $n + 1$ elemente alăturate este $0$. Astfel este suficient să găsim perioada minima $P$ a şirului primit ca input şi să verificăm dacă suma xor a acestei perioade este $0$. Daca este $0$, soluţia constă în primele $P - 1$ elemente ale şirului, altfel primele $2P - 1$ elemente (dacă nu există, şirul generator este cel primit ca input).

private

protected