人人公司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;
    }
    }