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

h1(#kxorbonacci). 'Solutia 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).

Observam ca un sir kxorbonacci generat de ( $v{~1~}$, $v{~2~}$, ..., $v{~n~}$ ) este periodic cu perioada $n + 1$. Deasemenea suma xor a orcaror $n + 1$ elemente alaturate este $0$. Astfel este suficient sa gasim perioada minima $P$ a sirului primit ca input si sa verificam daca suma xor a acestei perioade este $0$. Daca este $0$ solutia consta in primele $P - 1$ elemente ale sirului, altfel primele $2P - 1$ elemete (daca nu exista, sirul generator este cel primit ca input).

protected

private