結果

問題 No.515 典型LCP
ユーザー matsu7874matsu7874
提出日時 2017-05-05 23:39:31
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 965 bytes
コンパイル時間 774 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 31,416 KB
最終ジャッジ日時 2024-09-14 09:20:13
合計ジャッジ時間 5,194 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def next_query(n, x, d):
    i = (x // (n-1))
    j = (x % (n-1))
    if i > j:
        i, j = j, i
    else:
        j += 1
    x = (x+d) % (n * (n-1))
    return i, j, x

def lcp(a,b):
    size_a =  len(a)
    size_b =  len(b)
    size = min(size_a, size_b)
    for i in range(size):
        if a[i] != b[i]:
            return i
    return size


def main():
    n = int(input())
    s = []
    for i in range(n):
        s.append(input().strip())
    m, x, d = map(int, input().split())
    total = 0
    for _ in range(min(m, n*(n+1))):
        i, j, x = next_query(n, x, d)
        total += lcp(s[i], s[j])
        # print(total, lcp(s[i], s[j]))
    if m <= n*(n+1):
        print(total)
        exit()
    
    total *= m // (n*(n+1))
    # print(total)
    for _ in range(m % (n*(n+1))):
        i, j, x = next_query(n, x, d)
        total += lcp(s[i], s[j])
        # print(total, lcp(s[i], s[j]))

    print(total)

if __name__ == '__main__':
    main()
0