Zagadkowy Ciąg liczb Zadanie na jutro! 1121231234 Pomocy!

Witam. Jestem uczniem pewnego liceum na profilu mat-inf i zwracam się z prośbą o pomoc w poniższym zadaniu.

ZAGADKOWY CIĄG

Michał zawsze bardzo lubił matematykę, więc - co zrozumiałe - był pojętnym uczniem.
Rozwiązywał problemy matematyczne znacznie szybciej niż koledzy w klasie.
Pewnego dnia, na lekcji, gdy Michał zrobił już zadania z ćwiczeń, trochę ze znużenia, trochę z
ciekawości zapisał w zeszycie ciąg: 1121231234123451234561234567... - każda cyfra była w
odzielnej kratce.

Zaintrygowany profesor szybko odgadł, w jaki sposób jego uczeń zbudował ciąg i chcąc go
"zagiąć", zapytał, czy potrafi powiedzieć jaka cyfra znajduje się na zadanej pozycji. Michał
odpowiedział dyplomatycznie, że problem wymaga głębszych przemyśleń i obiecał, że na następnej
lekcji przedstawi rozwiązanie.

Po powrocie do domu zabrał się ostro do pracy - najpierw musi zobaczyć jak wyglądają wyniki dla
"małych" liczb z przedziału 1..231-1. Michał nie posiada komputera. Pomóż mu znaleźć rozwiązanie
dla "małych" przypadków.

Wejście

Pierwsza liczba C, 1 ≤ C ≤ 100, określa liczbę zestawów danych. W kolejnych C liniach znajdują
się liczby N, 1 ≤ N < 231, określające pozycję cyfry w ciągu.
Wyjście

Na wyjściu powinno znaleźć się C cyfr, każda w osobnej linii, równych odpowiednio cyfrze na Ntej
pozycji w ciągu.

Przykład

Dla danych:
3
3
4
5
poprawnym rozwiązaniem jest:
2
1
2

Proszę pomóżcie mi chociaż odnaleźć sposób na znalezienie wybranej liczby w ciągu, ewentualnie główną część programu. Z góry dziękuję.

Zadanie mi się spodobało.
http://ideone.com/kNwHK

Magia to trochę podstaw z ciągów arytmetycznych.

#include <iostream>
#include <cmath>

double MagicHappensHere(unsigned int position)
{
	return (sqrt(8. * position + 1) - 1) / 2;
}

int HokusPokus(unsigned int position)
{
	double value = MagicHappensHere(position);

	if(value == floor(value)) return value;

	int result;
	for(result = 0; value != floor(value); ++result)
		value = MagicHappensHere(--position);

	return result;
}

int main()
{
	int setsNum;
	std::cin >> setsNum;

	for(int i = 0; i < setsNum; i++)
	{
		int position;
		std::cin >> position;
		std::cout << HokusPokus(position) << "\n";
	}

	return 0;
}

O dzieki wielkie, teraz musze to dokładnie przeanalizować, bo jak na razie to czarna magia dla mnie ;D Dzięki jeszcze raz.

int cyfra_ciagu( int n ) { 
   static std::vector<int> ciag;

   // Inicjalizacja. Happens once. 
   if ( ciag.empty() ) { 
      for ( int i = 1; i <= 15; i++ ) { // ponieważ n < 231; ciąg zbudowany z 1...15 będzie > 231 
           for ( int j = 1; j <= i; j++ ) {
               if ( j >= 10 ) ciag.push_back( 1 ); 
               ciag.push_back( j % 10 ); 
           }
      }
   }
   // <-- Inicjalizacja

   return ciag[n];  
} 

Na szybko, brzydkie, nie testowane.

int ooo(int OOO) {
        int OO00=000, O0O=000, O00=000;
        while( O0O < OOO ){
                OO00=O0O;
                O0O += ++O00; }
        return (OOO-OO00)%012; }
 
main(){
        int i;
        for(i=1;i<231;i++)
                printf("%d", ooo(i));}

http://ideone.com/xkdzb