-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtestest.py
51 lines (40 loc) · 1.42 KB
/
testest.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
import sys
from math import sqrt
def sieve_of_eratosthenes_in_range(lower, upper):
full_sieve = [True] * (upper + 1)
full_sieve[0] = full_sieve[1] = False
for i in range(2, int(sqrt(upper)) + 1):
if full_sieve[i]:
for j in range(i * i, upper + 1, i):
full_sieve[j] = False
primes_in_range = [i for i in range(lower, upper + 1) if full_sieve[i]]
return primes_in_range
def find_least_penalty_and_order(nums):
nums.sort()
lower = nums[0] - 2 * len(nums)
upper = nums[-1] + 2 * len(nums)
primes = sieve_of_eratosthenes_in_range(lower, upper)
min_penalty = float('inf')
min_primes = None
for i in range(len(primes) - len(nums) + 1):
consecutive_primes = primes[i:i+len(nums)]
penalty = sum([abs(a - b) for a, b in zip(consecutive_primes, nums)])
if penalty < min_penalty:
min_penalty = penalty
min_primes = consecutive_primes
if min_penalty == 0:
break
return min_penalty, min_primes
path = '21395.txt'
sys.stdin = open(path, 'r')
input = sys.stdin.readline
import time
T = int(input())
min_penalty = sys.maxsize
start_time = time.time()
for _ in range(T):
n = int(input())
nums = list(map(int, input().split()))
min_penalty, ordered_primes = find_least_penalty_and_order(nums)
print( min_penalty)
print(time.time()-start_time )