3

SPOJ の Web サイトを発見し、問題に対する最初の解決策を提出しました: Alphacode http://www.spoj.com/problems/ACODE/

オンライン審査員は、次のコードで NZEC エラーを返しました。理由がわかりません。Python 3.2.3 (functools.lru_cache は Python3.2 で登場) を選択し、lru_cache を削除して memoize デコレーターに置き換えようとしましたが、同じ問題が発生しました。

from functools import lru_cache

@lru_cache(maxsize=10000)
def acode(s, i=0):
    if i == len(s):
        return 1
    if s[i] == "0":
        return 0
    res = acode(s, i+1)
    if i + 1 < len(s) and (10 * int(s[i]) + int(s[i+1]) <= 26):
        res += acode(s, i+2)
    return res

def main():
    i = input().strip()
    while i != "0":
        print(acode(i))
        i = input().strip()

if __name__ == "__main__":
    import sys
    try:
        main()
    except:
        sys.exit(0)

次のコマンドでテストできます。

$ echo "123\n1111\n21\n0" | python3 acode.py

注: 私も「try: except:」なしで送信しましたが、SPOJ Web サイトで出力ログを見つけることができません。

4

3 に答える 3

0

あなたのプログラムは NZEC を提供していないようです (少なくとも今は)。しかし、それは WA コードで救済されます。

しかし、LRU キャッシュを使用する代わりに、動的計画法を使用して配列を明示的にロールダウンすると、受け入れられます

from functools import lru_cache


@lru_cache(maxsize=10000)
def acode(s, i=0):
    if i == len(s):
        return 1
    if s[i] == "0":
        return 0
    res = acode(s, i + 1)
    if i + 1 < len(s) and (10 * int(s[i]) + int(s[i + 1]) ≤ 26):
        res += acode(s, i + 2)
    return res


def acode_second_try(s):
    n = len(s)
    f = [0 for i in range(1 + n)]
    f[n] = 1
    for i in range(n - 1, -1, -1):
        if s[i] != '0':
            f[i] = f[1 + i]
            if 1 + i < n:
                if 10 * int(s[i]) + int(s[1 + i]) ≤ 26:
                    f[i] += f[2 + i]
    return f[0]


def main():
    i = input().strip()
    while i[0] != '0':
        print(acode_second_try(i))
        #print(acode(i))
        i = input().strip()

if __name__ == "__main__":
    import sys

    try:
        main()
    except:
        sys.exit(0)
于 2014-02-10T13:25:57.173 に答える