Hexadecimal's Numbers([heu] 20180429_happy_labor_day1 L)

Author Avatar
XYenon 4月 29, 2018
  • 在其它设备中阅读本文章

题目

L - Hexadecimal’s Numbers

Description

One beautiful July morning a terrible thing happened in Mainframe: a mean virus Megabyte somehow got access to the memory of his not less mean sister Hexadecimal. He loaded there a huge amount of n different natural numbers from 1 to n to obtain total control over her energy.

But his plan failed. The reason for this was very simple: Hexadecimal didn’t perceive any information, apart from numbers written in binary format. This means that if a number in a decimal representation contained characters apart from 0 and 1, it was not stored in the memory. Now Megabyte wants to know, how many numbers were loaded successfully.

Input

Input data contains the only number n (1 ≤ n ≤ 109).

Output

Output the only number — answer to the problem.

Examples

Input

10

Output

2

Note

For n = 10 the answer includes numbers 1 and 10.

代码

#include <bits/stdc++.h>

using namespace std;

long long plusOne(long long, long long, long long);
long long mutiTen(long long, long long, long long);

int main() {
    long long n;
    scanf("%lld", &n);
    long long ans;
    if(n == 0) {
        ans = 0;
    } else {
        ans = mutiTen(1, n, 0) + plusOne(1, n, 0);
    }
    printf("%lld", ans);
    return 0;
}

long long mutiTen(long long x, long long n,long long ans) {
    if(x > n) {
        return 1;
    }
    return ans + mutiTen(x * 10, n, 0) + plusOne(x * 10, n, 0);
}

long long plusOne(long long x, long long n, long long ans) {
    if(x > n) {
        return 1;
    }
    if(x % 10) {
        return -1;
    }
    return ans + mutiTen(x + 1, n, 0);
}

本文使用 署名 - 非商业性使用 - 相同方式共享 3.0 中国大陆 协议许可
本文链接:https://xyenon.bid/2018/04/29/Hexadecimal-s-Numbers([heu]-20180429_happy_labor_day1-L)/