Есть на просторах интернета сайт для школьников с задачками про программированию. Пишешь программу, загружаешь ответ, получаешь оценки. Типа leetcode, только отечественный.
Задачки там в целом простые, рассчитанные не на гиков, которые готовятся к собеседованию в FAANG, а на школьников, которые только-только делают первые шаги в программировании. Некоторые задачки решаются программой буквально из двух строчек, первая их которых читает параметры с клавиатуры. Но иногда...
Даны числа M и N, причём гарантируется, что M<N. Требуется вывести частное M/N в виде десятичной дроби. Если дробь периодическая, то период заключить в скобки. Например: 1/2 → 0,5; 4/700 → 0,00(571428)
При всей кажущейся простоте задачка отнюдь не для начинающих программистов, хотя для опытного разработчика её решение никаких проблем не составляет. Оторвав от пола левую пятку, я написал примерно следующее:
#!/usr/bin/env python
(M,N) = map(int,input().split())
rem = {}
(ps, pe) = (0,0)
M *= 10
rc = "0,"
while True:
pe += 1
(q,r) = divmod(M,N)
M = r*10
k = str(q)+"."+str(r)
if k in rem: # такой остаток уже был, значит, это период
ps = rem[k]
break
rem[k] = pe
rc += str(q)
if r==0: break # дробь конечная
if ps!=0: rc = rc[:ps+1]+"("+rc[ps+1:]+")"
print(rc)
Загрузил решение на сайт. Часть тестов была успешно пройдена, а другая получила «ошибку выполнения».
Тут надо сказать пару слов про систему проверки. Программе выдаётся некое количество ресурсов — 64 мегабайта памяти и 2 секунды времени. Результатом выполнения может быть одна из четырёх строк:
- OK — если программа корректно отработала и выдала верный результат;
- Неверный результат — если программа коректно отработала, но результат неверный;
- Ошибка времени выполнения — если код завершения отличен от 0;
- Превышено время выполнения — ну, понятно.
Никаких «отладочных print’ов» не предусмотрено. В FAQ русским по белому написано «тестовые примеры не покажем, учитесь отлаживать методом пристального взгляда». И что-то мне стало так обидно...
Методом дихотомического обкладывания назных кусков кода конструкциями try .. except я выяснил, что программе не хватает памяти. Что ж, это вызов...
Первое, что я сделал, это вывел отдельно непериодическую часть. Количество цифр в непериодической части равно тому, сколько раз знаменатель делится на 2 и 5 (точнее, максимуму из этих чисел; например, если знаменатель делится на 1600=52×26, то длина непериодической части будет max(2,6)=6). После того, как это сделано, достаточно сохранять не пару частное+остаток, а только остаток. Мало того, не нужно сохранять его позицию, достаточно просто флага, что такой остаток был.
Получается, в ассоциативном массиве rem чуть более короткий ключ и можно логическое значение вместо целого, но памяти всё равно не хватает. Вместо ассоциативного массива попробовал множество, но и оно занимало слишком много памяти. Попробовал массив с остатками, но в нём надо держать остатки сортированными, а это получалось очень медленно. В конце концов нашёлся крайне эффективный тип bytearray — это реально массив байт! Получается, каждый остаток можно хранить одним битиком, и теперь с памятью всё стало хорошо, но несколько примеров всё равно не укладывались в отведённое время.
Следующим этапом выяснилось, что операции со строками тоже отнимают много времени, и накапливать циферки в питоновских строках неэффективно. Что ж, давайте и для строк тоже использовать bytearray. А если вспомнить, что последовательность байт — сама по себе строка, и для вывода на печать не нужно всякой питоновской магии, программа стала работать ещё быстрее. Но на одном из тестов времени ей всё равно не хватало.
Опытным путём я выяснил, что сайт подаёт на вход восьмизначный знаменатель. Интересный момент заключается в том, что время расчёта периода для двух чисел с разностью 2 может отличаться на порядок, потому что длина периода разная. Например, моя конечная программа прямо сейчас на незагруженной машине пример 4/99999991 обрабатывает за 0.07 секунды, 4/99999997 — за 1.2 секунды, а 4/99999993 — за 22 секунды. Исходная программа на последнем примере уходит в себя на несколько часов и сжирает несколько гигабайт памяти, ответа я от неё так и не дождался. Кстати, быстро определить длину периода нельзя, хотя я пытался сделать и это тоже, включая вариант поиска периода по строке, в которой записаны цифры искомой дроби.
В общем, вот окончательный вариант, который проходит 31 тест из 32. Кто может, пусть сделает лучше. И да, на код десятиклассника это не очень похоже.
#!/usr/bin/env python
from sys import stdout
IOBUF_SIZE = 4096
(M,N) = map(int,input().split())
# сокращаем дробь
(n1, n2) = (M, N)
while n1!=0 and n2!=0:
if n1>n2: n1 %= n2
else: n2 %= n1
M //= n1+n2
N //= n1+n2
stdout.write("0,")
# nn - "приведённый" знаменатель, т. е. без множителей 2 и 5
(nn,divisor) = (N,10)
iobuf = bytearray(IOBUF_SIZE)
iox = 0
while True:
M *= 10
q = M//N
M %= N
qq = nn//divisor
rr = nn%divisor
if rr==0:
nn = qq
elif divisor==10:
if rr==5:
nn = qq+qq+1
divisor = 5
rr = 0
elif rr in (2,4,6,8):
nn = qq*5+rr//2
divisor = 2
rr = 0
if rr!=0: break # дробь периодическая
iobuf[iox] = q+48
if (iox := iox+1)==IOBUF_SIZE:
stdout.write(iobuf)
iox = 0
if nn==1:
stdout.write(iobuf[:iox].decode("ascii"))
stdout.write("\n")
exit(0) # дробь конечная
# сюда будем складывать остатки
rem = bytearray(1+(N>>3))
rem[M>>3] |= (1<<(M&7))
stdout.write(iobuf[:iox].decode("ascii"))
stdout.write("("+str(q))
iox = 0
while True:
M *= 10
q = M//N
M %= N
(r1,r2) = (M>>3,1<<(M&7))
if rem[r1] & r2!=0:
stdout.write(iobuf[:iox].decode("ascii"))
stdout.write(")\n")
break
rem[r1] |= r2
iobuf[iox] = q+48
if (iox := iox+1)==IOBUF_SIZE:
stdout.write(iobuf.decode("ascii"))
iox = 0
P. S. А потом выяснилось, что на этом сайте ограничения по памяти и быстродействию одинаковые для всех языков программирования — и для Python, и для C. Вот тут-то мне, как говорится, фишка и попёрла. Неберущийся пример был решён за 0.05 секунды...
