 AtCoder Beginner Contest 114 C——755

2018-12-02 22:27:50

# 原题：

Problem Statement

You are given an integer N. Among the integers between 1 and N (inclusive), how many Shichi-Go-San numbers (literally "Seven-Five-Three numbers") are there?

Here, a Shichi-Go-San number is a positive integer that satisfies the following condition:

• When the number is written in base ten, each of the digits '7', '5' and '3' appears at least once, and the other digits never appear.

Constraints

• 1≤N<1e9
• N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of the Shichi-Go-San numbers between 1 and N (inclusive).

Sample Input 1

575

Sample Output 1

4

There are four Shichi-Go-San numbers not greater than 575: 357,375,537 and 573.

Sample Input 2

3600

Sample Output 2

13

There are 13 Shichi-Go-San numbers not greater than 3600: the above four numbers, 735,753,3357,3375,3537,3557,3573,3575 and 3577.

Sample Input 3

999999999

Sample Output 3

26484

# AC代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#include<algorithm>
#include<queue>
typedef long long ll;
#include<vector>
#include<set>
#define cin(n) scanf("%lld",&(n))
#define cout(n) printf("%lld",(n))
#define couc(c) printf("%c",(c))
#define coutn printf("\n")
#define cout_ printf(" ")
set<int> s;
const int MAXN= 1e4 + 5 ;
ll n;
ll ans;
void dfs(ll l,ll a,ll b,ll c)
{
if(l>n)    return;
if(a>=1&&b>=1&&c>=1) ans++;
dfs(l*10+3,a+1,b,c);
dfs(l*10+5,a,b+1,c);
dfs(l*10+7,a,b,c+1);
}
int main()
{
scanf("%lld",&n);
dfs(0,0,0,0);
printf("%lld",ans);
return 0;
}

• star
首页