Editing 2068 - kpal (section)

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(Sigma, Q, Cost):
    # Restrictiile impuse
    if not (1 <= Sigma <= 26 and 0 <= Q <= 1000000000):
        return False
    for i in range(Sigma):
        for j in range(Sigma):
            if i != j and not (1 <= Cost[i][j] <= 10000):
                return False
    return True

def main():
    with open("kpalIN.txt", "r") as f:
        Sigma = int(f.readline().strip())
        if Sigma > 26:  # Verificare pentru Sigma
            with open("kpalOUT.txt", "w") as out_file:
                out_file.write("Datele nu corespund restrictiilor impuse\n")
            return
        Cost = [list(map(int, f.readline().split())) for _ in range(Sigma)]
        cuvant = f.readline().strip()
        Q = int(f.readline().strip())

    if not verifica_restrictii(Sigma, Q, Cost):
        with open("kpalOUT.txt", "w") as f:
            f.write("Datele nu corespund restrictiilor impuse\n")
        return

    INF = 1000000000
    CostMatch = [[0] * 30 for _ in range(30)]
    Price = [0] * 300
    Count = [0] * 300

    for i in range(Sigma):
        for j in range(Sigma):
            CostMatch[i][j] = INF
            for k in range(Sigma):
                CostMatch[i][j] = min(CostMatch[i][j], Cost[i][k] + Cost[j][k])

    N = len(cuvant)
    StackSize = 0

    for lung in range(1, N + 1):
        if N % lung != 0:
            continue

        current_price = 0
        for i in range(N // lung):
            left = i * lung
            right = left + lung - 1
            while left < right:
                current_price += CostMatch[ord(cuvant[left]) - ord('a')][ord(cuvant[right]) - ord('a')]
                right -= 1
                left += 1

        while StackSize > 0 and Price[StackSize - 1] >= current_price:
            StackSize -= 1
        Count[StackSize] = N // lung
        Price[StackSize] = current_price
        StackSize += 1

    while StackSize > 0 and Price[StackSize - 1] > Q:
        StackSize -= 1
    Price[StackSize] = Q + 1

    answer = 0
    for i in range(StackSize):
        answer += (Price[i + 1] - Price[i]) * Count[i]

    with open("kpalOUT.txt", "w") as f:
        f.write(str(answer) + '\n')

if __name__ == "__main__":
    main()

</syntaxhighlight>