人人公司2017校园招聘在线考试-编程一

发表于 | 分类于 ，

题目-伪随机数

描述

有一天小M得到了一个随机数生成器，它是这样工作的：
* 首先你需要输入一个正整数n表示你要生成的随机数的位数。
* 然后它会生成一个n位的不包含前导0的正十进制数。
* 但是小M发现这个生成器有一个性质，它生成的数在第i位上(从左向右数)的数字永远不等于i。
比如生成位数长度为1的数，那么它不会生成0和1；
如果生成位数长度为2的数，它不会生成
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 32, 42, 52, 62, 72, 82和92。
现在小M想知道对于一个给定的输入n，它一共可能生成多少种不同的数？

输入

第一行包含一个整数n。1<=n<=100

输出

输出对应的答案。

Example

Input

1

Output

8

题解

思路

  • 递推公式 f(1)=8,f(n)=f(n-1)10-f(n-1) (n<=9),f(n)=f(9)10^(n-9) (n>9)
  • 注意 n 的范围
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include <bits/stdc++.h>

    using namespace std;

    int main()
    {
        int n;
        while(cin>>n)
        {
            double c=8;
            for(int i=2;i<=min(9,n);++i)
            {
                c=10*c-c;
            }
            cout<<c;
            for(int i=min(9,n)+1;i<=n;++i)
                cout<<0;
            cout<<endl;
        }
    }