Ciąg nieskonczony, i-ty element.

Witam mam problem otóż jest pewien ciąg nieskonczony 112123123412345...
Musze pobrać i-ty element tego ciągu co probówalem to np powiększyć ten ciąg do takiego stopnia aby pobrać ten index czyli np 4 element to będzie 1
tylko że przy podaniu liczby większej niż 100 000 to tak troche STL vector pada i mam illegal syscal ;p macie jakiś pomysł aby to jakoś sprytniej zrobić może? :D

#include <iostream>
#include <vector>

int main(void){

  std::vector<int> vec;
  int numb;
  std::cin >> numb;
  for(int i=0; i<numb;++i){
    for(int n=1;n<=i;++n){
      vec.push_back(n);
    }
  }
  std::cout<<vec[numb-1];
  return 0;
}

Coś słabo opisałeś warunki zadania. Dostajesz znany ciąg nieskończony na wejściu, czy masz sobie go wygenerować?

Tak czy inaczej jeśli interesuje Cię tylko jeden element to nie ma sensu trzymać wszystkich poprzednich.

wygenerować, jest to pewien ciąg 1121231234.. itd.. na wejscie dostajemy np 5 i musimy z tego ciągu wypisać 5 element

a na wejsciu może byc liczba i < 10^15 więc generowanie ciągu xd troche odpada :( nie mam pomysłu ;/

Przecież widać, że to można wyliczyć bez trzymania elementów ciągu.
Długości kolejnych podciągów to 1, 2, 3, 4, 5, 6, 7, ...
Mając n chyba nietrudno wyliczyć w którym podciągu to będzie?
A potem równie łatwo wyliczyć który to element tego podciągu, co jednocześnie będzie tą poszukiwaną liczbą.

nie masz iterować jaki aż trafisz na element o numerze milion miliardów , tyko masz zgadnąć jego wartość na podstawie tego jak ten ciąg wygląda. Na pewno można wyznaczyć wzór na ten element, który go obliczy w czasie O(1) ale na razie nie mam na to pomysłu, Jakbyś napisał algorytm który przesuwa "index" najpierw o jeden potem o 2 potem o 3 itd. bez liczenia wartości (ten cały czasz będzie wskazywał na jeden) to aż przekroczysz szukany numer, potem porostu policzył różnice miedzy przed ostatnim krokiem a szukaną liczbą, to raz było by dużo szybciej i dwa chyba dało by rade zgadnąć na podstawie tego jaką jaki jest algorytm który działa w czasie o(1)

Co będzie w ciągu po "123456789"?

tez się zastanawiam, nie wiem bo tak pisze w zadaniu że mamy pewien ciąg 112123123412345... i tyle :D ale chyba będzie 12345678910 :D
No niby znając n można obliczyć ale jak??

Po jednym podciągu masz 1 element.
Po 2 podciągach masz 3 = 2 + 1 = (2 + 1) * 2 / 2 elementy.
Po 3 podciągach masz 6 = 3 + 2 + 1 = (3 + 1) * 3 / 2 elementów.
Po 4 podciągach masz 10 = 4 + 3 + 2 + 1 = (4 + 1) * 4 / 2 elementów.
Po k podciągach masz (k + 1) * k / 2 elementów.

Mając n jakie jest największe k, że (k + 1) * k / 2 <= n?

ale to o to chodzi że ja dostaje tylko index w danym ciągu nie mam N ;) tzn ze jak dostane index 4 to ilosc elementow musi byc 6 zeby pobrac 4 element.. i co teraz:D

Ta dam na początku liczysz to n (ed k. )o którym mówił kolega wyżej u mnie to depth a potem obliczasz sume szeregu dla tych depth elemnetów i umiejętnie odejmujesz.

   static void Main(string[] args)
        {
            Random rnd = new Random(1234);
            long n = 4; // result 1
            int loop = 20;
            long element = BrutForce(n);
            for (int i = 0; i < loop; i++)
            {
                Console.WriteLine("n:"+n+" "+BrutForce(n)+" "+Faster(n)+" "+ Fast(n));
                n = n+rnd.Next(131, 3211);
            }
            Console.WriteLine();
            n = 19110;
            Console.WriteLine("n:" + n + " " + BrutForce(n) + " " + Faster(n) + " " + Fast(n));
            n = 19111;
            Console.WriteLine("n:" + n + " " + BrutForce(n) + " " + Faster(n) + " " + Fast(n));
            Console.ReadKey();
        }
        private static long BrutForce(long n)
        {
            long index = 1;
            for (int depth = 1; true; depth++)
            {
                for (int i = 1; i <= depth; i++)
                {
                    if (index == n)
                        return i;
                    index++;
                }
            }
        }
        private static long Faster(long n)
        {
            long index = 1; int depth;
            for (depth = 1; true; depth++)
            {
                if (index >= n)
                    break;
                index += depth;
            }
            if (index == n)
                return 1;
            return (n - index + depth); // mówiłem że da rade zgadać na podstawie tej wersji :D
        }
        private static long Fast(long n)
        {
            var depth = (long)Math.Ceiling(GetDepth(n));
            var sum = Suma(depth);
            if (sum == n)
                return depth;
            return (n -sum + depth) % (depth);
        }
        private static long Suma(long n)
        {
            return ((2 + (n - 1)) *n)/ 2 ;
        }
       
        private static double GetDepth(long n)
        {
            var delta = 2 * n + 1;
            var x2 = (-1 + Math.Sqrt(delta));
            return x2;
        }

ok tylko że mi to liczy najwieksza ilosc elementow w danym ciagu aby uzyskac ten element, i co dalej?

#include <iostream>

int main(void){

  int numb;
  int n=0,el=0;
  std::cin >> numb;
  while(n<=numb){
    n = ((el+1)*el)/2;
    ++el;
  }


  return 0;
}

cos takiego? wychodzi mi dla 4 6 a powinno 1 ... i co?

Załóżmy, że dostajesz n == 12. Wtedy wyliczasz, że największe k, o którym wspomniałem to 4. Czyli element o indeksie n znajduje się po 4 pierwszych podciągach (czyli jest w piątym podciągu, ale to jest mało ważne). 4 pierwsze podciągi mają razem 4 * 5 / 2 == 10 elementów, czyli szukasz drugiego (12 - 10) elementu w piątym podciągu, czyli liczby 2.

I nie, nie wyliczasz k za pomocą pętli. Wystarczy przekształcić wzór.