PPaste!

solutions by other candidates

Home - All the pastes - Authored by Thooms

Raw version

 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
# Solution1

n = int(input())
k = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()
ps = [0]
for i in range(n):
    ps.append(ps[-1] + a[i])
cur = 0
for i in range(k):
    cur += i * a[i] - ps[i]
ans = cur
for i in range(1, n - k + 1):
    cur -= ps[i + k - 1] - ps[i - 1] - k * a[i - 1]
    cur += k * a[i + k - 1] - ps[i + k] + ps[i]
    ans = min(ans, cur)
print(ans)

# ============================================
#solution2

def unfairness(packets, K):
    un = 0
    sump = sum(packets)
    for i in range(K):
        sump -= packets[i]
        un += sump - (K - i - 1) * packets[i]
    return un

def calculateSum(packets):
    s = [0] * len(packets)
    s[0] = packets[0] 
    for i in range(1, len(packets)):
        s[i] = s[i - 1] + packets[i]
    return s

import sys
N = int(sys.stdin.readline().rstrip())
K = int(sys.stdin.readline().rstrip())

packets = []
for i in range(N):
    packets.append(int(sys.stdin.readline().rstrip()))

packets.sort()
sump = calculateSum(packets)

#print(unfairness([10, 20, 30], 3))
#print(unfairness([1, 2, 3, 4], 4))
current_unfairness = unfairness(packets[0:K], K)
min_unfairness = current_unfairness

for i in range(1, N - K + 1):
    suma = sump[i + K - 2] - sump[i - 1]
    dodaj = abs((K - 1) * packets[i + K - 1] - suma)
    oduzmi = abs((K - 1) * packets[i - 1] - suma)
    current_unfairness = current_unfairness + dodaj - oduzmi
    if current_unfairness < min_unfairness:
        min_unfairness = current_unfairness
print(min_unfairness)

#====================================
#solution3

from operator import add
from functools import reduce

def sum_difference(array):
	res = 0
	k = len(array)
	for i in range(k):
		res += (2 * i - k + 1) * array[i]
	return res

N = int(input())
K = int(input())

packets = [int(input()) for i in range(N)]

packets.sort()

s = sum_difference(packets[0:K])

mini = s
alpha = sum(packets[0:K-1])
for i in range(0,N-K):
	alpha = alpha - packets[i] + packets[i+K-1]
	s = s - 2 * alpha + (K-1)*(packets[i] + packets[i+K])
	if s < mini:
		mini = s
print(mini)