1. Hádam prežijeme zimu vzorové riešenie

6
1 2 3 4 5 6
5 6 7 8 9 5

nie

3
2 8 64
57 20 3

ano

Riešenie hrubou silou

Priamočiare riešenie je prejsť všetkými výmenami, ktoré existujú a overiť, či by k nim mohlo dôjsť. Takže skúsime vymeniť každú Gabikinu kôpku guliek postupne s každou Timkinou kôpkou. Pre každú výmenu musíme overiť, či sa môže uskutočniť, teda či majú obe párny súčet všetkých svojich guličiek. Toto by sme mohli overiť tak, že pre každú výmenu sčítame počty guliek na každej kôpke postupne pre Gabiku aj Timku a tento súčet zmodulujeme dvoma. Uvedomme si, že toto vôbec nemusíme robiť, stačí nám raz spočítať zvlášť súčet Gabikiných a Timkiných guliek ešte predtým ako budeme prechádzať výmenami. Pri skúšaní konkrétnej výmeny nám potom stačí Gabike odčítať počet guliek v kôpke, čo dáva Timke a pričítať počet guliek v kôpke, ktorú dostáva od Timky. Toto číslo následne vydelíme dvoma, aby sme zistili, či má Gabika párny počet guliek. To isté spravíme s Timkiným počtom guličiek, odrátame guličky, ktoré dáva Gabike a prirátame tie, ktoré od nej dostáva a vydelíme dvoma. Ak sú oba súčty deliteľné dvoma, zistili sme, že k výmene dôjde a môžeme ukončiť skúšanie. Ak je aspoň jeden nepárny, tak musíme skušať ďalšie výmeny.

Časová zložitosť tohto riešenia je \(O(n^2)\), pretože každú z \(n\) Gabikiných kôpok guličiek skúsime vymeniť s \(n\) Timkinými kôpkami guličiek a vrámci jednej výmeny robíme len jednoduché aritmetické operácie. V dvoch poliach si pamätáme \(n\) Gabikiných a \(n\) Timkiných kôpok a okrem toho iba pomocné premenné, takže pamäťová zlozitisť je \(O(n)\).

Vzorové riešenie

Na vylepšenie predchádzajúceho riešenia si musíme uvedomiť ako sa správajú párne a nepárne čísla pri súčte. Keď sčítame čísla rovnakej parity, sučet bude párny a keď sčítame čísla opačnej parity dostaneme číslo nepárne. Rovnako to platí aj pri rozdieli. Podľa týchto pravidiel vieme na základe parity súčtov všetkých guliek hovniválok povedať, kedy dôjde k výmene. Pripomeňme si ešte, čo sa stane keď príde k výmene medzi Timkou a Gabikou. Timka aj Gabika jednu kôpku darujú, teda odráta sa počet guliek, ktoré obsahovala a jednu dostanú, teda priráta sa jej počet guličiek. Poďme si teraz rozobrať možné prípady výmeny. Povedzme, že Gabika má súčet svojich guliek \(g\) a Timka \(t\).

Ak \(g\) a \(t\) sú rôznej parity, napríklad \(g\) je párne a \(t\) nepárne (opačný prípad sa správa rovnako), tak k výmene nedôjde. Potrebovali by sme totiž zmeniť paritu \(t\). Podľa toho, čo sme si povedali na začiatku vieme, že musíme k \(t\) prirátať párne číslo a odrátať nepárne alebo prirátať nepárne a odrátať párne. Ako sa pri týchto výmenách správalo \(g\)? Buď sme k nemu pripočítali nepárne číslo a odčítali od neho párne alebo opačne, každopádne sme zmenili jeho paritu na nepárnu.

Ak sú \(g\) aj \(t\) párne k výmene dôjde za istých podmienok. Oba súčty sú párne a teda im nechceme zmeniť paritu, to vieme, že sa stane ak ich zmeníme o párne číslo, teda buď pripočítame a odpočítame párne čísla alebo pripočítame a odpočítame nepárne čísla. Minimálne jeden z týchto prípadov vieme spraviť práve vtedy, keď Gabika má aspoň jednu kôpku rovnakej parity ako Timka. Inak sa výmena nemôže uskutočniť.

Ak sú \(g\) a \(t\) nepárne tiež môže nastať výmena. Keďže sú oba súčty nepárne potrebujeme im obom zmeniť paritu. Vieme, že nepárne číslo zmeníme na párne súčtom alebo rozdielom s nepárnym číslom. Od oboch čísel teda potrebujeme odpočítať číslo jednej parity a pripočítať k nemu číslo druhej parity. Toto v našej úlohe vieme spraviť ak má Gabika aspoň jednu kôpku s počtom guličiek rôznej parity ako aspoň jedna Timkina kôpka. Keď si vymenia túto dvojicu kôpok nastane presne tá situácia, ktorú potrebujeme. Inak k výmene nemôže dôjsť.

Celé riešenie vieme implementovať bez zapamätania si všetkých počtov guličiek na kôpkach v poli. Stačí nám si pri náčítávaní počtov guliek každej hovniválky zapamätať, či sme našli aspoň jeden párny počet, aspoň jeden nepárny počet a sčítavať celkový súčet všetkých guličiek. Pre ten následne určíme, či je párny alebo nepárny.

Už nekontrolujeme všetky výmeny, iba raz prejdeme vstupom pri jeho načítávaní, takže časová zložitosť tohto riešenia je lineárna \(O(n)\) a keďže sme si ukázali, že nám netreba si pamätať vstup, iba pár premenných, tak pamäťová zložitosť je konštantná \(O(1)\).

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int gabika_parita = 0;
    int timka_parita = 0;
    bool gabika_parny = false;
    bool gabika_neparny = false;
    bool timka_parny = false;
    bool timka_neparny = false;

    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        gabika_parita += a;
        if (a % 2 == 0)
        {
            gabika_parny = true;
        }
        else
        {
            gabika_neparny = true;
        }
    }

    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        timka_parita += a;
        if (a % 2 == 0)
        {
            timka_parny = true;
        }
        else
        {
            timka_neparny = true;
        }
    }

    gabika_parita %= 2;
    timka_parita %= 2;

    if (gabika_parita == 0 and timka_parita == 0 and ((gabika_neparny and timka_neparny) or (gabika_parny and timka_parny)))
    {
        cout << "ano" << endl;
    }
    else if (gabika_parita == 1 and timka_parita == 1 and ((gabika_neparny and timka_parny) or (gabika_parny and timka_neparny)))
    {
        cout << "ano" << endl;
    }
    else
    {
        cout << "nie" << endl;
    }
}

n = int(input())
gabika = list(map(int, input().split()))
timka = list(map(int, input().split()))

gabika_parita = sum(gabika) % 2
timka_parita = sum(timka) % 2
gabika_parny = False
gabika_neparny = False
timka_parny = False
timka_neparny = False

for cis in gabika:
    if cis % 2 == 1:
        gabika_neparny = True
    else:
        gabika_parny = True

for cis in timka:
    if cis % 2 == 1:
        timka_neparny = True
    else:
        timka_parny = True


if gabika_parita == 0 and timka_parita == 0 and ((gabika_neparny and timka_neparny) or (gabika_parny and timka_parny)):
    print('ano')
elif gabika_parita == 1 and timka_parita == 1 and ((gabika_neparny and timka_parny) or (gabika_parny and timka_neparny)):
    print('ano')
else:
    print('nie')