hiho一下 第180周Nature Numbers

题目1 : Nature Numbers

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

Consider the following sequence S which is constrcuted by writting nature numbers one by one: “012345678910111213…”.

The first digit of S, S[0], is 0. The second digit S[1] is 1. And the 11th digit S[10] is 1.

Given an integer N, can you find the digit S[N]?

输入

An integer N. (0 <= N <= 1018)

输出

Digit S[N].

样例输入

17

样例输出

3

思路1：打表找规律

#include <iostream>
using namespace std;

int main()
{
    int num[1005] = {0}, tag = 1;
    for(int i = 1; i < 100; i++) {
        int n = i;
        int tmp[5], dex = 0;
        while(n) {
            tmp[dex++] = n % 10;
            n /= 10;
        }
        while(dex--) {
            num[tag++] = tmp[dex];
        }
    }
    //打表找规律并不可行~~~
    for(int i  = 0; i < 50; i++) {
        cout << i << ' ' << num[i] << endl;
    }

    int N;
    while(cin >> N) {
        cout << num[N] << endl;
    }
}

思路2：直接数位数，不存储

//开始一个数一个数枚举，面对10^18数肯定超时
#include <iostream>
using namespace std;

int main()
{
    int N;
    while(cin >> N) {
        //位数计算也只能用除法一位一位去试探
        if(N == 0) {
            cout << 0 << endl;
            continue;
        }
        int cnt = 0;
        for(int i = 1; ; i++) {
            int n = i, tmp = 0;
            while(n) n /= 10, tmp++;
            cnt += tmp;
            if(cnt >= N) {
                int ans = cnt - N;  //应为i的倒数第cnt-N+1位。
                while(ans--) i /= 10;
                cout << i % 10 << endl;
                break;
            }
        }
    }
}

思路3：AC

《Nature Numbers》题目分析
一个直观的解法是从1, 2, 3, … 开始一个数一个数枚举。一开始count=0，保存位数之和。

假设当前枚举到K，我们就把count加上K的位数。如果这时count大于等于N，我们就知道第N位应为K的倒数第N-K+1位。

考虑到N=10^18时，K至少大于10^16，这个算法肯定会超时。

一种优化的思路是不要一个数一个数枚举，而是一批数一批数枚举：每次枚举所有的一位数、两位数、三位数……

一位数有10个(包括0)，两位数有90个，三位数有900个，四位数有9000个（包含的数量为9000 * 4）……

假设当前枚举到K位数，我们就把count加上(K * K位数的个数)。如果这时count大于等于N，我们就知道第N位是一个K位数的某一位。

当然具体是第几个K位数的第几位，也可以计算出来。请大家自己算一算~

• 在思路2中输入150计算出结果是80的第一位8，则151是80的第二位0.
• 两位数的总量为10 1 + 90 2 = 190. 190 >= 150.
• so 150 - 10 = 140, 140 / 2 = 70, 140 % 2 = 0.
• 70就是那个数，但不要忘记加上前面的1位数的数，即10，10 + 70 = 80.
• 余数为0所有是8，余数是1则是0.

#include <iostream>
#include <cmath>
#define LL long long
using namespace std;

int main()
{
    LL N;
    while(cin >> N) {
        if(N == 0) {
            cout << 0 << endl;
            continue;
        }
        LL cnt = 1, temp = 9;
        for(int i = 1; i < 20; i++) {   //寻找位数
            cnt += (temp * i);
            if(cnt >= N) {
                LL tmp = N - (cnt - temp * i);
                LL n = tmp / i, ans = tmp % i;
                n = n + pow(10, i - 1);
                int arr[25], tag = 0;
                while(n) {
                    arr[tag++] = n % 10;
                    n /= 10;
                }
                cout << arr[tag - ans - 1] << endl;
                break;
            }
            temp *= 10;
        }
    }
}