UVA 10427 - Naughty Sleepy Boys

#include <bits/stdc++.h>
#define EPS 1e-9
#define PI 3.14159265359
using namespace std;

int main()
{
    int n, l, h, mid, t1, t2, t3, cnt, dig;
    while(scanf("%d", &n) == 1){
        l = 1, h = 1e8;
        while(1){
            mid = (l + h) / 2;
            t1 = 1; t2 = mid; dig = 0;
            while(t2) t2 /= 10, t1 *= 10, dig++;
            t3 = dig;
            t1 /= 10;
            cnt = (mid - t1) * t3;
            t3--;
            while(t3 > 1){
                cnt += (t1 - 1 - t1/10 + 1) * t3;
                t3--; t1 /= 10;
            }
            if(t3) cnt += 9;
            if(n - cnt <= 0) h = mid - 1;
            else if(n - cnt <= dig) break;
            else if(n - cnt > dig) l = mid + 1;
        }
        for(int i=1; i<=dig - n + cnt; i++){
            mid /= 10;
        }
        printf("%d\n", mid % 10);
    }
}