Chefstr2.py — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
<source lang="python"> | <source lang="python"> | ||
| − | |||
| − | |||
def main(): | def main(): | ||
symbols = {} | symbols = {} | ||
| Строка 10: | Строка 8: | ||
symbols[alphabet[i]] = i | symbols[alphabet[i]] = i | ||
| − | input_str = | + | input_str = input() |
n = len(input_str) | n = len(input_str) | ||
| Строка 18: | Строка 16: | ||
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 = -(n // -ind) | ||
| Строка 43: | Строка 41: | ||
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()