ABC114 C - 755
備忘録
問題
回答
import sys import os import math import bisect import collections import itertools import heapq ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: x * y / math.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = iss() S = [] for i in range(1, 10): S += set(itertools.product('753', repeat=i)) ret = 0 for s in S: if '7' in s and '5' in s and '3' in s and int(N) >= int("".join(s)): ret += 1 print(ret) if __name__ == '__main__': main()
考え方
先に7, 5, 3
のみで構成される1桁から9桁までの数値を全て生成しておき、
条件に一致する値をカウントする。
7, 5, 3
のみで構成される1桁から9桁までの数値を全て生成しても、
3 * 10 ** 5
個程度なので、処理時間も余裕で間に合う。
数値の生成にはデカルト積(itertools.product
)を使用する。
product
は引数に使用する文字列、repeat
で繰り返し回数をとる。
今回、文字列には7, 5, 3
を使用し、
繰り返し回数はrange(1, 10)
で指定することで、1桁から9桁まで生成した。