結果
問題 | No.453 製薬会社 |
ユーザー |
![]() |
提出日時 | 2022-01-05 15:23:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,494 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 52,608 KB |
最終ジャッジ日時 | 2024-10-15 20:10:31 |
合計ジャッジ時間 | 1,505 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 9 |
ソースコード
def make_tableau(A, b, c):m = len(A)n = len(A[0])tableau = []for i in range(m):row = A[i] + [int(j == i) for j in range(m)] + [b[i]]tableau.append(row)row = c + [0] * (m + 1)tableau.append(row)return tableaudef pivot_index(tableau):cN = tableau[-1][:-1]piv_col = -1for col, x in enumerate(cN):if x > 0:piv_col = colbreakif piv_col == -1:return False, -1, -1a = [tableau[i][piv_col] for i in range(len(tableau) - 1)]b = [tableau[i][-1] for i in range(len(tableau) - 1)]thetas = [bi / ai if ai > 0 else float('inf') for ai, bi in zip(a, b)]piv_row = thetas.index(min(thetas))return True, piv_row, piv_coldef step(tableau, piv_row, piv_col):h = len(tableau)w = len(tableau[0])piv = tableau[piv_row][piv_col]for j in range(w):tableau[piv_row][j] /= pivfor i in range(h):if i == piv_row:continued = tableau[i][piv_col]for j in range(w):tableau[i][j] -= d * tableau[piv_row][j]def simplex(A, b, c):tableau = make_tableau(A, b, c)while True:improved, piv_row, piv_col = pivot_index(tableau)if not improved:breakstep(tableau, piv_row, piv_col)return -tableau[-1][-1]C, D = map(int, input().split())A = [[3 / 4, 2 / 7],[1 / 4, 5 / 7]]b = [C, D]c = [1000, 2000]print(simplex(A, b, c))