Problem:


ニッシン館マラソン部

アイヅ市立ニッシン館は、文武両道を掲げる歴史ある学校です。ニッシン館マラソン部は熱血指導で有名であり、決められた練習時間の間、周回コースをひたすら走るという鬼の特訓を行います。このとき、脱水症状で倒れる部員がいないように、部員の実力に合わせて飲み物を提供する給水所を設けています。

各部員が１単位時間あたりに走れる距離(ペース)は部員ごとに決まっており、全員が１単位時間ごとに必ず給水できるように給水所を設けたうえで特訓を行います。部員は 1 単位時間で着いた給水所で必ず中身の入った容器を取り、そのまま走り続けます。さらに、次の１単位時間で着いた給水所で空の容器を置き、中身の入った容器を取って走り続けるということを繰り返します。また、空の容器は、置いてから 1 単位時間の時点で飲料が補充され、その瞬間から誰にでも提供できるようになります。

部員は全員同じ地点から、容器を持たずに出発します。決められた練習時間まで走ると練習を終えます(このときも給水が必要です)。複数の部員が同時に同じ給水所に到着する場合もあるので、一か所の給水所で同時に複数の容器が必要になることもあります。

鬼の特訓を安全に行うために、最低いくつの給水容器が必要になるか求めるプログラムを作成してください。

入力

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

N R T
p1
p2
:
pN

１行目に部員の数 N (1 ≤ N ≤ 100)、周回コースの長さ R (1 ≤ R ≤ 1000)、決められた練習時間 T (1 ≤ T ≤ 1000) が与えられる。続く N 行に、部員 i のペース pi (1 ≤ pi ≤ 1000) が与えられる。

出力

最低いくつの給水容器が必要になるかを１行に出力する。

入出力例

入力例１ 

1 10 20
1

出力例１

11

入力例２ 

2 5 12
1
2

出力例２

8



Sample input:
1 10 20
1


Sample output:
11

Submission status: Accepted

Solution code:
n, r, t = map(int, input().split())
speed = [int(input()) for _ in range(n)]
point = [0] * n
bottle = [0] * r
for i in range(n):
  point[i] = (point[i] + speed[i]) % r
  bottle[point[i]] += 1
for _ in range(t - 1):
  nums = [0] * r
  for i in range(n):
    bottle[point[i]] -= 1
    point[i] = (point[i] + speed[i]) % r
    nums[point[i]] += 1
  for i in range(r):
    if bottle[i] < nums[i]:
      bottle[i] = nums[i]
    bottle[i] += nums[i]
print(sum(bottle))

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


N,LEN,LIMIT = map(int,input().split())

speed = [None]*N
loc = [None]*N
num_fill = [0]*LEN
num_empty = [0]*LEN

ans = N

#時刻1の状態にする
for i in range(N):
    speed[i] = int(input())
    loc[i] = speed[i]

for current in range(2,LIMIT+1):

    for i in range(LEN):
        num_fill[i] += num_empty[i]
        num_empty[i] = 0

    for i in range(N):
        loc[i] += speed[i]
        loc[i] %= LEN
        num_empty[loc[i]] += 1
        if num_fill[loc[i]] > 0:
            num_fill[loc[i]] -= 1
        else:
            ans += 1 #元々あったことにする

print("%d"%(ans))