Chefstr2.py - История изменений

StasFomin в 23:55, 4 мая 2022

2022-05-04T23:55:26Z

2022-05-04T23:37:22Z

2022-05-04T23:18:47Z

2022-05-04T22:59:52Z

2022-05-04T22:02:51Z

2022-05-04T21:53:29Z

2022-05-04T21:48:09Z

2022-05-04T21:40:04Z

2022-05-04T21:37:20Z

2022-05-04T21:30:18Z

@@ Строка 16: / Строка 16: @@
      k_pow = 1e6
      ind = 1
-     lim = 3 * n / 4
+     lim = 0.55 * n
      while ind <= lim:
          ks = -(n // -ind)
@@ Строка 41: / Строка 41: @@
          ind += 1
      print(f"{operations} {k_pow}")
 main()
 </source>

@@ Строка 1: / Строка 1: @@
 <source lang="python">
 def main():
      symbols = {}
@@ Строка 10: / Строка 8: @@
          symbols[alphabet[i]] = i
-     input_str = sys.stdin.readline()[:-1]
+     input_str = input()
      n = len(input_str)

@@ Строка 20: / Строка 20: @@
      lim = 3 * n / 4
      while ind <= lim:
          ks = -(n // -ind)
-         for i in range(ind):
-            frequency = {}
+        frequency = [0] * lenalf*ind
-            max_frequency = 0
+        max_frequency = [0]*ind
              j = i
-             while j < n:
+         for i, idx in enumerate(input_idx):
-                cur_freq = frequency.get(input_idx[j], 0) + 1
+             j = i % ind
-                if cur_freq > max_frequency:
+             i_ = j*lenalf + idx
-                    max_frequency = cur_freq
+            cur_req = frequency[i_] + 1
-                frequency[input_idx[j]] = cur_freq
+            if cur_req > max_frequency[j]:
-                j += ind
+                max_frequency[j] = cur_req
-            cur_diff += ks - max_frequency
+            frequency[i_] = cur_req
          if cur_diff < operations:

@@ Строка 23: / Строка 23: @@
          ks = -(n // -ind)
          for i in range(ind):
-             frequency = [0] * lenalf
+             frequency = {}
              max_frequency = 0
              j = i
              while j < n:
-                 cur_freq = frequency[input_idx[j]] + 1
+                 cur_freq = frequency.get(input_idx[j], 0) + 1
                  if cur_freq > max_frequency:
                      max_frequency = cur_freq

@@ Строка 24: / Строка 24: @@
          for i in range(ind):
              frequency = [0] * lenalf
              j = i
              while j < n:
-                 frequency[input_idx[j]] += 1
+                 cur_freq = frequency[input_idx[j]] + 1
                  j += ind
-             cur_diff += ks - max(frequency)
+             cur_diff += ks - max_frequency
          if cur_diff < operations:

@@ Строка 30: / Строка 30: @@
              cur_diff += ks - max(frequency)
-         if operations == cur_diff:
+         if cur_diff < operations:
-            if ks < k_pow:
-                k_pow = ks
-        elif cur_diff < operations:
              operations = cur_diff
              k_pow = ks
          ind += 1
      print(f"{operations} {k_pow}")

@@ Строка 15: / Строка 15: @@
      input_idx = bytearray([symbols[ch] for ch in input_str])
      operations = 1e6
      k_pow = 1e6
@@ Строка 24: / Строка 23: @@
          ks = -(n // -ind)
          for i in range(ind):
-             for j in range(lenalf):
+             frequency = [0] * lenalf
-                frequency[j] = 0
              j = i
              while j < n: