Почти Ханойские башни
От: olimp_20  
Дата: 31.10.16 09:31
Оценка: 5 (1)
Задача. Почти Ханойские башни
Лимит времени 1с.
Игровое поле представляет собой последовательность из N колонок по Ki фишек в каждой. За один ход с колонки с номером Ni можно забрать и переместить по m фишек в соседнюю левую и правую колонку. (2 * m ≤ Ki) С крайней левой и правой колонок разрешается перемещать фишки только в одну из соседних соответственно. Определите какое наименьшее количество разрешенных ходов нужно выполнить, чтобы в каждой колонке было равное количество фишек. Гарантируется что СУММ(Ki) / N всегда целое число.
входные данные
Первая строка входного файла содержит число N — количество колонок. В следующей строке записано Ki — количества фишек в каждой из колонок. (I принадлежит[1: N]) (2≤N≤200) (0≤Ki≤2000)
Исходные данные
Выходной файл должен содержать одно число — минимальное количество разрешенных ходов.
Input.txt    Output.txt
5            7
5 2 4 8 16

Примечание
колонка 3 берем по 2, колонка 2 берем по 2, колонка 5 берем 16, колонка 4 берем по 13, колонка 3 берем по 7, колонка 5 берем 12, колонка 4 берем по 6.

Моя идея решения:
Дано:
1) вектор фишек v={5 2 4 8 16}
2) maxFish = СУММ(Ki);

Алгоритм:
"взвесить" левую left и правую right половины вектора вычислив для каждой стороны suma(v[i]-maxFish ) / N
 если left<right тогда
    Для каждой колонки i (слева направо)
          f(i)=f(i-1)+(количество ходов для №i).
 иначе
    Для каждой колонки i (справа налево)
          f(i)=f(i-1)+(количество ходов для №i).
answ = f(n)



Вопрос: как быстрее можно получить ответ задачи?
Отредактировано 31.10.2016 18:44 olimp_20 . Предыдущая версия . Еще …
Отредактировано 31.10.2016 18:43 olimp_20 . Предыдущая версия .
Отредактировано 31.10.2016 18:42 olimp_20 . Предыдущая версия .
Отредактировано 31.10.2016 18:40 olimp_20 . Предыдущая версия .
Отредактировано 31.10.2016 18:03 olimp_20 . Предыдущая версия .
Отредактировано 31.10.2016 14:14 olimp_20 . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.