Форум » Обработка числовых последовательностей » №5316 (27.120) ошибка в решении » Ответить
№5316 (27.120) ошибка в решении
beep: Здравствуйте! В одном из решений в файле "27-120_shastin.py" есть следующая ошибка: [pre2] F = open('27-120a.txt') N = int(F.readline()) line = '' for i in range(N): x = F.readline().strip() if x == '1': line += '_' if len(line) > 2 and line[-3:] == '___': line = line[:-3] + '..#..' else: line += '.' line = line.split('#') count = 0 for s in line: count += (((len(s) * (len(s) + 1))) - (len(s) * (len(s) + 1))%2)//2 print(count - len(line) + 1) [/pre2] Решение не учитывает вариант, когда подряд может идти больше трех единиц, например: [pre2] 7 2 3 1 1 1 1 2 [/pre2] Правильный ответ 17, алгоритм выдает 19. Связано это с неправильной заменой подстроки: [pre2] # неправильно line = line[:-3] + '..#..' # правильно line = line[:-3] + '..#__' [/pre2] Еще один момент заключается в том, что для вычисления количества вариантов используется странная формула, в которой есть лишнее вычитаемое: [pre2] count += (((len(s) * (len(s) + 1))) - (len(s) * (len(s) + 1))%2)//2 [/pre2] При любом s (четном или нечетном) оно всегда дает 0, какой-то смысл в этом вычитаемом отсутствует, а сама формула подсчета вариантов это формула суммы чисел от 1 до n (в ней тоже нет этого вычитаемого).
Ответов - 4
beep: Более того, для того, чтобы подсчитывать количество вариантов не при каждом шаге, а только на "стыках", не нужно использовать строку, как это сделано в двух последних предложенных решениях в этом файле. Достаточно просто сохранять предыдущий стык. Использование строки только запутывает решение, как мне кажется. [pre2] n = None checker = 0 count = 0 iPrev = -1 with open('27-120b.txt') as f: n = int(f.readline()) for i, x in enumerate(f): x = int(x) if x == 1: checker += 1 else: checker = 0 if checker == 3: amount = i - 1 - iPrev count += amount * (amount + 1) // 2 - 1 checker = 2 iPrev = i - 2 amount = n - 1 - iPrev count += amount * (amount + 1) // 2 print(count) [/pre2]
beep: ап
leo26011: Здравствуйте! Это решение просто забыл удалить из файла. Ниже верное (на строках; оно было сделано "забавы ради"). Спасибо, файл поправим!
Поляков: Решение заменено. Спасибо за замечание.
полная версия страницы