#include <cstdio> #include <cmath> #include <cassert> #include <string> #include <algorithm> #include <functional> //#define DEBUG #ifdef DEBUG #define D(x); x #else #define D(x); #endif using namespace std; int input[1000002]; void print_input(int n) { if(n > 50) printf("[...]*%d ", n); else for(int i = 0; i < n; i++) { printf("%d ", input[i]); } } int max_coin(int n) { D(printf("---\nMAX COIN for array of (%d): ", n);); sort(input, input + n, greater<int>()); D(print_input(n);); int m = input[0]; // max int uv = input[0]; // next upgrade - value needed int uq = 1; // next upgrade - quantity needed for(int i = 1; i < n; i++) { if(input[i] == uv) { uq--; if(uq == 0) { m++; int p = m - uv; if(p > 20) break; uq = (int)pow(2, p); } } else { // needed: uq * uv // now need: (nuq * input[i]) - 1 where input[i] < uv int nuq = (uv - input[i]) * 2 * uq; uq = nuq - 1; uv = input[i]; } } D(printf("= %d\n", m);); return m; } #ifdef DEBUG int test(int a[], int n) { std::copy(a, a + n, input); return max_coin(n); } int main() { assert(test((int []){1, 2, 3, 4}, 4) == 4); assert(test((int []){0}, 1) == 0); assert(test((int []){1}, 1) == 1); assert(test((int []){2}, 1) == 2); assert(test((int []){201719}, 1) == 201719); assert(test((int []){201717, 201717, 201718}, 3) == 201719); assert(test((int []){201717, 201717, 201718, 1}, 4) == 201719); assert(test((int []){2, 2, 2, 2}, 4) == 4); assert(test((int []){1, 2, 2, 1, 2}, 5) == 4); assert(test((int []){1, 2, 0, 1, 2}, 5) == 3); assert(test((int []){4, 3}, 2) == 4); assert(test((int []){0, 0, 0, 0}, 4) == 2); assert(test((int []){1, 0, 1, 1, 1}, 5) == 3); assert(test((int []){4, 4, 4, 4, 4, 4, 4, 4, 4, 4}, 10) == 7); assert(test((int []){10, 7, 7, 7, 7, 7, 7, 7, 7, 7}, 10) == 11); int big[1000000]; for(int i = 0; i < 1000000; i++) { big[i] = 1; } assert(test(big, 20) == 5); assert(test(big, 50) == 6); assert(test(big, 1000000) == 20); big[500] = 201717; big[1500] = 201717; big[999999] = 201718; assert(test(big, 1000000) == 201719); return 0; } #else int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &input[i]); } printf("%d\n", max_coin(n)); return 0; } #endif
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #include <cstdio> #include <cmath> #include <cassert> #include <string> #include <algorithm> #include <functional> //#define DEBUG #ifdef DEBUG #define D(x); x #else #define D(x); #endif using namespace std; int input[1000002]; void print_input(int n) { if(n > 50) printf("[...]*%d ", n); else for(int i = 0; i < n; i++) { printf("%d ", input[i]); } } int max_coin(int n) { D(printf("---\nMAX COIN for array of (%d): ", n);); sort(input, input + n, greater<int>()); D(print_input(n);); int m = input[0]; // max int uv = input[0]; // next upgrade - value needed int uq = 1; // next upgrade - quantity needed for(int i = 1; i < n; i++) { if(input[i] == uv) { uq--; if(uq == 0) { m++; int p = m - uv; if(p > 20) break; uq = (int)pow(2, p); } } else { // needed: uq * uv // now need: (nuq * input[i]) - 1 where input[i] < uv int nuq = (uv - input[i]) * 2 * uq; uq = nuq - 1; uv = input[i]; } } D(printf("= %d\n", m);); return m; } #ifdef DEBUG int test(int a[], int n) { std::copy(a, a + n, input); return max_coin(n); } int main() { assert(test((int []){1, 2, 3, 4}, 4) == 4); assert(test((int []){0}, 1) == 0); assert(test((int []){1}, 1) == 1); assert(test((int []){2}, 1) == 2); assert(test((int []){201719}, 1) == 201719); assert(test((int []){201717, 201717, 201718}, 3) == 201719); assert(test((int []){201717, 201717, 201718, 1}, 4) == 201719); assert(test((int []){2, 2, 2, 2}, 4) == 4); assert(test((int []){1, 2, 2, 1, 2}, 5) == 4); assert(test((int []){1, 2, 0, 1, 2}, 5) == 3); assert(test((int []){4, 3}, 2) == 4); assert(test((int []){0, 0, 0, 0}, 4) == 2); assert(test((int []){1, 0, 1, 1, 1}, 5) == 3); assert(test((int []){4, 4, 4, 4, 4, 4, 4, 4, 4, 4}, 10) == 7); assert(test((int []){10, 7, 7, 7, 7, 7, 7, 7, 7, 7}, 10) == 11); int big[1000000]; for(int i = 0; i < 1000000; i++) { big[i] = 1; } assert(test(big, 20) == 5); assert(test(big, 50) == 6); assert(test(big, 1000000) == 20); big[500] = 201717; big[1500] = 201717; big[999999] = 201718; assert(test(big, 1000000) == 201719); return 0; } #else int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &input[i]); } printf("%d\n", max_coin(n)); return 0; } #endif |