Решение задачи Перемещение фишек с Codeforces
Без пояснения   Просмотров: 93
Вам задано n фишек на числовой прямой. i-я фишка располагается в целочисленной координате xi. Некоторые фишки могут иметь одинаковые координаты.
Вы можете совершать любой из следующих двух типов ходов любое (возможно, нулевое) количество раз над любой фишкой:
Переместить фишку i на 2 влево или на 2 вправо бесплатно (то есть заменить текущую координату xi на xi−2 или xi+2);
переместить фишку i на 1 влево или на 1 вправо и заплатить одну монету за этот ход (то есть заменить текущую координату xi на xi−1 или xi+1).
Заметьте, что разрешается перемещать фишки в любые целочисленные координаты, включая нулевую и отрицательные.
Ваша задача — найти минимальное суммарное количество монет, необходимое для того, чтобы переместить все n фишек в одну координату (то есть после какой-то последовательности ходов все xi должны быть равны).
Вы можете совершать любой из следующих двух типов ходов любое (возможно, нулевое) количество раз над любой фишкой:
Переместить фишку i на 2 влево или на 2 вправо бесплатно (то есть заменить текущую координату xi на xi−2 или xi+2);
переместить фишку i на 1 влево или на 1 вправо и заплатить одну монету за этот ход (то есть заменить текущую координату xi на xi−1 или xi+1).
Заметьте, что разрешается перемещать фишки в любые целочисленные координаты, включая нулевую и отрицательные.
Ваша задача — найти минимальное суммарное количество монет, необходимое для того, чтобы переместить все n фишек в одну координату (то есть после какой-то последовательности ходов все xi должны быть равны).