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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<source lang="python"> import math def main(): symbols = {} alphabet = "abcdefghijklmnopqrstuvwxyz" for i in range(26): symbols[alphabet[i…»)
 
Строка 1: Строка 1:
 
<source lang="python">
 
<source lang="python">
import math
 
 
 
 
def main():
 
def main():
 
     symbols = {}
 
     symbols = {}
Строка 9: Строка 6:
 
         symbols[alphabet[i]] = i
 
         symbols[alphabet[i]] = i
 
     input_str = input()
 
     input_str = input()
    k = int(input())
 
 
     n = len(input_str)
 
     n = len(input_str)
     frequency = [0.0 for i in range(26)]
+
     frequency = [0 for i in range(26)]
 
     operations = 1e6
 
     operations = 1e6
 
     k_pow = 1e6
 
     k_pow = 1e6
Строка 18: Строка 14:
 
     while ind <= lim:
 
     while ind <= lim:
 
         cur_diff = 0
 
         cur_diff = 0
         ks = math.ceil(float(n) / float(ind))
+
         ks = -(n // -ind)  
 
         for i in range(ind):
 
         for i in range(ind):
 
             for j in range(26):
 
             for j in range(26):
                 frequency[j] = 0.0
+
                 frequency[j] = 0
 
             j = i
 
             j = i
 
             while j < n:
 
             while j < n:
Строка 35: Строка 31:
 
             k_pow = ks
 
             k_pow = ks
 
         ind += 1
 
         ind += 1
     print(f"{int(operations)} {k_pow}")
+
     print(f"{operations} {k_pow}")
 
   
 
   
 
   
 
   
 
main()
 
main()
 
</source>
 
</source>

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

def main():
    symbols = {}
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    for i in range(26):
        symbols[alphabet[i]] = i
    input_str = input()
    n = len(input_str)
    frequency = [0 for i in range(26)]
    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):
            for j in range(26):
                frequency[j] = 0
            j = i
            while j < n:
                frequency[symbols[(input_str[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()