atcoder ABC114 C - 755の勉強

atcoder.jp

・参考
AtCoder ABC 114 C - 755 (緑色, 300 点) - けんちょんの競プロ精進記録

・説明
参考記事をPythonで勉強した。全通り試すのではなく、3,5,7を桁に追加して再帰関数を回していけば良い。値がnを超えれば終了になる。

n=int(input())

#ansをもとめる。
def func(now,use):  #nowが今の数、useが3，5，7どれを使ったか、
  global ans
  #終端
  if now>n:
    return 
  
  if use==7:  #3，5，7が1回以上で。7は0b111。
    ans+=1
  
  #7のとき
  func(10*now+7,use|0b001)  #例えばuseが0(nowが0)ではuse|0b001=0b001。
  
  #5のとき
  func(10*now+5,use|0b010)  #例えばuseが1(nowが7)ではuse|0b010=0b011。
  
  #3のとき
  func(10*now+3,use|0b100)  #例えばuseが0b011(nowが75)ではuse|0b010=0b111。

ans=0
func(0,0)
print(ans)