Problem:


Score: 300 points

Problem Statement

AtCoder Mart sells 1000000 of each of the six items below:

Riceballs, priced at 100 yen (the currency of Japan) each

Sandwiches, priced at 101 yen each

Cookies, priced at 102 yen each

Cakes, priced at 103 yen each

Candies, priced at 104 yen each

Computers, priced at 105 yen each

Takahashi wants to buy some of them that cost exactly X yen in total.
Determine whether this is possible.

(Ignore consumption tax.)

Constraints

1 \leq X \leq 100000

X is an integer.

Input

Input is given from Standard Input in the following format:

X

Output

If it is possible to buy some set of items that cost exactly X yen in total, print 1; otherwise, print 0.

Sample Input 1

615

Sample Output 1

1

For example, we can buy one of each kind of item, which will cost 100+101+102+103+104+105=615 yen in total.

Sample Input 2

217

Sample Output 2

0

No set of items costs 217 yen in total.



Sample input:
615


Sample output:
1

Submission status: Wrong Answer

Solution code:
x = input()
if len(x) < 3:
    print(0)
    exit()

if x[-3] == "0":
    k = 10
else:
    k = int(x[-3])

x = int(x[-2:])

if 0 <= x <= 5*k:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

x = input()
if len(x) < 3:
    print(0)

if len(x) == 3:
    x = "0" + x

x = int(x[-4:])

products = [100, 101, 102, 103, 104, 105]

def dfs(comb_):
    if sum(comb_) == x:
        return 1
    elif sum(comb_) > x:
        return 0
    
    for product in products:
        comb = comb_[:]
        comb.append(product)
        if dfs(comb) == 1:
            return 1

    return 0

print(dfs([]))

Submission status: Wrong Answer

Solution code:
x = int(input()[-3:])

if 100 <= x <= 105 or 201 <= x <= 209 or 303 <= x <= 312 or 406 <= x <= 414 or \
    510 <= x <= 515 or x == 615:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
x = int(input())
tmp = []
for a in range(2):
    for b in range(2):
        for c in range(2):
            for d in range(2):
                for e in range(2):
                    for f in range(2):
                        tmp.append(100*a + 101*b + 102*c + 103*d + 104*e + 105*f)
x = x % 615
print(1 if x in tmp else 0)

Submission status: Wrong Answer

Solution code:
X = int(input())

dp = [False] * (X + 1)
dp[0] = True
for i in range(X):
  if i:
    for x in [100, 101, 102, 103, 104, 105]:
      if i+x <= X:
        dp[i+x] = True

if dp[-1]:
  print(1)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
x=int(input())
for i in range(1,1000000):
  if 100*i<=x<105*i:
    print(1)
    exit()
print(0)

Submission status: Wrong Answer

Solution code:
x=int(input())
for i in range(1,1000000):
  if 100*i<=x<105*i:
    print(1)
    break
else:
  print(0)

Submission status: Wrong Answer

Solution code:
x=int(input())
for i in range(1,1001):
  if 100*i<=x<105*i:
    print(1)
    break
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    x = II()
    n = x//100
    d = x%(10*(len(str(n*5))))
    if d < n*5:
        print(1)
    else:
        print(0)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    x = II()
    n = x//100
    d = x%100
    if d < n*5:
        print(1)
    else:
        print(0)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
X = int(input())
def hoge(X):
    if 1+ ((X%100)//5) <= X//100:
        return 1
    else:
        return 0
print(hoge(X))

Submission status: Wrong Answer

Solution code:
X = int(input())
def hoge(X):
    if ((X%100)%5) + ((X%100)//5) <= X//100:
        return 1
    else:
        return 0
print(hoge(X))

Submission status: Wrong Answer

Solution code:
X = int(input())
def hoge(X):
    if ((X%100)%5) + 1 <= X//100:
        return 1
    else:
        return 0
print(hoge(X))

Submission status: Wrong Answer

Solution code:
X = int(input())
def hoge(X):
    if X%100 < ((X//100) + 1)*5:
        return 1
    else:
        return 0
print(hoge(X))

Submission status: Wrong Answer

Solution code:
x=int(input())
a=x//100
b=x%100
print(a,b)
if b>=0 and b<=5*a:
    print("1")
else:
    print("0")

Submission status: Wrong Answer

Solution code:
X = int(input())
a = [100, 101, 102, 103, 104, 105]
dp = [[False]*100010 for _ in range(10)]
dp[0][0] = True
for i in range(6):
    for j in range(100001):
        dp[i+1][j] |= dp[i][j]
        if j >= a[i]:
            dp[i+1][j] |= dp[i][j-a[i]]

if dp[6][X]:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
x=int(input())
n = x//100
k = x %100
if n >= 17 :
    print(1)
elif k <= n*5:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:

x=int(input())
n = x//100
k = x %100
if n >= 21 :
    print(1)
elif n*1 <= k <= n*5:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
x=int(input())
n = x//100
k = x %100
if n >= 101 :
    print(1)
elif n*1 <= k <= n*5:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
sum = input()

if len(sum) < 3:
    print('0')
else:
    last_2_digit = sum[-2:]
    upper_digit = sum[:-2]

    if last_2_digit == '00':
        print('1')
    else:
        required_num = (int(last_2_digit) - 1) // 5 + 1
        print(upper_digit, last_2_digit, required_num)
        if int(upper_digit) >= required_num:
            print('1')
        else:
            print('0')

Submission status: Wrong Answer

Solution code:
sum = input()

if len(sum) < 3:
    print('0')
else:
    last_2_digit = sum[-2:]
    upper_digit = sum[:-2]

    if last_2_digit == '00':
        print('1')
    else:
        required_num = int(last_2_digit) // 5 + 1
        if int(upper_digit) >= required_num:
            print('1')
        else:
            print('0')

Submission status: Wrong Answer

Solution code:
X = int(input())
if X < 100:
    print(0)
else:
    sX = str(X)
    div1 = X // 100
    div2 = int(sX[-2:]) // 5
    # print(div1, div2)
    if div1 < div2:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
import math
X=int(input())

N=int(math.ceil(X/105))
dekiruka=0
while N < X/100:
    if X-100*N <= 5*N:
        dekiruka=1
        break
    N=N+1

if dekiruka==1:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
x = input()
x1 = list(x)
h = len(x)
x = int(x)

if x>2000:
  print('1')
  sys.exit()

a1 = int(x1[h-1])
a2 = int(x1[h-2])

if 0 < a1 < 5:
  c1 = 1
elif a1 == 0:
  c1 = 0
else:
  c1 = 2

c2 = a2*2
#print(x1[0],x1[1])
if h>3:
  if 10*int(x1[0])+int(x1[1]) < c1+c2:
    print('0')
  else:
    print('1')
else:
  if int(x1[0]) < c1+c2:
    print('0')
  else:
    print('1')

Submission status: Wrong Answer

Solution code:
import sys
x = input()
x1 = list(x)
h = len(x)
x = int(x)

if x>2000:
  print('1')
  sys.exit()

elif x<100:
  print('0')
  sys.exit()
a1 = int(x1[h-1])
a2 = int(x1[h-2])

if 0 < a1 < 5:
  c1 = 1
elif a1 == 0:
  c1 = 0
else:
  c1 = 2

c2 = a2*2
if int(x1[0])+int(x1[1]) < c1+c2:
  print('0')
else:
  print('1')

Submission status: Wrong Answer

Solution code:
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math
import functools

def judge(li,x,flag):
    ans = 0
    for j in range(len(flag)):
        if flag[j] == True:
            ans += li[j]
    if ans == x:
        return 1
    else:
        return 0
li = [100,101,102,103,104,105]
n = len(li)
x = int(input())
for i in range(2**n):
    flag =[False]*n
    for j in range(n):
        if (i>>j)&1:
            flag[n-j-1] = True
    ans = judge(li,x,flag)
    if ans == 1:
        print(ans)
        sys.exit()
print("0")

Submission status: Wrong Answer

Solution code:
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math
import functools

def judge(li,x,flag):
    ans = 0
    for j in range(len(li)):
        if flag[j] == True:
            ans += li[j]
    if ans == x:
        return 1
    else:
        return 0
li = [100,101,102,103,104,105]
x = int(input())
for i in range(2**len(li)):
    flag =[False]*len(li)
    for j in range(len(li)):
        if (i>>j)&1:
            flag[j] = True
    ans = judge(li,x,flag)
    if ans == 1:
        print(ans)
        sys.exit()
print("0")

Submission status: Wrong Answer

Solution code:
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math
import functools

def judge(li,x,flag):
    ans = 0
    for j in range(len(li)):
        if flag[j] == True:
            ans += li[j]
    if ans == x:
        return 1
    else:
        0
li = [100,101,102,103,104,105]
x = int(input())
for i in range(2**len(li)):
    flag =[False]*len(li)
    for j in range(len(li)):
        if (i>>j)&1:
            flag[j] = True
    ans = judge(li,x,flag)
    if ans == 1:
        print(ans)
        sys.exit()
print("0")

Submission status: Wrong Answer

Solution code:
x = int(input())

x_sur = x % 100

if x_sur > 15:
    print(0)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
X = int(input())
print(0 if X//105 == X//100 else 1)

Submission status: Wrong Answer

Solution code:
x = int(input())

num_min = x//106
num_max = x//100

for i in range(num_min, num_max+1):
    if x - 100*i <= 6*i:
        print(1)
        exit()
        
print(0)

Submission status: Wrong Answer

Solution code:
x=int(input())
if x>=2000:
    print(1)
else:
    if (x%100)**100<=x<=(x%100)**105:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
x=int(input())
if x>=2000:
    print("YES")
else:
    if (x%100)**100<=x<=(x%100)**105:
        print("YES")
    else:
        print("NO")

Submission status: Wrong Answer

Solution code:
x=int(input())
if x>=2100:
    print("YES")
else:
    if x%100<=5*(x//100):
        print("YES")
    else:
        print("NO")

Submission status: Wrong Answer

Solution code:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
X = int(input())

dp = {}
lis = [100,101,102,103,104,105]
que = deque([100,101,102,103,104,105])
while len(que)>0:
    num = que.popleft()
    for i in lis:
        dp[num+i] = 1
        if num+i <=1000 and not(num+i in que):
            que.append(num + i)

ans = 0
if X<100:
    ans = 0
elif 100<= X <106:
    ans = 1
elif 106<= X <1000:
    if X in dp:
        ans = dp[X]
    else:
        ans = 0
else:
    X = X%1000
    if X in dp:
        ans = dp[X]
    else:
        ans = 0

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Wrong Answer

Solution code:
x = int(input())
for i in range(-(-x//100)):
    if i*100 <= x <= i*105:
        print(1)
        break
else:
    print(0)

Submission status: Wrong Answer

Solution code:
x = int(input())
r = range(x//100)
for i in r:
    for j in r:
        for k in r:
            for l in r:
                for m in r:
                    for n in r:
                        a = 100*i + 101*j + 102*k + 103*l + 104*m + 105*n
                        if a > x: continue
                        if a == x:
                            print(1)
                            break
                    else: continue
                    break
                else: continue
                break
            else: continue
            break
        else: continue
        break
    else: continue
    break
else:
    print(0)

Submission status: Wrong Answer

Solution code:
x = int(input())
num = x // 100
amr = x % 100
if num*5 < amr:
  ans = "No"
else:
  ans = "Yes"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
def main(x):
    dp = [0] * x
    dp[0] = 1
    for i in range(x):
        if i - 1 in [100, 101, 102, 103, 104, 105]:
            dp[i] = 1
            continue
        if 0 <= i - 105:
            dp[i] = max(dp[i], dp[i - 105])
        if 0 <= i - 104:
            dp[i] = max(dp[i], dp[i - 104])
        if 0 <= i - 103:
            dp[i] = max(dp[i], dp[i - 103])
        if 0 <= i - 102:
            dp[i] = max(dp[i], dp[i - 102])
        if 0 <= i - 101:
            dp[i] = max(dp[i], dp[i - 101])
        if 0 <= i - 100:
            dp[i] = max(dp[i], dp[i - 100])
    return dp[x - 1]


x = int(input())
print(main(x))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
def main(x):
    dp = [0] * x
    for i in range(x):
        if i - 1 in [100, 101, 102, 103, 104, 105]:
            dp[i] = 1
            continue
        if 0 <= i - 105:
            dp[i] = max(dp[i], dp[i - 105])
        if 0 <= i - 104:
            dp[i] = max(dp[i], dp[i - 104])
        if 0 <= i - 103:
            dp[i] = max(dp[i], dp[i - 103])
        if 0 <= i - 102:
            dp[i] = max(dp[i], dp[i - 102])
        if 0 <= i - 101:
            dp[i] = max(dp[i], dp[i - 101])
        if 0 <= i - 100:
            dp[i] = max(dp[i], dp[i - 100])
    return dp[x - 1]


x = int(input())
print(main(x))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
def main(x):
    p = [100, 101, 102, 103, 104, 105]
    dp = [[0 for j in range(100001)] for i in range(6)]
    for i in range(6):
        if i == 0:
            dp[i][0] = 1
            dp[i][p[i]] = 1
            continue
        for j in range(100001):
            if 0 <= j - p[i] < 100001 and dp[i - 1][j - p[i]] == 1:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[- 1][x]

x = int(input())
print(main(x))