Rozważmy sam ciąg.
110100100, albo inaczej:
1
10
100
1000
10000
Czyli. Pierwszy element to 1znak, drugi - 2 znaki, 3 - 3 znaki element numer n - n znaków. Korzystająz ze wzoru na sumę ciągu arytmetycznego:
S(n) = ((2a1 + (n-1)*r) / 2)n; - czyli w tym wypadku:
S(n) = ((2 + (n-1) * 1) / 2)n = ((n + 1) / 2)n = (n2 + n) / 2;
Możemy obliczyć na której pozycji kończy się liczba zawierająca (n-1) zer (i jedynkę).
a więc mamy -
S(n) + 1- pozycja jedynki z (n+1)'tej potęgi dziesiątki. (+1 - ze względu na syngature. wzór pokazuje nam gdzie kończy się dana potęga).
Pozycję znamy, nie wiemy która to potęga. A więc proste podstawienie:
S(n) + 1 = x
((n2 + n) / 2) + 1 = x (x - pozycja na wejściu).
Przekształcić ten wzór to chyba dasz radę? ;)
Wnioskując po komentarzach - nie potrafisz. Więc:
Wyznaczam n z powyższego:
n2 + n + 2 = 2x,
n2 + n - 2x + 2 = 0
d - delta.
d = 12 - 4 * 1 * (-2x + 2),
d = 1 -8x - 8,
d = 8x - 7.
interesuje nas tylko dodatni wynik:
n = (-1 + sqrt(d)) / 2.
n = (sqrt( 8x - 7 ) - 1) / 2.
Jeśli n wyjdzie całkowite, to na danym miejscu jest jedynka, jeśli nie - mamy zero :)
if( float( int( n ) ) == n ) // albo trudniej, ale szybciej:
cout << float( int( n ) ) == n;
Jeśli nie rozumiesz dlaczego tak jest to możesz zrobić tak jak @_13th_Dragon poniżej:
Jeżeli równanie jest spełnione - mamy jedynkę:
if( (n*(n+1) / 2) == x ) // albo trudniej, ale szybciej:
cout << (n*(n+1) / 2) == x ;
Do tego możesz łatwo rysować ciąg dalej. Wystarczy na podstawie ułamka określić, które to zero ( część po przecinku / n), dorysować pozostałe zera i dalej rysować 1 i n+1 zer, 2 i n+1 zer. Coś mogłem pochrzanić, bo nie rozpisywałem tego na kartce, ale ogólna zasada jest taka :)
No i pochrzaniłem. Nie wziąłem pod uwagę, że S(n) pokazuje na koniec danego elementu. @_13th_Dragon zrobił niżej poprawnie. Gdybyś kierował się tą zasadą mógłbyś mi nawet wytknąć błąd.