-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathstamps.py
102 lines (73 loc) · 2.21 KB
/
stamps.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
c,q =list(map(int, input().split(" ")))
clusters=list(map(int,input().split(" ")))
def isImpossible(need):
return bfs(need)
class ClusterState:
def __init__(self, s,a):
self.arr=a
self.sum=s
def bfs(need):
queue=[]
# queue.add(clusters[0])
# queue.add(clusters[len(clusters)-1])
# initial = clusters.copy()
# intital2=clusters.copy()
first=clusters[0]
last=clusters[len(clusters)-1]
# initial.pop(0)
queue.append(ClusterState(last,clusters[:-1]))
queue.append(ClusterState(first,clusters[1:]))
# clusters.pop(len(clusters)-1)
while len(queue)>0:
state=queue.pop()
if state.sum==need:
return True
elif state.sum<need:
arr1=state.arr
if (len(state.arr)==0):
if state.sum==need:
return True
continue
sum=state.sum+arr1[0]
sum2=state.sum+arr1[len(arr1)-1]
if sum==need or sum2==need:
return True
if sum<need:
# /arr1.pop(0)
# queue.append(ClusterState(sum, arr1))
if (len(arr1[1:])>0):
queue.append(ClusterState(sum, arr1[1:]))
# arr3.pop(len(arr3)-1)
# queue.append(ClusterState(sumP, arr3))
if sum2<need:
if (len(arr1[:-1])>0):
queue.append(ClusterState(sum2, arr1[:-1]))
return False
res=[]
sums=sum(clusters)
def fastSearch(need):
total=0
if clusters[0]+clusters[len(clusters)-1]==need:
return True
for i in range(len(clusters)):
total+=clusters[i]
if total> need:
return False
if total==need:
return True
for i in range(q):
query=int(input())
if query==sums:
res.append("Yes")
elif query==0:
res.append("Yes")
elif fastSearch(query):
res.append("Yes")
else:
val=isImpossible(query)
if val:
res.append("Yes")
else:
res.append("No")
for i in range(q):
print(res[i])