Problem:


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

D: スキャナー / Scanner

問題文

ここに $N$ 枚の紙がある。あなたは $3$ 台のスキャナーを並列に用いることで、
全ての紙をスキャンしたいと考えている。それぞれの紙はスキャンにかかる時間が決まっており、
$i$ 番目の紙をスキャンするのにかかる時間は $T_i$ である。
紙をスキャンする順番は任意であるが、$1$ 台のスキャナーで複数の紙を同時にスキャンすることはできない。

全ての紙のスキャンが終了し、スキャンを行っているスキャナーがなくなるまでにかかる時間を最小化しなさい。

入力

$N$

$T_1$

$T_2$

$T_3$

$\vdots$

$T_N$

制約

$1 \leq N \leq 50$

$1 \leq T_i \leq 50$

入力は全て整数

出力

答えを $1$ 行で出力してください．

サンプル

サンプル入力1

4
1
1
1
1

サンプル出力1

2

サンプル入力2

9
15
20
27
4
10
7
34
30
36

サンプル出力2

61

サンプル入力3

6
20
18
46
16
9
48

サンプル出力3

55



Sample input:
4
1
1
1
1


Sample output:
2

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

T.sort(reverse = True)

machine = [0, 0, 0]
for t in T:
    no = machine.index(min(machine))
    machine[no] += t

print(max(machine))

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
dp=[[1<<20]*850 for _ in [0]*850]
dp[0][0]=0
t=[int(input()) for _ in[0]*n]
s=sum(t)
for i,j,k in itertools.product(range(n),range(s//3+1),range(s//2+1)):
    dp[j][k]+=t[i]
    if t[i]<=j and dp[j][k]>dp[j-t[i]][k]:dp[j][k]=dp[j-t[i]][k]
    if t[i]<=k and dp[j][k]>dp[j][k-t[i]]:dp[j][k]=dp[j][k-t[i]]
a=1<<20
for i,j in itertools.product(range(s//3+1),range(s//2+1)):
    if dp[i][j]!=1<<20:a=min(a,max(i,j,s-i-j))
print(a)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
dp=[[1<<30]*850 for _ in [0]*850]
dp[0][0]=0
t=[int(input()) for _ in[0]*n]
s=sum(t)
for i,j,k in itertools.product(range(n),range(s//3+1),range(s//2+1)):
    dp[j][k]+=t[i]
    if t[i]<=j and dp[j][k]>dp[j-t[i]][k]:dp[j][k]=dp[j-t[i]][k]
    if t[i]<=k and dp[j][k]>dp[j][k-t[i]]:dp[j][k]=dp[j][k-t[i]]
a=1<<30
for i,j in itertools.product(range(s//3+1),range(s//2+1)):
    a=min(a,max(i,j,s-i-j))
print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
ts = [int(input()) for i in range(N)]
ts.sort()
ts.reverse()
s = [0, 0, 0]
for t in ts:
    min_index = s.index(min(s))
    s[min_index] += t
print(max(s))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
dp=[[1<<20]*850 for _ in [0]*850]
dp[0][0]=0
t=[int(input()) for _ in[0]*n]
for i,j,k in itertools.product(range(n),range(849,-1,-1),range(849,-1,-1)):
    dp[j][k]+=t[i]
    if t[i]<=j and dp[j][k]>dp[j-t[i]][k]:dp[j][k]=dp[j-t[i]][k]
    if t[i]<=k and dp[j][k]>dp[j][k-t[i]]:dp[j][k]=dp[j][k-t[i]]
a=1<<20
for i,j in itertools.product(range(850),range(850)):
    a=min(a,max([i,j,dp[i][j]]))
print(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ts = [int(input()) for i in range(N)]
ts.sort()
ts.reverse()
s = [[[0 for i in range(1000)] for j in range(1000)] for k in range(50)]
for i in range(N):
    for j in range(1000):
        for k in range(1000):
            p = [s[i][j][k] + ts[i]]
            if(j >= ts[i]):
                p.append(s[i][j - ts[i]][k])
            if(k >= ts[i]):
                p.append(s[i][j][k - ts[i]])
            s[i + 1][j][k] = min(p)
i = 0
while True:
    if(s[N][i][i] <= i):
        break
    i += 1
print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ts = [int(input()) for i in range(N)]
ts.sort()
ts.reverse()
ma = sum(ts) // 3 + 50
s = [[[0 for i in range(ma)] for j in range(ma)] for k in range(N + 1)]
for i in range(N):
    for j in range(ma):
        for k in range(ma):
            p = [s[i][j][k] + ts[i]]
            if(j >= ts[i]):
                p.append(s[i][j - ts[i]][k])
            if(k >= ts[i]):
                p.append(s[i][j][k - ts[i]])
            s[i + 1][j][k] = min(p)
i = 0
while True:
    if(s[N][i][i] <= i):
        break
    i += 1
print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ts = [int(input()) for i in range(N)]
ma = sum(ts) // 3 + 50
s = [[[0 for i in range(ma)] for j in range(ma)] for k in range(N + 1)]
for i in range(N):
    for j in range(ma):
        for k in range(j, ma):
            p = [s[i][j][k] + ts[i]]
            if(j >= ts[i]):
                p.append(s[i][j - ts[i]][k])
            if(k >= ts[i]):
                p.append(s[i][j][k - ts[i]])
            s[i + 1][j][k] = s[i + 1][k][j] = min(p)
i = 0
while True:
    if(s[N][i][i] <= i):
        break
    i += 1
print(i)