Решение задачи Перемещение фишек с Codeforces

Без пояснения   Просмотров: 23


Вам задано n фишек на числовой прямой. i-я фишка располагается в целочисленной координате xi. Некоторые фишки могут иметь одинаковые координаты.

Вы можете совершать любой из следующих двух типов ходов любое (возможно, нулевое) количество раз над любой фишкой:

Переместить фишку i на 2 влево или на 2 вправо бесплатно (то есть заменить текущую координату xi на xi−2 или xi+2);
переместить фишку i на 1 влево или на 1 вправо и заплатить одну монету за этот ход (то есть заменить текущую координату xi на xi−1 или xi+1).
Заметьте, что разрешается перемещать фишки в любые целочисленные координаты, включая нулевую и отрицательные.

Ваша задача — найти минимальное суммарное количество монет, необходимое для того, чтобы переместить все n фишек в одну координату (то есть после какой-то последовательности ходов все xi должны быть равны).

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, k = 0, t;
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> t;
        if(t % 2)
            ++k;
    }
    cout << min(k, n - k);
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться