1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <list>

using namespace std;

class Coin
{
    public:
        int index;
        int value;
};

void fixTail(list<Coin>& coinList)
{
    Coin lastCoin = coinList.back();
    if (lastCoin.value > 1) {
        int moveToNextBit = lastCoin.value / 2;
        lastCoin.value = lastCoin.value % 2;
        Coin nextCoin;
        nextCoin.index = lastCoin.index += 1;
        nextCoin.value = moveToNextBit;
        coinList.push_back(nextCoin);
    }
}

int main() {
//    deklaracja zmiennych
    int numberOfCoins;  //1 <= numberOfCoins <= 1 000 000
    int *coins;
    int binarySumOfMoney[201719] = {0};
    int maxCoin = -1;   //0 <= maxCoin <= 201718
    list<Coin> sumOfMoney;
//    wczytywanie zmiennych
    cin>>numberOfCoins;
    coins = new int[numberOfCoins];
    for (int i = 0; i < numberOfCoins; i++) {
        cin>>coins[i];
    }
    
//    dla kazdej wczytanej dodac 1
    for (int i = 0; i < numberOfCoins; i++) {
        int currentCoin = coins[i];
        binarySumOfMoney[currentCoin] += 1;
        if (currentCoin > maxCoin) {
            maxCoin = currentCoin;
        }
    }
    
//    zsumowac dane w tablicy
    for (int i = 0; i <= maxCoin; i++) {
        if (binarySumOfMoney[i] == 0) {
            continue;
        } else if (binarySumOfMoney[i] > 0) {
            //  add coin to the list
            Coin currentCoin;
            currentCoin.index = i;
            currentCoin.value = binarySumOfMoney[i];
            if (sumOfMoney.size() == 0)
            {
                sumOfMoney.push_back(currentCoin);
            } else {
                if (sumOfMoney.back().index == currentCoin.index){
                    sumOfMoney.back().value += currentCoin.value;
                } else {
                    sumOfMoney.push_back(currentCoin);
                }
            }
            fixTail(sumOfMoney);
        }
    }

//    fixuj ogon do konca
    
    while (sumOfMoney.back().value > 1) {
        fixTail(sumOfMoney);
    }
    
//    zwroc najwyzszy indeks z tablicy czyli najwyzsza mozliwa do dostania monete
    cout << sumOfMoney.back().index << endl;
    
    return 0;
}