Problem:


Problem B: Hating Crowd

Problem

ニート君は1年12ヶ月毎月30日まで計360日の世界線で暮らしています。その世界では毎年同じ日程のN個の連休が世界中の人に適用されていました。連休iはMi月Di日から始まる連続したVi日間です。

ニート君はNEETなので連休に関係なく毎日休みです。ある日ニート君は珍しく出かけようと思いましたが、人混みが嫌いなので、連休の影響で混雑する日はなるべく外に出たくありません。そこで、ニート君は以下の方法で各日の混雑度を計算し、混雑度が一番小さい日を探そうとしています。

  

    
ある日付xが、連休iによって受ける影響の度合を表す数値は、日付xが連休iの中に含まれていればSiであり、そうでなければ、 max( 0,  Si &minus; min (   xから連休iの初日までの日数 , 連休iの最終日からxまでの日数    ) )である

    
ある日付xの混雑度は、N個の連休から受ける影響の度合の中で、最も大きく受ける影響の度合となる

  

  

1年の中で一番小さい混雑度を出力してください。 ただし、連休iは年を跨ぐ事があります。また、連休の日程は重複する事があります。

Input

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

N
M1 D1 V1 S1
M2 D2 V2 S2
...
MN DN VN SN

    1行目に整数Nが与えられる。

    2行目からN+1行目に整数Mi, Di, Vi, Siが空白区切りで与えられる。（1 ≤ i ≤ N）

Constraints

入力は以下の条件を満たす。

  
1 ≤ N ≤ 100

  
1 ≤ Mi ≤ 12

  
1 ≤ Di ≤ 30

  
1 ≤ Vi, Si ≤ 360

Output

 一番小さい混雑度を1行に出力する。

Sample Input 1

1
1 1 359 1

Sample Output 1

0

Sample Input 2

2
2 4 25 306
1 9 7 321

Sample Output 2

158

Sample Input 3

8
2 9 297 297
8 6 359 211
8 16 28 288
7 9 113 143
3 18 315 190
10 18 277 300
9 5 276 88
3 5 322 40

Sample Output 3

297



Sample input:
1
1 1 359 1


Sample output:
0

Submission status: Accepted

Solution code:
D = 360
x = [0 for i in range(D)]

n = int(input())
for i in range(n):
    m,d,v,s = map(int,input().split())
    m -= 1
    d -= 1

    start = 30*m+d
    end = (start+v-1)%D
    h = [False for _ in range(D)]
    for j in range(v):
        y = (start+j)%D
        h[y] = True

    for j in range(D):
        if h[j]:
            x[j] = max(x[j],s)
        else:
            A = abs(start-j)
            if A>D//2:
                A = D-A
            B = abs(end-j)
            if B>D//2:
                B = D-B
            x[j] = max(x[j], s-min(A,B))

print(min(x))

Submission status: Accepted

Solution code:
n = int(input())
eff = [0]*360
days = [list(map(int, input().split())) for i in range(n)]

for m, d, v, s in days:
    # [a, b)
    a = (m-1)*30 + d - 1
    b = a + v
    for i in range(a, b):
        eff[i%360] = max(eff[i%360], s)
    for i in range(b, a+360):
        eff[i%360] = max(eff[i%360], s - min(i - b + 1, 360 + a - i))
print(min(eff))

Submission status: Accepted

Solution code:

N = input()
N = int(N)+1
X = [0]
C = [0]*360

for i in range(1,N):
    x = input()
    X.append(x.split())
    i_start = (int(X[i][0])-1)*30+int(X[i][1])-1
    i_end = i_start+int(X[i][2])-1

    for j in range(i_start,i_end+1):
        C[j%360] = max(C[j%360],int(X[i][3]))

    for k in range(1,int(X[i][3])+1):
        C[(i_start-k+360)%360] = max(C[(i_start-k+360)%360],int(X[i][3])-k)
        C[(i_end+k)%360] = max(C[(i_end+k)%360],int(X[i][3])-k)

print(min(C))