2. Ováľané mince vzorové riešenie

for i in range(len(pole)-1):
	print(pole[i], end=' ')
print(pole[-1])

print(" ".join(str(prvok) for prvok in pole))

2
3 0
5 0

0
1

2
3 1
5 1

0
2 1 2
1 3
1
3 1 2 5
2 3 4

Skúsme si najprv rozdeliť rovnomerne nejaké čísla \(a, a+1, ..., b\). Veľmi rýchlo si môžeme všimnúť, že ak berieme najväčšie a najmenšie, druhé najväčšie a druhé najmenšie, tak tieto dvojice majú vždy rovnaký súčet.

Bohužiaľ, nám to ešte nepovie, ako rozdeliť čísla, aby bol medzi nimi čo najmenší rozdiel. Povedzme si najprv, že kedy vieme mince \(1,2, ..., n\) rozdeliť na rovnaké časti. Aby bolo možné rozdeliť mince rovnomerne, tak ich súčet musí byť párny, a teda v ňom musí byť párny počet nepárnych čísiel. To, či to v našej postupnosti platí, vieme šikovne zisťovať tak, že (počet čísel označme ako \(n\)), \(n \% 4 = 3\) alebo \(n \% 4 = 0\).

Ľahko si všimneme, že ak \(n \% 4 = 0\), tak mince vieme rovnomerne rozdeliť tak, že zoberieme dvojice \(1\) a \(n\), \(2\) a \(n-1\), … . Takýchto dvojíc je párny počet, a teda ich vieme rozdeliť na dve rovnaké polovice.

V prípade ak \(n \% 4 = 3\), tak je to už trochu zložitejšie. Ak ale vieme, že \(n+1\) mincí (teda \(n \% 4 = 0\)) sa dá rozdeliť, tak toto sa líši len o \(n+1\) a teda ak jednej strane zoberieme mincu/mince v hodnote \((n+1)/2\), tak budú obe polovice vyrovnané. (Dá sa to jednoduchšie predstaviť ak si to napíšete na papier.)

Čo ale v prípade, ak sa nedajú mince rozdeliť rovnomerne? Ak \(n \% 4 = 2\), tak máme vlastne oproti prípadu, ktorý vieme rovnomerne rozdeliť (\(n \% 4 = 0\)), naviac čísla \(n+1\) a \(n+2\), a tieto čísla sa líšia len o \(1\), a to je minimálny rozdiel, čo vieme dosiahnuť. (Nech robíme čo robíme, nepárny súčet na dve rovnaké polovice nerozdelíme.)

A ostáva posledný prípad, keď \(n \% 4 = 1\). Tento prípad je zase veľmi podobný prípadu keď \(n \% 4 = 3\), a rovnako tu máme naviac dve čísla, a rovnako je minimálny rozdiel \(1\).

Keď už máme vypočítanú hodnotu, akú má dostať každý stavbár, teraz pokiaľ \(p = 1\), tak musíme vypísať aj aké mince každý dostane.

Čísla vieme získavať buď tak, ako sme písali, teda po dvojiciach, alebo jednoduchšie, pažravo. Pažravo ich získame tak, že ideme od najväčších mincí, a počítame si súčet už zobraných mincí. Ak si danú mincu vieme zobrať (pripočítať k súčtu) bez toho, aby sme presiahli polovicu cekovej sumy, zoberieme ju.

Možno si kladiete otázku, či to takto pažravo môže fungovať. Odpoveď je, áno. Naše mince majú v súčte určite väčšiu hodnotu ako potrebujeme, a máme mince s každou hodnotou, ktorú by sme mohli potrebovať. Teda máme zaručené, že nech zmenšíme rozdiel medzi sumou, ktorú chceme získať a sumou, ktorú sme zatiaľ nazbierali, na ľubovoľnú hodnotu, tak určite bude existovať minca, ktorá sa nám do tohto rozdielu zmestí.

Čo sa týka časovej zložitosti, pokiaľ \(p = 0\), tak časová zložitosť je \(O(1)\), lebo odpoveď na jednu otázku vypočítame v konštantnom čase, vzorcom. V prípade, že \(p = 1\), musíme dokopy vypísať \(n\)-prvkové pole, ktoré ale vieme získať v čase priamo úmernom od \(n\), takže zložitosť je \(O(n)\). Pamätať si nemusíme nič, pretože hodnoty poľa môžeme vypočítať vo for-cykle bez toho, aby sme si okrem niekoľko málo premenných niečo naviac pamätali, a preto je pamäťová zložitosť konštantná = \(O(1)\).

#include<iostream>
#include<vector>

using namespace std;

int main()
{
    long long t=0, n=0, i=0, j=0, suma=0, odpoved=0, suma_doteraz=0;
    vector<long long> prva, druha;
    cin>>t;
    for(i=0;i<t;i++)
    {
        cin>>n>>odpoved;
        suma=n*(1+n)/2;
        cout<<(suma%2)<<endl;
        if(odpoved==1)
        {
            suma_doteraz=0;
            prva.clear();
            druha.clear();
            for(j=n;j>0;j--)
            {
                if(suma_doteraz+j <= suma/2)
                {
                    suma_doteraz+=j;
                    prva.push_back(j);
                }
                else
                    druha.push_back(j);
            }
            cout<<prva.size();
            for(j=0;j<prva.size();j++)
                 cout<<" "<<prva[j];
            cout<<endl;

            cout<<druha.size();
            for(j=0;j<druha.size();j++)
                 cout<<" "<<druha[j];
            cout<<endl;

        }
    }
}

def vysledok(k):
    return int((k*(k+1)//2) % 2)
    
    
def vypis(k):
    polovica = int((k*(k+1)//2) / 2)
    p1 = []
    p2 = []
    sum1 = 0
    sum2 = 0
    for i in range(k, 0, -1):
        if sum1+i > polovica:
            sum2 += i
            p2.append(i)
            continue
        sum1 += i
        p1.append(i)
    print(len(p1), *p1)
    print(len(p2), *p2)
        

n = int(input())
for i in range(n):
    k, mam_vypisat = map(int, input().split())
    print(vysledok(k))
    if mam_vypisat:
        vypis(k)