Форум » Обработка числовых последовательностей » №5460 (27.125) ошибка в решении » Ответить
№5460 (27.125) ошибка в решении
beep: Здравствуйте! Небольшой недочет: на картинке, которая приложена в пояснении к задаче, вместо точки со значением 19 нанесена точка со значением 1. В алгоритме "27-125_4512.py" есть ошибка. Для данных: [pre2] 5 5 9 3 2 1 [/pre2] алгоритм выдаст 1, что неверно. Правильный ответ 0. Проблема в том, что алгоритм не все варианты дуги просматривает. Будут учтены только следующие варианты: 5 = 5 5 + 9 = 14 9 + 3 = 12 9 + 3 + 2 = 14 9 + 3 + 2 + 1 = 15 Лучшим будет выбран результат 9 + 3, поскольку 12 наиболее близко к 10 из предложенных вариантов (путь равен 1). Но можно выбрать 9, тогда минимальный путь будет равен 0, а 11 ближе к 10, чем 12. Автор не учитывает, что если получить сумму дуги меньше, чем идеальный вариант, то оставшаяся часть окружности будет тоже больше идеального варианта, и такая оставшаяся часть окружности может оказаться ближе к идеальному результату, чем те варианты, где изначально сумма дуги больше.
Ответов - 2
EugeneJobs: Согласен, замечание справедливое. Надо сделать двойной проход по кольцу, чтобы этот недочет убрать [pre2]for i in range(n*2): k += a[i%n] while k - a[st%n] >= best_s: k -= a[st%n] st += 1[/pre2]
Поляков: Спасибо за обсуждение, решение исправлено.
полная версия страницы