Записи в блоге

Примечание к задаче

"Хватайте конфеты" — это простая и в то же время интересная задача на логику, которая является второй из соревнования Codeforces Round 859 (Div. 4)

Условия к задаче

данные

Имя входного файла: Стандартный ввод / input.txt

Имя выходного файла: Стандартный вывод / output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Условие

Михай и Бьянка играют с мешочками конфет. У них есть последовательность $$$a$$$ из $$$n$$$ мешочков с конфетами. В $$$i$$$ -м мешке $$$a_{i}$$$ конфет. Мешочки раздаются игрокам в порядке от первого до $$$n$$$ -го мешочка.

Если в мешке чётное количество конфет, то его хватает Михай. В противном случае его хватает Бьянка. Как только мешок схвачен, количество конфет в нём прибавляется к общему количеству конфет игрока, который его взял.

Михай хочет покрасоваться, поэтому он хочет изменить порядок массива так, чтобы в любой момент (кроме самого начала, когда у обоих нет конфет) у Михая было строго больше конфет, чем у Бьянки. Помогите Михаю выяснить, существует ли такой способ переставить мешочки.

Входные данные

Первая строка ввода содержит целое число $$$t$$$ (1 ≤ $$$t$$$ ≤ 1000 ) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ (1 ≤ $$$n$$$ ≤ 100 ) — количество мешков.

Вторая строка каждого набора входных данных содержит $$$n$$$ разделенных пробелами целых чисел $$$a_{i}$$$ (1 ≤ $$$a_{i}$$$ ≤ 100 ) — количество конфет в каждом мешке.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если такая перестановка существует, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример

входные данные

1 2 3 4

1 1 1 2

1 4 3

выходные данные

YES

Решение задачи

Ввод

Первым делом нам нужно организовать правильный ввод данных. В начале у нас вводится переменная t — сколько всего наборов входных данных. Дальше t раз вводится число n и n $$$a_{i}$$$ чисел в строку. Где n — количество мешков, а $$$a_{i}$$$ — количество конфет в мешке.

Чтобы ввести t наборов данных я буду использовать цикл for. А чтобы ввести n $$$a_{i}$$$ чисел в строку буду использовать конструкцию из функций list() и map().

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))

Алгоритм решения

Итак по условию задачи мы должны определить существует ли способ переставить мешочки так, чтобы у Михая в любой момент всегда было строго больше конфет чем у Бьянки кроме начала когда у них обоих по 0 конфет. Так как же определить существует способ или нет?

Так как мы знаем что Михай хватает мешки с чётным количеством конфет мы можем просто эти мешки условно переместить в начало, ведь тогда нам останется только проверить что сумма конфет в мешках с чётным количеством конфет больше суммы конфет в мешках с нечётным количеством конфет. Так как если это условие выполняется то мы сможем перетащить мешки так, чтобы у Михая было всегда больше конфет чем у Бьянки. Если же это условие не выполняется то способа переставить мешки так, чтобы у Михая было всегда больше конфет чем у Бьянки нет.

Итак чтобы считать конфеты которые находятся в мешках у Михая я завёл переменную s, а чтобы считать конфеты в мешках у Бьянки переменную d. Дальше я организую цикл for по массиву a. В цикле проверяю делимость количества конфет на 2, то есть на чётность и если число конфет в мешке чётное то я прибавляю число конфет к переменной s, а если нет то число конфет прибавляю к переменной d.

s = 0
d = 0    
for i in a:
    if i % 2 == 0:
        s += i
    else:
        d += i

Остаётся проверить условие что сумма конфет Михая больше суммы конфет Бьянки, если это условие верно то это значит, что способ переставить мешки с конфетами так, чтобы у Михая было всегда больше конфет кроме начала существует, следовательно вывожу "YES", иначе вывожу "NO".

В итоге мы получаем конечный код:

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = 0
    d = 0    
    for i in a:
        if i % 2 == 0:
            s += i
        else:
            d += i
    if s > d:
        print("YES")
    else:
        print("NO")

Вот и всё решение задачи.

Мой комментарий

Вот таким получился мой первый разбор. Надеюсь вам понравилось и было всё понятно и если это так то голосуйте плюсом за этот разбор. Если было что-то непонятно, есть предложения для дальнейших разборов, или есть интересная задача по которой вы хотите увидеть разбор, то обязательно пишите.

Всем Удачи!

Полный текст и комментарии »