Chefstr2.py — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<source lang="python"> import math def main(): symbols = {} alphabet = "abcdefghijklmnopqrstuvwxyz" for i in range(26): symbols[alphabet[i…») |
StasFomin (обсуждение | вклад) |
||
| (не показано 10 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
<source lang="python"> | <source lang="python"> | ||
| − | |||
| − | |||
| − | |||
def main(): | def main(): | ||
symbols = {} | symbols = {} | ||
alphabet = "abcdefghijklmnopqrstuvwxyz" | alphabet = "abcdefghijklmnopqrstuvwxyz" | ||
| − | for i in range( | + | lenalf = len(alphabet) |
| + | |||
| + | for i in range(lenalf): | ||
symbols[alphabet[i]] = i | symbols[alphabet[i]] = i | ||
| + | |||
input_str = input() | input_str = input() | ||
| − | |||
n = len(input_str) | n = len(input_str) | ||
| − | + | ||
| + | input_idx = bytearray([symbols[ch] for ch in input_str]) | ||
| + | |||
operations = 1e6 | operations = 1e6 | ||
k_pow = 1e6 | k_pow = 1e6 | ||
ind = 1 | ind = 1 | ||
| − | lim = | + | lim = 0.55 * n |
while ind <= lim: | while ind <= lim: | ||
| − | + | ks = -(n // -ind) | |
| − | ks = | + | |
| − | for i in | + | 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 operations == cur_diff: | + | if cur_diff < operations: |
| + | operations = cur_diff | ||
| + | k_pow = ks | ||
| + | elif operations == cur_diff: | ||
if ks < k_pow: | if ks < k_pow: | ||
k_pow = ks | k_pow = ks | ||
| − | |||
| − | |||
| − | |||
ind += 1 | ind += 1 | ||
| − | print(f"{ | + | 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()