Задача. Почти Ханойские башни
Лимит времени 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)
Здравствуйте, olimp_20, Вы писали:
_>Задача. Почти Ханойские башни _>Лимит времени 1с. _>Игровое поле представляет собой последовательность из N колонок по Ki фишек в каждой. За один ход с колонки с номером Ni можно забрать и переместить по m фишек в соседнюю левую и правую колонку. (2 * m ≤ Ki) С крайней левой и правой колонок разрешается перемещать фишки только в одну из соседних соответственно. Определите какое наименьшее количество разрешенных ходов нужно выполнить, чтобы в каждой колонке было равное количество фишек. Гарантируется что СУММ(Ki) / N всегда целое число.
Для вектора колонок K[1..n] определим вектор снятия фишек M[1..n]
За один ход в векторе должен быть ровно один ненулевой компонент. Но мы сперва посмотрим на суперпозицию.
Поскольку мы не можем делать отрицательные ходы, то нужно найти такой M1, чтобы все числа оказались неотрицательными.
Ну это понятно, находим минимальный Emin, получаем M1 = Emin/{1,2} в зависимости от того, что там был за множитель, и получаем итоговый вектор.
Итак, M = [0,4,18,38,28]
Если бы мы могли залезать в минусы на кучках, то достаточно было бы сделать ровно столько ходов, сколько у нас ненулевых компонентов.
0) [5,2,4,8,16]
1) снимаем 4 c K2, получаем [7,-2,6,8,16]
2) снимаем 18 c K3, получаем [7,7,-12,17,16]
3) снимаем 38 c K4, получаем [7,7,7,-21,35]
4) снимаем 28 c K5, получаем [7,7,7,7,7]
Но так нельзя, поэтому придётся с некоторых кучек снимать в несколько приёмов.
И вот это — задача для оптимизации. Я честно скажу: не знаю ещё, как к ней подойти. Может быть, строить дерево решений, а может, обычного градиентного спуска достаточно.
Понятно, что оценочная функция — это минимизировать сумму компонентов M, не реализованную после каждого шага.
К>Значит, нам надо найти вектор M — решить уравнение D = (Kend-Kbegin) = T*M К>где D — это сколько фишек нужно добавить-убавить в каждую колонку.
К>Применительно к демонстрационному примеру, К>Kbegin = [5,2,4,8,16] К>Kend = [7,7,7,7,7] К>D = [2,5,3,-1,-9]
Как видно из значений вектора D — фишки будут "переливаться" из 5, 4 столбца в левые 1, 2, 3.
То есть рассматриваю модель: колонки — сообщающиеся сосуды. Остается проблема: промоделировать "разбегание" фишек и заполнение уровней.
Кроме того, исходя из описания примера, удобно достраивать до значения 7, начиная от крайнего столбца и при этом соседний с ним равен 0.
К>Оказывается менее эффективно, чем эталонный ответ...
Тоже экспериментировал с наибольшим числом — иногда это очень усложняет, например для 8 16 5 4 2 или 2 16 5 4 8
Поэтому остановился на выборе левого или правого крайнего столбца. Эмпирически получил: чем меньше числа возле крайнего столбца, тем оптимальнее выбирать именно этот столбец. А вот как "подвести" теоретическую основу — не знаю...
Здравствуйте, olimp_20, Вы писали:
К>>D = [2,5,3,-1,-9]
_>Как видно из значений вектора D — фишки будут "переливаться" из 5, 4 столбца в левые 1, 2, 3. _>То есть рассматриваю модель: колонки — сообщающиеся сосуды. Остается проблема: промоделировать "разбегание" фишек и заполнение уровней. _>Кроме того, исходя из описания примера, удобно достраивать до значения 7, начиная от крайнего столбца и при этом соседний с ним равен 0.
К>>Оказывается менее эффективно, чем эталонный ответ...
_>Тоже экспериментировал с наибольшим числом — иногда это очень усложняет, например для 8 16 5 4 2 или 2 16 5 4 8 _>Поэтому остановился на выборе левого или правого крайнего столбца. Эмпирически получил: чем меньше числа возле крайнего столбца, тем оптимальнее выбирать именно этот столбец. А вот как "подвести" теоретическую основу — не знаю...
Во-первых, я бы не стал терять информацию о векторе M = [0,4,18,38,28].
Хочешь-не хочешь, а 38 фишек с четвёртой колонки снять придётся. Естественно, в несколько приёмов.
Во-вторых, короткие вектора не показательны. На длинном могут быть редкие островки далеко от краёв, над которыми только и требуется выполнить манипуляции.
И таких островков может быть несколько, т.е. встанет вопрос о выборе одного из локальных максимумов...
А что, если пойти с другой стороны.
Обратный ход: взять поровну из соседних колонок и сложить в центральную.
Исходное состояние — все колонки равны.
В каждую колонку надо положить M (это мы уже нашли), и это приведёт в конце к тому, от чего начинали в оригинальной задаче.
Будем отдавать предпочтения тем ходам, которые можно сделать сразу. Иначе — делать максимально возможный ход.
K 7 7 7 7 7
M 0 4 18 38 28
\ | / 2*min(7,7) >= 4 - завершающий ход! делаем!
4
K 5 11 5 7 7
M 0 0 18 38 28
\ | / 2*min(11,7)=14; 2*min(5,7)=10; 1*min(7)=7 - делаем наибольший
14
K 5 4 19 0 7
M 0 0 4 38 28
\ | / единственный возможный
14
K 5 4 12 14 0
M 0 0 4 24 28
\ | / завершающий
4
K 5 2 16 12 0
M 0 0 0 24 28
\ | единственно возможный
12
K 5 2 16 0 12
M 0 0 0 24 16
\ | / завершающий
24
K 5 2 4 24 0
M 0 0 0 0 16
\ | завершающий
16
K 5 2 4 8 16
M 0 0 0 0 0
Эталонное решение
K 7 7 7 7 7
M 0 4 18 38 28
\ | /
12
K 7 7 1 19 1
M 0 4 18 26 28
\ |
12
K 7 7 1 7 13
M 0 4 18 26 16
\ | /
14
K 7 0 15 0 13
M 0 4 4 26 16
\ | /
26
K 7 0 2 26 0
M 0 4 4 0 16
\ |
16
K 7 0 2 10 16
M 0 4 4 0 0
\ | /
4
K 5 4 0 10 16
M 0 0 4 0 0
\ | /
4
K 5 2 4 8 16
M 0 0 0 0 0
Что так, что этак 7 ходов.
Однако, надо показать, что мы не свалимся в локальный экстремум.
Как это доказать, я пока не представляю.
_>Вопрос: как быстрее можно получить ответ задачи?
Итак, текущий подход состоит в натурном эксперименте.
За O(n) находим вектор суперпозиции ходов M
Затем, тратим O(n) на каждый шаг, а количество шагов — не меньше, чем количество ненулевых компонентов в M, т.е. O(n) — итого, O(n^2).
Если завести приоритетную очередь, то нахождение максимального хода займёт O(log n). Но это ценой некоторой громоздкости. Вот не факт, что линейные забеги по массиву будут медленнее.
или
+M[2]/2 -M[3] +M[4]/2
К>То есть, получается матрица T c -1 на главной диагонали и +1 и +1/2 на соседних диагоналях.
Где "+1"?
К>Отсюда и темы про суперпозицию.
К>Значит, нам надо найти вектор M — решить уравнение D = (Kend-Kbegin) = T*M К>где D — это сколько фишек нужно добавить-убавить в каждую колонку.
К>Применительно к демонстрационному примеру, К>Kbegin = [5,2,4,8,16] К>Kend = [7,7,7,7,7] К>D = [2,5,3,-1,-9]
К>Система зависимая, все M[i] можно выразить как M[1]+E[i]*{1,2}.
Е[i] — единичная матрица типа:
100
010
001?
Почему в формуле всегда М[1]+... ?
К>Поскольку мы не можем делать отрицательные ходы, то нужно найти такой M1, чтобы все числа оказались неотрицательными. К>Ну это понятно, находим минимальный Emin, получаем M1 = Emin/{1,2} в зависимости от того, что там был за множитель, и получаем итоговый вектор.
Как вычисляется Emin?
К>Например, К>
К>K: 5 2 4 8 16
К>M: 0 4 18 38 28
К> -16 - раскидали наибольшее возможное значение
К>K: 5 2 4 24 0
К>M: 0 4 18 38 12
К> -24 - опять раскидали наибольшее значение
К>K: 5 2 16 0 12
К>M: 0 4 18 14 12
К> -12 - это обязательный ход, полностью сокращающий компоненту <-- на основе какого критерия выбор?
К>K: 5 2 16 12 0
К>M: 0 4 18 14 0
К> -16 - наибольшее
К>K: 5 10 0 20 0
К>M: 0 4 4 14 0
К> -14 - обязательное <-- на основе какого критерия выбор?
К>K: 5 10 7 6 7
К>M: 0 4 2 0 0
К> -4 - одно из двух обязательных <-- на основе какого критерия выбор?
К>K: 7 6 9 6 7
К>M: 0 0 2 0 0
К> -2 - второе из двух обязательных
К>K: 7 7 7 7 7
К>M: 0 0 2 0 0
К>
К>Оказывается менее эффективно, чем эталонный ответ...
В чем меньшая эффекттивность, если, как я понял , шагов тоже 7?
К>>Отсюда и темы про суперпозицию.
К>>Значит, нам надо найти вектор M — решить уравнение D = (Kend-Kbegin) = T*M К>>где D — это сколько фишек нужно добавить-убавить в каждую колонку.
К>>Система зависимая, все M[i] можно выразить как M[1]+E[i]*{1,2}. _>Е[i] — единичная матрица типа: _>100 _>010 _>001? _>Почему в формуле всегда М[1]+... ?
Потому что — почему бы и нет
Переобозначим D = [p,q,r,s,t], M = [a,2b,2c,2d,e] — поскольку серединные ходы чётные, удобно будет выразить их вот так.
p = -a+b
q = +a-2b+c
r = +b-2c+d
s = +c-2d+e
t = +d-e
0 = -a+a - допишем сюда для общей картины
p = -a+b
2p+q = -a+c
3p+2q+r = -a+d
4p+3q+2r+s = -a+e
Вот мы получили вектор E
Пусть в одном или нескольких уравнениях получили набежавшую сумму меньше нуля, u = -a+f, где u — сумма, f — одна из компонент M.
a >= 0, f >= 0
a = f-u
a >= -u
То есть, выберем a = -min(E) и на его основе получим все неотрицательные M = [a,2b,2c,2d,e] — помним про удвоение!
К>>Оказывается менее эффективно, чем эталонный ответ... _>В чем меньшая эффекттивность, если, как я понял , шагов тоже 7?
В моих кривых глазах. Почему-то прочитал, что оптимальное число ходов — 6
Перекуём баги на фичи!
