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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
<source lang="python">
 
<source lang="python">
import sys
 
 
 
def main():
 
def main():
 
     symbols = {}
 
     symbols = {}
Строка 10: Строка 8:
 
         symbols[alphabet[i]] = i
 
         symbols[alphabet[i]] = i
 
      
 
      
     input_str = sys.stdin.readline()[:-1]
+
     input_str = input()
 
     n = len(input_str)
 
     n = len(input_str)
  
 
     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
 
     ind = 1
 
     ind = 1
     lim = 3 * n / 4
+
     lim = 0.55 * n  
 
     while ind <= lim:
 
     while ind <= lim:
        cur_diff = 0
 
 
         ks = -(n // -ind)  
 
         ks = -(n // -ind)  
         for i in range(ind):
+
 
            for j in range(lenalf):
+
         frequency = [0] * lenalf*ind              
                frequency[j] = 0
+
        max_frequency = [0]*ind
             j = i
+
 
             while j < n:
+
        for i, idx in enumerate(input_idx):
                frequency[input_idx[j]] += 1
+
             j = i % ind
                 j += ind
+
             i_ = j*lenalf + idx
             cur_diff += ks - max(frequency)
+
            cur_req = frequency[i_] + 1
 +
            if cur_req > max_frequency[j]:
 +
                 max_frequency[j] = cur_req
 +
             frequency[i_] = cur_req               
 +
 
 +
        cur_diff = ks*ind - sum(max_frequency)
 
   
 
   
         if operations == cur_diff:
+
         if cur_diff < operations:
            if ks < k_pow:
+
                k_pow = ks
+
        elif cur_diff < operations:
+
 
             operations = cur_diff
 
             operations = cur_diff
 
             k_pow = ks
 
             k_pow = ks
 +
        elif operations == cur_diff:
 +
            if ks < k_pow:
 +
                k_pow = ks
 
         ind += 1
 
         ind += 1
 
     print(f"{operations} {k_pow}")
 
     print(f"{operations} {k_pow}")
 
 
   
 
   
 
main()
 
main()
 
</source>
 
</source>

Текущая версия на 23:55, 4 мая 2022

def main():
    symbols = {}
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    lenalf = len(alphabet)
 
    for i in range(lenalf):
        symbols[alphabet[i]] = i
 
    input_str = input()
    n = len(input_str)
 
    input_idx = bytearray([symbols[ch] for ch in input_str])
 
    operations = 1e6
    k_pow = 1e6
    ind = 1
    lim = 0.55 * n 
    while ind <= lim:
        ks = -(n // -ind) 
 
        frequency = [0] * lenalf*ind                
        max_frequency = [0]*ind
 
        for i, idx in enumerate(input_idx):
            j = i % ind
            i_ = j*lenalf + idx
            cur_req = frequency[i_] + 1
            if cur_req > max_frequency[j]:
                max_frequency[j] = cur_req
            frequency[i_] = cur_req                
 
        cur_diff = ks*ind - sum(max_frequency)
 
        if cur_diff < operations:
            operations = cur_diff
            k_pow = ks
        elif operations == cur_diff:
            if ks < k_pow:
                k_pow = ks
        ind += 1
    print(f"{operations} {k_pow}")
 
main()