【CodeForces - 244B】Undoubtedly Lucky Numbers （dfs打表 + 二分）

题干：

Polycarpus loves lucky numbers. Everybody knows that lucky numbers are positive integers, whose decimal representation (without leading zeroes) contain only the lucky digits x and y. For example, if x = 4, and y = 7, then numbers 47, 744, 4 are lucky.

Let's call a positive integer a undoubtedly lucky, if there are such digits x and y(0 ≤ x, y ≤ 9), that the decimal representation of number a (without leading zeroes) contains only digits x and y.

Polycarpus has integer n. He wants to know how many positive integers that do not exceed n, are undoubtedly lucky. Help him, count this number.

Input

The first line contains a single integer n (1 ≤ n ≤ 109) — Polycarpus's number.

Output

Print a single integer that says, how many positive integers that do not exceed nare undoubtedly lucky.

Examples

Input

10

Output

10

Input

123

Output

113

Note

In the first test sample all numbers that do not exceed 10 are undoubtedly lucky.

In the second sample numbers 102, 103, 104, 105, 106, 107, 108, 109, 120, 123 are not undoubtedly lucky.

 

题目大意：

输入一个n，定义Undoubtedly Lucky 数字是仅由小于等于两种数字组成的。问你有多少个 小于等于n的 是Undoubtedly Lucky 的数字。

解题报告：

   写法很多啊这题也可以直接用set去重，，，dfs别写萎了就行了。。然后注意这题二分用upper_bound不能用lowerbound。。（因为要分很多种情况，，比如包含这个点或者不包含这个点）

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll up; int tot; ll a[MAX*100]; void dfs(ll cur,ll wei,ll i,ll j) {if(wei > 10 /*|| cur > up*/) return ;a[++tot] = cur; // if(cur == 101) { // putchar('a'); // }dfs(cur*10+i,wei+1,i,j);dfs(cur*10+j,wei+1,i,j); } int main() {cin>>up;for(int i = 0; i<=9; i++) {for(int j = i+1; j<=9; j++) {dfs(0,0,i,j);}}sort(a+1,a+tot+1);int len = unique(a+1,a+tot+1) - a-1; // printf("len = %d\n",len);for(int i = 1; i<=len; i++) printf("%lld ",a[i]); // puts("");printf("%d\n",upper_bound(a+1,a+len+1,up) - a - 1 -1);return 0 ;}

总结：

  至于为什么main函数的内层for循环为什么要从i+1开始，这是因为我们现在是枚举的那两个数字，这样会保证没有重复啊，不然肯定会多搜一倍的东西。。

总结

以上是生活随笔为你收集整理的【CodeForces - 244B】Undoubtedly Lucky Numbers （dfs打表 + 二分）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。