#include <iostream> #include <deque> #include <vector> #include <map> #include <cmath> using namespace std; struct barrel { int row; int place; int year; }; deque<barrel> RemoveSkippedBarrels(int rows, int minimalRow, deque<barrel> barrels) { if (minimalRow == 0) return barrels; while(barrels.front().row!=minimalRow){ barrels.pop_front(); } return barrels; } bool CanBeChosen(int rows, int changes, barrel currentBarrel) { int placesInCurrentRow = rows - currentBarrel.row; int edgesMeeted = 0; int rowsMeeted = 0; int maxToRight = currentBarrel.place; int maxToLeft = currentBarrel.place; changes--; if (currentBarrel.place == 0 || currentBarrel.place == placesInCurrentRow - 1) return true; for (int i = currentBarrel.row + 1; i < rows; i++) { for (int j = 0; j < rowsMeeted - edgesMeeted + 2; j++) { changes--; if (changes == 0) { return false; } } rowsMeeted++; maxToLeft--; maxToRight++; if (maxToLeft <= 0 || maxToRight >= placesInCurrentRow - rowsMeeted) { edgesMeeted++; } if (maxToLeft <= 0 && maxToRight >= placesInCurrentRow - rowsMeeted) { edgesMeeted++; } } return true; } int CalculateFirstIndexInBarrel(int rowToCheck, int rows, int barrelsSize) { int index = 0; for (int i = rows; i > rows-rowToCheck; i--) { index += i; } return index; } int GetMinYear(int rows, deque<barrel> barrels, vector<barrel> possibleList, int breakIndex) { int min = possibleList.back().year; int pointsNumber = 0; const int minimumRow = possibleList.back().row; for (int i = 0; i < possibleList.size()-1; i++) { if (possibleList[i].year < min) { min = possibleList[i].year; } } for (int i = breakIndex; i < barrels.size(); i++) { if (barrels[i].year < min) { min = barrels[i].year; } } return min; } int FindMinYear(deque<barrel> barrels, int changes, int rows) { if (changes == 1) { return barrels.back().year; } int minimalRow = changes>rows ? 0 : rows-changes; int inserted = 0; vector<barrel> possibleList; deque<barrel> barrelsToCheck = RemoveSkippedBarrels(rows, minimalRow, barrels); bool isEverythingPossible = true; for (int i = minimalRow; i < rows; i++) { isEverythingPossible = true; inserted = 0; for (int j = 0; j < ceil(((float)rows - (float)i)/2.0F); j++) { if (CanBeChosen(rows, changes, barrelsToCheck.front())) { possibleList.push_back(barrelsToCheck.front()); barrelsToCheck.pop_front(); inserted++; } else { for (int k = j; k < rows - i-inserted; k++) { barrelsToCheck.pop_front(); } for (int k = rows - i - inserted; k<rows-i; k++) { possibleList.push_back(barrelsToCheck.front()); barrelsToCheck.pop_front(); } isEverythingPossible = false; break; } } if (isEverythingPossible) { return GetMinYear(rows, barrels, possibleList, CalculateFirstIndexInBarrel(i, rows, barrels.size())); } } } int main() { cin.tie(NULL); cout.sync_with_stdio(false); int changes; int rows; int year; deque<barrel> barrels; cin >> rows; cin >> changes; for (int i = rows; i >= 0; i--) { for (int j = 0; j < rows - i; j++) { cin >> year; barrel tempBarrel; tempBarrel.place = j; tempBarrel.row = i; tempBarrel.year = year; barrels.push_front(tempBarrel); } } cout << FindMinYear(barrels, changes, rows); }
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 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #include <iostream> #include <deque> #include <vector> #include <map> #include <cmath> using namespace std; struct barrel { int row; int place; int year; }; deque<barrel> RemoveSkippedBarrels(int rows, int minimalRow, deque<barrel> barrels) { if (minimalRow == 0) return barrels; while(barrels.front().row!=minimalRow){ barrels.pop_front(); } return barrels; } bool CanBeChosen(int rows, int changes, barrel currentBarrel) { int placesInCurrentRow = rows - currentBarrel.row; int edgesMeeted = 0; int rowsMeeted = 0; int maxToRight = currentBarrel.place; int maxToLeft = currentBarrel.place; changes--; if (currentBarrel.place == 0 || currentBarrel.place == placesInCurrentRow - 1) return true; for (int i = currentBarrel.row + 1; i < rows; i++) { for (int j = 0; j < rowsMeeted - edgesMeeted + 2; j++) { changes--; if (changes == 0) { return false; } } rowsMeeted++; maxToLeft--; maxToRight++; if (maxToLeft <= 0 || maxToRight >= placesInCurrentRow - rowsMeeted) { edgesMeeted++; } if (maxToLeft <= 0 && maxToRight >= placesInCurrentRow - rowsMeeted) { edgesMeeted++; } } return true; } int CalculateFirstIndexInBarrel(int rowToCheck, int rows, int barrelsSize) { int index = 0; for (int i = rows; i > rows-rowToCheck; i--) { index += i; } return index; } int GetMinYear(int rows, deque<barrel> barrels, vector<barrel> possibleList, int breakIndex) { int min = possibleList.back().year; int pointsNumber = 0; const int minimumRow = possibleList.back().row; for (int i = 0; i < possibleList.size()-1; i++) { if (possibleList[i].year < min) { min = possibleList[i].year; } } for (int i = breakIndex; i < barrels.size(); i++) { if (barrels[i].year < min) { min = barrels[i].year; } } return min; } int FindMinYear(deque<barrel> barrels, int changes, int rows) { if (changes == 1) { return barrels.back().year; } int minimalRow = changes>rows ? 0 : rows-changes; int inserted = 0; vector<barrel> possibleList; deque<barrel> barrelsToCheck = RemoveSkippedBarrels(rows, minimalRow, barrels); bool isEverythingPossible = true; for (int i = minimalRow; i < rows; i++) { isEverythingPossible = true; inserted = 0; for (int j = 0; j < ceil(((float)rows - (float)i)/2.0F); j++) { if (CanBeChosen(rows, changes, barrelsToCheck.front())) { possibleList.push_back(barrelsToCheck.front()); barrelsToCheck.pop_front(); inserted++; } else { for (int k = j; k < rows - i-inserted; k++) { barrelsToCheck.pop_front(); } for (int k = rows - i - inserted; k<rows-i; k++) { possibleList.push_back(barrelsToCheck.front()); barrelsToCheck.pop_front(); } isEverythingPossible = false; break; } } if (isEverythingPossible) { return GetMinYear(rows, barrels, possibleList, CalculateFirstIndexInBarrel(i, rows, barrels.size())); } } } int main() { cin.tie(NULL); cout.sync_with_stdio(false); int changes; int rows; int year; deque<barrel> barrels; cin >> rows; cin >> changes; for (int i = rows; i >= 0; i--) { for (int j = 0; j < rows - i; j++) { cin >> year; barrel tempBarrel; tempBarrel.place = j; tempBarrel.row = i; tempBarrel.year = year; barrels.push_front(tempBarrel); } } cout << FindMinYear(barrels, changes, rows); } |