題目地址：http://poj.org/problem?id=1019
一道普通的ACM題，但是從中可以看出一些問題。題很簡單，就是給你一串數字串，其規律為：
1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 123456789101112······
輸入位置i，計算這一串數字第i位是什麼數字，注意是數字，不是數。例如12345678910的第10位是1，而不是10，第11位是0，也不是10。
然後就很好說了，計算一個數字k的長度用：int(log10(double(num))) + 1，然後變量sk每次加上k的長度，再定一個和變量sum，它每次加上sk的值，直到sum比index大。然後再根據剩余的長度在sk內部找那個數字，很簡單。
這裡有個問題就是，題中說“The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)”，按照OJ的慣例，測試用例肯定會有極端情況，極大的或極小的，所以i = 2147483647是一定要考慮的。這裡如果處理不好或許會出現超時的情況。很不幸我就超時了。
有一點非常詭異，在代碼第48行，注釋說：若是sum < index 則超時。因為我開始時while裡用的就是sum < index，每次判定當前數到的長度是否比題中給的長度index小。但是很遺憾這樣對於極大的情況：i = 2147483647會很慢，插裝了計算時間的代碼後發現這一步需要計算60秒左右。
而後我在網上搜索到了別人的代碼，基本都是使用累加的方法，比如：http://blog.csdn.net/lyy289065406/article/details/6648504中是這樣累加的：
const int size=31269;
void play_table(void) { a[1]=s[1]=1; for(int i=2;i<size;i++) { a[i]=a[i-1]+(int)log10((double)i)+1; //log10(i)+1 表示第i組數字列的長度 比 第i-1組 長的位數 s[i]=s[i-1]+a[i]; //前i組的長度s[i] 等於 前i-1組的長度s[i-1] + 第i組的長度a[i] } //log()是重載函數，必須對int的i強制類型轉換，以確定參數類型 return; }雖然采用的是數組打表的方法在大量測試用例的情況下會快很多，但是累加過程是一樣的，耗時差異如此之大，我想，可能就是出在判斷語句上了。
他的判斷語句是“i<31269”，而我的是“sum < 2147483647”，問題或許就出在這裡，我的小於號兩端用來比較的數字都太大。事實證明是這樣的，我采用了與他類似的判斷條件來累加後，耗時變成了0s，然後我將while的判定條件從sum < index改為了index - sum > 0，耗時也是0s（這個0s是在本機上用time函數測出來的，非OJ運行時間，若要像OJ那樣精確到毫秒需要用別的函數）。
為什麼只是一個小小的改動，耗時卻變化這麼大呢？或許我們要到底層去考慮，int型的變量占4個字節，也就是32bit，兩個比較大32bit的數字相互比較自然比兩個比較小的相互比較要耗時很多。或許再結合匯編裡的知識會理解地更透徹一些，但是很遺憾我已經忘了。。。
下面是完整的代碼，在POJ上通過，268K 16MS。（如果打表的話，占用內存會增加，但是時間會減少，以空間換時間而已，既然這樣能過就不打表了）
#include <iostream>
#include <cmath>
#include <fstream>
#include <time.h>
size( (log10((num))) + ;
digit( num, length = size(num) - (length-- num /= num %= num;
cin >> (t-- cin >>
sum = k = sk =
(index - sum > )
k++ sk += sum +=
sum = index - sum +
num = length = (length < num++ length +=
length = sum - length +
cout <<digit(num, length) << }
