結果

問題 No.10 +か×か
ユーザー yuki2006yuki2006
提出日時 2014-10-11 03:51:56
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 1,552 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2024-06-09 15:48:07
合計ジャッジ時間 4,500 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
6,816 KB
testcase_01 AC 10 ms
6,940 KB
testcase_02 AC 10 ms
6,944 KB
testcase_03 AC 1,259 ms
9,472 KB
testcase_04 AC 141 ms
7,040 KB
testcase_05 AC 10 ms
6,940 KB
testcase_06 WA -
testcase_07 AC 454 ms
8,448 KB
testcase_08 AC 110 ms
7,296 KB
testcase_09 WA -
testcase_10 AC 11 ms
6,940 KB
testcase_11 AC 11 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

# -*- coding: utf-8 -*-

def solve(N, total, A):
    MAX = (1 << N + 2)
    dp = [MAX] * (total + 1)
    # 結果をビットで保存するDP
    dp[A[0]] = 0

    for i, a in enumerate(A[1:]):
        for v in xrange(total, 0, -1):
            if dp[v] == MAX:
                continue

            current = dp[v]
            # 1倍の時に上書きされてしまう対策
            mul_change = False
            if v * a <= total:
                if i == 0:
                    dp[v * a] = (1 << ((N - 2) - i))
                    mul_change = True
                else:
                    if a == 1:
                        mul_change = True
                        dp[v * a] = current | (1 << ((N - 2) - i))
                    else:
                        dp[v * a] = min(dp[v * a], current | (1 << ((N - 2) - i)))

            if v + a <= total:
                if i == 0:
                    dp[v + a] = 0
                else:
                    dp[v + a] = min(dp[v + a], current)

            if not mul_change:
                # 1倍の時以外はMAXにする。
                # 1倍の時にすると値が消えてしまう。
                dp[v] = MAX

    ans_bit = dp[total]
    if ans_bit == MAX:
        return None
    ans = ""

    while N > 1:
        ans = ("*" if ans_bit & 1 else "+") + ans
        ans_bit >>= 1
        N -= 1
    return ans



N = int(raw_input())
total = int(raw_input())
A = map(int, raw_input().split(" "))

print solve(N, total, A)

0