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
83
84
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long ulong_t;
typedef unsigned long long uint_t;

#define max_input_pow 201740

void upate_single_power(uint_t* arr) {
    if(arr[0] >= 2) {
        uint_t val = arr[0] >> 1;
        arr[1] += val;
        arr[0] -= val << 1;
    }
}

ulong_t process_input(ulong_t n, uint_t* arr, size_t arr_size) {
    int i = 0;
    for(i = 0; i < arr_size; i++)
    {
        upate_single_power(&(arr[i]));
    }
    i = arr_size - 1;
    while(arr[i] == 0) {
        i--;
    }
    return i;
}


char* get_next_num(const char* input, uint_t *val) {
    char arr[21];
    int i = 0;
    char c;
    c = input[i];
    while(c >= '0' && c <= '9')
    {
        arr[i] = c;
        i++;
        c = input[i];
    }

    arr[i] = '\0';
    *val = atoi(arr);
    if(c == '\0')
    {
        return NULL;
    }
    else {
        return input + i + 1;
    }

}


void insert_powers(const char* line, uint_t* arr, size_t arr_len)
{
    char *c = line;
    uint_t val = 0;
    while(NULL != c)
    {
        c = get_next_num(c, &val);
        arr[val] ++;
    }

}

int main(int argc,char* argv[])
{
    char* str = malloc(7000010);
    memset(str, 0, 700010);
    int no = 0;
    gets(str);
    get_next_num(str, &no);
    int i = 0;
    uint_t input[max_input_pow] = {0};
    memset(str, 0, 700010);
    gets(str);
    insert_powers(str, input, max_input_pow);

    printf("%lu", process_input(no, input, max_input_pow));
    return 0;
}