Chefstr2.py — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показано 8 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
<source lang="python"> | <source lang="python"> | ||
| − | |||
| − | |||
def main(): | def main(): | ||
symbols = {} | symbols = {} | ||
| Строка 9: | Строка 7: | ||
for i in range(lenalf): | for i in range(lenalf): | ||
symbols[alphabet[i]] = i | symbols[alphabet[i]] = i | ||
| − | input_str = | + | |
| + | 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 = -(n // -ind) | ||
| − | + | ||
| − | + | frequency = [0] * lenalf*ind | |
| − | + | max_frequency = [0]*ind | |
| − | j = i | + | |
| − | + | for i, idx in enumerate(input_idx): | |
| − | + | j = i % ind | |
| − | j | + | i_ = j*lenalf + idx |
| − | cur_diff | + | 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 | + | if 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()