-
Notifications
You must be signed in to change notification settings - Fork 0
/
1145.py
34 lines (32 loc) · 847 Bytes
/
1145.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
from math import sqrt
def isPrime(n):
if n < 2:
return False
for i in range(2,int(sqrt(n))+1):
if n % i == 0:
return False
return True
Msize,n,m = map(int,input().split())
number = list(map(int,input().split()))
query = list(map(int,input().split()))
cnt = 0
while isPrime(Msize) == False:
Msize += 1
HASH = [-1 for i in range(Msize)]
for key in number:
flag = True
for i in range(Msize):
location = (key + i*i) % Msize
if HASH[location] == -1:
HASH[location] = key
flag = False
break
if flag:
print("%d cannot be inserted."%key)
for key in query:
for i in range(Msize+1):
cnt+=1
location = (key + i*i) % Msize
if HASH[location] == -1 or HASH[location] == key:
break
print("%.1f"%(cnt/m))