Chefstr2.py — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 15: Строка 15:
 
     input_idx = bytearray([symbols[ch] for ch in input_str])
 
     input_idx = bytearray([symbols[ch] for ch in input_str])
  
    frequency = [0 for i in range(lenalf)]
 
 
     operations = 1e6
 
     operations = 1e6
 
     k_pow = 1e6
 
     k_pow = 1e6
Строка 24: Строка 23:
 
         ks = -(n // -ind)  
 
         ks = -(n // -ind)  
 
         for i in range(ind):
 
         for i in range(ind):
             for j in range(lenalf):
+
             frequency = [0] * lenalf
                frequency[j] = 0
+
 
             j = i
 
             j = i
 
             while j < n:
 
             while j < n:

Версия 21:48, 4 мая 2022

import sys
 
def main():
    symbols = {}
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    lenalf = len(alphabet)
 
    for i in range(lenalf):
        symbols[alphabet[i]] = i
 
    input_str = sys.stdin.readline()[:-1]
    n = len(input_str)
 
    input_idx = bytearray([symbols[ch] for ch in input_str])
 
    operations = 1e6
    k_pow = 1e6
    ind = 1
    lim = 3 * n / 4
    while ind <= lim:
        cur_diff = 0
        ks = -(n // -ind) 
        for i in range(ind):
            frequency = [0] * lenalf
            j = i
            while j < n:
                frequency[input_idx[j]] += 1
                j += ind
            cur_diff += ks - max(frequency)
 
        if operations == cur_diff:
            if ks < k_pow:
                k_pow = ks
        elif cur_diff < operations:
            operations = cur_diff
            k_pow = ks
        ind += 1
    print(f"{operations} {k_pow}")
 
 
main()