AtCoder Beginner Contest 114 C——755

2018-12-02 22:27:50


B类

题目链接:

https://abc114.contest.atcoder.jp/tasks/abc114_c

原题:

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

题意:

从1到N,有多少个“七五三”数,“七五三”数是这样规定的:数字中只有7,5和3,且至少全部都有一个。

思路:

(刚开始看成数学题了,导致自闭做不出来

(别说了,又是赛后过题o(╥﹏╥)o

深搜把所有的3,5,7存下来,当3,5,7全部都有以上时,答案数就加一,注意开long long

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;
}