Отправлено: 09.09.22 12:53. Заголовок: №5460 (27.125) ошибка в решении

Здравствуйте!
Небольшой недочет: на картинке, которая приложена в пояснении к задаче, вместо точки со значением 19 нанесена точка со значением 1.

В алгоритме "27-125_4512.py" есть ошибка. Для данных:

 
 5 
 5 
 9 
 3 
 2 
 1 
 

алгоритм выдаст 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.

Автор не учитывает, что если получить сумму дуги меньше, чем идеальный вариант, то оставшаяся часть окружности будет тоже больше идеального варианта, и такая оставшаяся часть окружности может оказаться ближе к идеальному результату, чем те варианты, где изначально сумма дуги больше.

 Отправлено: 16.09.22 15:47. Заголовок: Согласен, замечание ..

Согласен, замечание справедливое.

Надо сделать двойной проход по кольцу, чтобы этот недочет убрать

for i in range(n*2): 
     k += a[i%n] 
     while k - a[st%n] >= best_s: 
         k -= a[st%n] 
         st += 1

 Отправлено: 16.09.22 21:44. Заголовок: Спасибо за обсуждени..

Спасибо за обсуждение, решение исправлено.