Сообщение Почти Ханойские башни от 31.10.2016 9:31
Изменено 31.10.2016 18:03 olimp_20
Задача. Почти Ханойские башни
Лимит времени 1с.
Игровое поле представляет собой последовательность из N колонок по Ki фишек в каждой. За один ход с колонки с номером Ni можно забрать и переместить по m фишек в соседнюю левую и правую колонку. (2 * m ≤ Ki) С крайней левой и правой колонок разрешается перемещать фишки только в одну из соседних соответственно. Определите какое наименьшее количество разрешенных ходов нужно выполнить, чтобы в каждой колонке было равное количество фишек. Гарантируется что СУММ(Ki) / N всегда целое число.
входные данные
Первая строка входного файла содержит число N — количество колонок. В следующей строке записано Ki — количества фишек в каждой из колонок. (I принадлежит[1: N]) (2≤N≤200) (0≤Ki≤2000)
Исходные данные
Выходной файл должен содержать одно число — минимальное количество разрешенных ходов.
Моя идея решения:
Вопрос: 1) существует ли типичный алгоритм (по типу — дерево Фенвика, поиск в глубину и тп), решающий поиск количества ходов за допустимое время? или 2) придумывать эвристический алгоритм в соответствии условию задачи?
Лимит времени 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.Моя идея решения:
Для каждой колонки i
f(i)=f(i-1)+(min количество ходов для №i).Вопрос: 1) существует ли типичный алгоритм (по типу — дерево Фенвика, поиск в глубину и тп), решающий поиск количества ходов за допустимое время? или 2) придумывать эвристический алгоритм в соответствии условию задачи?
Задача. Почти Ханойские башни
Лимит времени 1с.
Игровое поле представляет собой последовательность из N колонок по Ki фишек в каждой. За один ход с колонки с номером Ni можно забрать и переместить по m фишек в соседнюю левую и правую колонку. (2 * m ≤ Ki) С крайней левой и правой колонок разрешается перемещать фишки только в одну из соседних соответственно. Определите какое наименьшее количество разрешенных ходов нужно выполнить, чтобы в каждой колонке было равное количество фишек. Гарантируется что СУММ(Ki) / N всегда целое число.
входные данные
Первая строка входного файла содержит число N — количество колонок. В следующей строке записано Ki — количества фишек в каждой из колонок. (I принадлежит[1: N]) (2≤N≤200) (0≤Ki≤2000)
Исходные данные
Выходной файл должен содержать одно число — минимальное количество разрешенных ходов.
Моя идея решения:
Вопрос: как быстрее можно получить ответ задачи?
Лимит времени 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.Моя идея решения:
Для каждой колонки i (слева направо)
f1(i)=f1(i-1)+(количество ходов для №i).
Для каждой колонки i (справа налево)
f2(i)=f2(i-1)+(количество ходов для №i).
answ = min(f1, f2)Вопрос: как быстрее можно получить ответ задачи?