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 /* Potyczki Algorytmiczne 2019 (zad.: WIN) Copyright 2019 by Michał Gibas */ #include #include unsigned findSolution(size_t n, size_t k, unsigned* array); unsigned* genCosts(size_t n); unsigned findMin(const std::vector& vec); int main(void) { std::iostream::sync_with_stdio(); size_t n, k; std::cin >> n >> k; unsigned* array = new unsigned[(n*(n+1))/2]; size_t cnt = 0; for(size_t i = 0; i < n; ++i) { for(size_t j = 0; j < (i+1); ++j) { std::cin >> array[cnt]; ++cnt; } } std::cout << findSolution(n, k, array) << '\n'; return 0; } unsigned findSolution(size_t n, size_t k, unsigned* array) { if(k == 1) return array[0]; size_t aSize = (n*(n+1))/2; std::vector v = {array[0]}; unsigned* costs = genCosts(aSize); for(size_t i = 1; i < aSize; ++i) { if(k >= costs[i]) { v.push_back(array[i]); } } return findMin(v); } unsigned* genCosts(size_t n) { unsigned* array = new unsigned[(n*(n+1))/2]; for(size_t i = 0; i < n; ++i) { array[ (i*(i+1))/2 ] = i+1; array[ ((i*(i+1))/2) + i] = i+1; } size_t offset = 1; for(size_t i = 2; i < n; ++i) { for(size_t j = i; j < n; ++j) { array[(j*(j+1))/2 + offset] = i*(j-i+2); array[(j*(j+1))/2 + (j-offset)] = i*(j-i+2); } ++offset; } return array; } unsigned findMin(const std::vector& vec) { unsigned min = vec.at(0); for(auto x : vec) { if(min > x) min = x; } return min; }