3620: 数字序列 -训练套题T8T2
Description
2.数字序列number
【问题描述】
给定一个数字N，在黑板上写下1到N，这样你就得到一个数字N1。例如，给定N=11，
则N1=123456789101l，然后从N1里擦掉偶数位置的数组，就得到N2=1357901，再擦掉N2奇数位的数字，就得到N3=370,重复以上步骤直到只剩下一个数字，输出这个数。
【输入格式】
输入有多组数据，每组数据占一行，仅有一个数N。
【输出格式】
对于每组数据，输出按如上操作后，黑板上剩下的数。
【输入样例】
1
4
11
【输出样例】
1
3
0
【数据规模】
对于30％的数据，N≤1 0^3。
对于60％的数据，N≤1 0^6。
对于100％的数据，N≤10^15，数据不超过10^4组。
HINT
HJF:
首先对于一个x位的数，我们来观察先擦掉它偶数位置的数字，再擦掉余下的数字中的奇数位置的数字后剩下的数字在原数中是哪些位上的?显然剩下的数字在原数中的位置依次为3，7，11，…，这样的位置共有(x+1)／4个(“／’’在本文中均表示整除运算)。
我们将剩下的数字的位置还按照1，2，3，…进行编号，然后继续进行下一周期的操作，则得到一个与原问题本质一致的子问题，其规模为(x+1)／4。设原问题的解为F(x)，则子问题的解为F((x+1)／4)。根据上述的位置编号转换关系可得递归式F(x)=4 F((x+1)／4)-1，边界条件为F(1)=1，F(2)=1。
有了上述的递归式，我们就能在1 og4(x)的时间内求出一个总长为x位的数最终剩下
的是哪个位置的数。对于输入数据n，只要算出它对应的数n1共有多少位，这一点相信大
家都会推算，然后用递归式算出n1最终剩下的数所在的位置，再用二分法找到这个位置
上的数即可。