Problem:

F: ごちうさ数

問題

ごちうさが大好きなAORイカちゃんは「ごちうさ数」を定義した。
ごちうさ数とは、 $10$ 進表記において「 $51?3$ 」を含む自然数のことである。

$?$ は $0$ 〜 $9$ のどの数字であってもよい。

 $N$ 以下の自然数のうち、ごちうさ数の個数を求めよ。

制約

$1 \le N < 10^{18}$

入力

$N$

出力

ごちうさ数の個数を一行で出力せよ。また末尾に改行を出力せよ。

サンプル

サンプル入力 1

5124

サンプル出力 1

3

$5124$ 以下のごちうさ数は、$5103$ , $5113$ , $5123$ の 三つである。

サンプル入力 2

60000

サンプル出力 2

160

サンプル入力 3

100000

サンプル出力 3

200



Sample input:
5124


Sample output:
3

Submission status: Wrong Answer

Solution code:
def usa(x):
    if x <= 5000: return False
    sx = str(x)
    return sx[0] == '5' and sx[1] == '1' and sx[3] == '3'


def rec(k, tight, prev, ok, x, dp):
    if len(x) == k:
        # print(prev)
        return 1 if ok else 0
    if dp[k][tight][prev] != -1:
        return dp[k][tight][prev]

    upper = int(x[k]) if tight == 1 else 9
    ret = 0
    for i in range(0, upper + 1):
        newPrev = prev
        newPrev *= 10
        newPrev %= 10000
        newPrev += i
        newTight = tight
        if newTight == 1 and i != int(x[k]):
            newTight = 0
        ret += rec(k + 1, newTight, newPrev, ok or usa(newPrev), x, dp)

    dp[k][tight][prev] = ret
    return ret


if __name__ == '__main__':
    N = int(input())
    Dp = [[[-1 for k in range(10000)] for j in range(2)] for i in range(len(str(N)))]
    ans = rec(0, 1, 0, False, str(N), Dp)
    print(ans)

Submission status: Wrong Answer

Solution code:
def usa(x):
    if x <= 5000: return False
    sx = str(x)
    return sx[0] == '5' and sx[1] == '1' and sx[3] == '3'


def rec(k, tight, prev, ok, x, dp):
    if len(x) == k:
        # print(prev)
        return 1 if ok else 0
    if dp[k][tight][prev] != -1:
        return dp[k][tight][prev]
    if ok:
        return int(10 ** (len(x) - k))

    upper = int(x[k]) if tight == 1 else 9
    ret = 0
    for i in range(0, upper + 1):
        newPrev = prev
        newPrev *= 10
        newPrev %= 10000
        newPrev += i
        newTight = tight
        if newTight == 1 and i != int(x[k]):
            newTight = 0
        ret += rec(k + 1, newTight, newPrev, ok or usa(newPrev), x, dp)

    dp[k][tight][prev] = ret
    return ret


def solve(N):
    Dp = [[[-1 for k in range(10000)] for j in range(2)] for i in range(len(str(N)))]
    ans = rec(0, 1, 0, False, str(N), Dp)
    return ans
    # print(ans)


if __name__ == '__main__':
    N = int(input())
    print(solve(N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()

def func(S, index, cnt):
    ans = 0
    if index == 20:
        if cnt == 0:
            return 0
        S_ = list(S)
        for i in range(20):
            if S_[i] != '?':
                continue
            for j in range(10):
                S_[i] = str(j)
                if int(''.join(S_).replace('?', '9')) > N:
                    break
                else:
                    ans += 10 ** S_.count('?')
        ans *= (-1) ** (cnt + 1)
        return ans
    ans += func(S, index + 1, cnt)
    if index <= 16:
        S_ = list(S)
        S_[index] = '5'
        S_[index + 1] = '1'
        S_[index + 3] = '3'
        ans += func(S_, index + 4, cnt + 1)
    return ans

S = ['?'] * 20
print func(S, 0, 0)