Problem:


MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});

B: 重さの範囲

問題

重さの異なる $N$ 色のボールがキューにたくさん入っています。キューには、先頭から
$1,2,3, \dots ,N-1,N,1,2,3, \dots ,N-1,N,1,2,3, \dots$ というふうに昇順にボールが並んでいて、
色 $N$ のボールの後ろにはまた色 $1$ のボールから順に入っています。
同じ色のボールはそれぞれ同じ重さであり、色 $i$ のボールの重さは $A_i$ です。

この状態から、キューの先頭からボールを $M$ 個取り出し、これを 1 つのグループとする作業を繰り返します。
そして、キューから取り出した各色のボールの総数がすべて等しくなったときにグループを作る作業をやめます。
なお、キューには十分な数のボールが入っており、グループを作る作業をやめるまでにキューの中身が空になることはありません。

たとえば、
$N=8, M=2$ のとき、{色1,色2}, {色3,色4}, {色5,色6}, {色7,色8} の 4 グループができます
(このとき各色のボールは 1 つずつ存在する)。
$N=4, M=3$ のとき、{色1,色2,色3}, {色4,色1,色2}, {色3,色4,色1}, {色2,色3,色4} の $4$
グループができます (このとき各色のボールはそれぞれ3つずつ存在する)。

このとき、各グループにおいて、
含まれるボールの重さの最大値と最小値の差をそのグループの重さの範囲と呼ぶことにします。
各グループの重さの範囲の総和を出力してください。

制約

$1 \le N \le 1000$

$1 \le M \le N$

$0 \le A_i \le 100$

入力は全て整数である

入力形式

入力は以下の形式で与えられます。

$N \ M$

$A_1 \cdots A_N$

出力

答えを 1 行で出力してください。また、末尾に改行も出力してください。

サンプル

サンプル入力 1

8 2
23 61 57 13 91 41 79 41

サンプル出力 1

170

重さの範囲の総和は $38+44+50+38=170$ となります。

サンプル入力 2

4 3
72 46 67 5

サンプル出力 2

222

重さの範囲の総和は $26+67+67+62=222$ となります。

サンプル入力 3

4 2
1 2 3 5

サンプル出力 3

3

重さの範囲の総和は $1+2=3$ となります。



Sample input:
8 2
23 61 57 13 91 41 79 41


Sample output:
170

Submission status: Memory Limit Exceeded

Solution code:
N, M = map(int, input().split())
As = list(map(int, input().split())) * N * M

rd = 0
c = 1
N_ = N * c
while(N_ % M != 0):
    c += 1
    N_ = c * N 
rd = N_ // M

ls = []
cnt = 0
for i in range(rd):
    lstmp = []
    for j in range(M):
        lstmp.append(As[cnt])
        cnt += 1
    ls.append(lstmp)

s = 0
for i in ls:
    s += max(i)-min(i)
print(s)

Submission status: Accepted

Solution code:
# AOJ 2806: Weight Range
# Python3 2018.7.11 bal4u

def gcd(a, b):
	while b != 0:
		r = a % b
		a, b = b, r
	return a

N, M = map(int, input().split())
a = list(map(int, input().split()))
a.extend(a)
step = gcd(N, M)
group = N // step;
ans = 0
for i in range(group):
	k = i*step
	mi = ma = a[k];
	for j in range(1, M):
		mi = min(mi, a[k+j])
		ma = max(ma, a[k+j])
	ans += ma-mi
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(i) for i in input().split()]

l = 0
ans = 0

while l % N != 0 or l == 0:
    min_ = 101
    max_ = -1

    for i in range(l, l + M):
        min_ = min(min_, A[i % N])
        max_ = max(max_, A[i % N])

    ans += max_ - min_
    l += M

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,m = LI()
    a = LI()
    r = 0
    i = 0
    while True:
        mi = ma = a[i%n]
        for j in range(1,m):
            t = a[(i+j)%n]
            if mi > t:
                mi = t
            elif ma < t:
                ma = t
        r += ma-mi
        i += m
        if i % n == 0:
            break
    return r

print(main())

Submission status: Accepted

Solution code:
def GCD(a, b):
    while(b):
        a, b = b, a % b
    return(a)

def LCM(a, b):
    return(a * b // GCD(a, b))

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    lcm = LCM(N, M)
    l = []
    if(N != lcm):
        for i in range(lcm // N):
            for j in range(N):
                l.append(A[j])
    else:
        l = A
    ans = 0
    for i in range(lcm // M):
        temp = []
        for j in range(M):
            temp.append(l[M * i + j])
        ans += max(temp) - min(temp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
i = 0
ans = 0
while True:
    t_min = float('inf')
    t_max = 0
    for j in range(m):
        t = a[i % n]
        t_min = min(t_min, t)
        t_max = max(t_max, t)
        i += 1
    ans += t_max - t_min
    if i % n == 0:
        break
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
As = list(map(int, input().split()))

rd = 0
c = 1
N_ = N * c
while(N_ % M != 0):
    c += 1
    N_ = c * N 
rd = N_ // M

As = As * (N_//N + 1)

ls = []
cnt = 0
for i in range(rd):
    lstmp = []
    for j in range(M):
        lstmp.append(As[cnt])
        cnt += 1
    ls.append(lstmp)

s = 0
for i in ls:
    s += max(i)-min(i)
print(s)

Submission status: Accepted

Solution code:
def list_eq(get_num, first):
    if first == 1:
        return False
    for i in range(len(get_num)-1):
        if get_num[0] != get_num[i+1]:
            return False
    return True

a_raw = input().split(' ')
b_raw = input().split(' ')
a = [int(n) for n in a_raw]
b = [int(n) for n in b_raw]


get_num = [0 for _ in range(a[0])]
first=1
next_num=0
res=0

while list_eq(get_num, first) == False:
    first=0
    weight = []
    for i in range(a[1]):
        weight.append(b[next_num])
        get_num[next_num] += 1
        next_num+=1
        if next_num > a[0]-1:
            next_num = 0
    res+=max(weight)-min(weight)
print(res)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
A = list(map(int, input().split()))
a = [0]*M
count = 0
weight = 0
while count != N:
    #print("count=",count)
    for i in range(M):
        if N-1 < count:
            count = 0
        a[i] = A[count]
        count += 1 
    sa = max(a) - min (a)
    #print("a=",a," sa=",sa)
    weight += sa
print(weight)

Submission status: Accepted

Solution code:
import math
n,m=map(int,input().split())
a=list(map(int,input().split()))*2
gr=n//math.gcd(n,m)
ans=0
for i in range(gr):
    test=[]
    for j in range(m):
        test.append(a[(i*m+j)%n])
    test.sort()
    ans+=test[-1]-test[0]
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
n, m = map(int, input().split())
alst = list(map(int, input().split()))
loop = m // gcd(n, m)
alst = alst * loop
ans = 0
for i in range(0, loop * n, m):
  ans += max(alst[i:i+m]) - min(alst[i:i+m])
print(ans)

Submission status: Accepted

Solution code:
import math

n, m = map(int, input().split())
ball = list(map(int, input().split()))

lcm = n * m // math.gcd(n, m)

ans = 0
for i in range(lcm // m):
    data = []
    for j in range(m):
        d = ball[(i*m+j) % len(ball)]
        data.append(d)
    ans += (max(data) - min(data))

print(ans)