Question

Se da un șir de tipul 1,2,1,2,3,2,1,2,3,4,3,2,1,2,3,4,5,4,3,2,1,2etc.
Îmi trebuie un algoritm care sa deducă al k termen 1 <=k<=2000000000 și sa scoată și un timp bun.
Mulțumesc anticipat :)

Answer 1

Păi, în primul rând le poți împărți în grupe:
12,1232,123432,1234565432
Fiecare grupă are cu 2 elemente mai mult decât precedenta. De aici deducem că a N-a grupă începe pe poziția N*(N-1)+1. De aici vom putea afla grupa lui k, adică x=√k sau √k+1. Acum mai trebuie să aflăm poziția mijlocului secvenței și vom putea deduce elementul k în funcție de distanță până la mijloc. Ai mai jos un cod C++.

int x=sqrt(k);
if(x*(x+1)+1<=k)
x++;

int start=x*(x-1)+1;
int mij=start+x;

int t=x+1-abs(k-mij);