648.md (14271B)
1 Source: https://codeforces.com/blog/entry/43964 2 3 ### [648A - Наибольший подъем](/contest/648/problem/A "Технокубок 2016 - Отборочный Раунд 1") 4 5 Для решения данной задачи насчитаем высоту каждой горы и сохраним ее в массиве *h*[], где *h*[*j*] равно высоте *j*-й горы. Для этого обойдем заданную матрицу, и если элемент, стоящий в строке *i* и в столбце *j* (строки и столбцы 0-индексированы), равен звездочке, обновим высоту *j*-й горы: *h*[*j*] = *max*(*h*[*j*], *n* - *i*). Осталось просто проитерироваться по столбцам от 0 до m — 2 включительно, и, если текущий столбец равен *j*, обновить величину максимального подъема или максимального спуска величиной |*h*[*j* + 1] - *h*[*j*]|. 6 7 **Пример решения** 8 9 Основная часть решения: 10 11 ``` 12 int n, m; 13 int h[N]; 14 char c; 15 16 void solve() { 17 cin >> n >> m; 18 for (int i = 0; i < n; i++) { 19 for (int j = 0; j < m; j++) { 20 cin >> c; 21 if (c == '*') { 22 h[j] = max(h[j], n - i); 23 } 24 } 25 } 26 int maxU = 0, maxD = 0; 27 for (int i = 0; i < m - 1; i++) { 28 int diff = h[i + 1] - h[i]; 29 if (diff > 0) { 30 maxU = max(maxU, diff); 31 } else { 32 maxD = max(maxD, -diff); 33 } 34 } 35 cout << maxU << ' ' << maxD << endl; 36 } 37 ``` 38 39 ### [648B - Собери стол](/contest/648/problem/B "Технокубок 2016 - Отборочный Раунд 1") 40 41 Для решения данной задачи сначала посчитаем длину одной собранной ножки стола и сохраним ее в переменную *len* (*len* = *sum* / *n*, где *sum* — это суммарная длина всех частей, а *n* — количество ножек стола). Сохраним длины всех частей ножек в массив *a*[] и отсортируем его по возрастанию. Затем переберем части ножек переменной *i* от 0 до *n* - 1 включительно и будем выводить в ответ пары вида (*a*[*i*], *len* - *a*[*i*]). 42 43 **Пример решения** 44 45 Основная часть решения: 46 47 ``` 48 int n, len, sum; 49 int a[N]; 50 51 int main() { 52 cin >> n; 53 for (int i = 0; i < 2 * n; i++) { 54 cin >> a[i]; 55 sum += a[i]; 56 } 57 len = sum / n; 58 sort(a, a + 2 * n); 59 for (int i = 0; i < n; i++) { 60 cout << a[i] << ' ' << len - a[i] << endl; 61 } 62 } 63 ``` 64 65 ### [648C - Путь Робота](/contest/648/problem/C "Технокубок 2016 - Отборочный Раунд 1") 66 67 Сначала найдем стартовую позицию Робота, сохраним ее и присвоим значение стартовой позиции звездоке. Так как по условию задана ломаная без самопересечений и самокасаний верен следующий алгоритм: если есть соседняя с текущей клетка, в которой стоит звездочка, перейдем в соседнюю клетку, значение которой равно звездочке, и присвоим ее значение точке (при этом выведем букву, соответствующую направлению, в котором мы перешли). При этом соседняя клетка должна быть отлична от той, из которой мы пришли в текущую клетку. Если нет соседней клетки с звездочкой, значит мы обошли всю ломаную и нужно закончить работу программы. 68 69 **Пример решения** 70 71 Основная часть решения: 72 73 ``` 74 int n, m, sx, sy; 75 char a[N][N]; 76 77 int dx[] = {-1, 1, 0, 0}; 78 int dy[] = {0, 0, -1, 1}; 79 char dir[] = {'U', 'D', 'L', 'R'}; 80 81 void solve() 82 { 83 cin >> n >> m; 84 for (int i = 0; i < n; i++) { 85 for (int j = 0; j < m; j++) 86 { 87 cin >> a[i][j]; 88 if (a[i][j] == 'S') { 89 sx = i, sy = j; 90 } 91 } 92 } 93 a[sx][sy] = '*'; 94 int px = -1, py = -1; 95 while (true) { 96 bool wasMove = false; 97 for (int i = 0; i < 4; i++) { 98 int nx = sx + dx[i]; 99 int ny = sy + dy[i]; 100 if (nx < 0 || nx >= n || ny < 0 || ny >= m) { 101 continue; 102 } 103 if (a[nx][ny] != '*') { 104 continue; 105 } 106 if (nx == px && ny == py) { 107 continue; 108 } 109 a[nx][ny] = '.'; 110 px = sx, py = sy; 111 sx = nx, sy = ny; 112 cout << dir[i]; 113 wasMove = true; 114 break; 115 } 116 if(wasMove) { 117 break; 118 } 119 } 120 puts(""); 121 } 122 ``` 123 124 ### [648D - Собачки и миски](/contest/648/problem/D "Технокубок 2016 - Отборочный Раунд 1") 125 126 Если представить каждую миску в виде отрезка [*u**j* - *t**j*, *u**j* + *t**j*], то *i*-я собачка сможет покушать из *j* миски, если *u**j* - *t**j* ≤ *x**i* ≤ *u**j* + *t**j*. 127 128 Будем решать задачу жадно. Рассмотрим самую левую собачку и те миски из которых она может покушать. Если таких мисок нет, то собачка не сможет покушать. В противном случае из мисок доступных самой левой собачке выберем для неё миску с самым левым правым концом. Далее не будем рассматривать эту собачку и эту миску и продолжим аналогично наши рассуждения. 129 130 Легко видеть, что такая жадность приводит к оптимальному ответу: 131 132 * Если самая левая собачка может покушать, то нет смысла ей не кушать, поскольку этим мы убираем одну миску и ухудшим ответ на единицу; 133 * Рассмотрим те миски из которых может покушать самая левая собачка. Все эти миски будут доступны и остальным собачкам кроме тех у которых правая граница находится слишком далеко влево. Таким образом, если мы хотим взять какую-либо миску (а мы уже поняли из пункта 1, что это стоит сделать), то выгоднее будет взять миску с самым левым правым концом, так мы не ухудшим выбор для собачек справа. 134 135 По этой задаче можно было попробовать написать другие жадности, но многие являются неправильными. 136 137 Для того, чтобы это реализовать отсортируем собачек и миски (по левому концу) слева направо. Будем идти слева-направо обрабатывая события появилась миска (в этом случае добавим её правый конец в какую-нибудь структуру данных) и появилась собачка (нужно для собачки в структуре данных найти самый левый подходящий правый конец). 138 139 Сложность: *O*(*nlogn*) или *O*(*n*) в зависимости от структуры данных (*set* или *queue*). 140 141 **Решения на С++** 142 143 ``` 144 const int N = 200200; 145 146 int n, m; 147 int x[N]; 148 int u[N], t[N]; 149 150 bool read() { 151 if (!(cin >> n >> m)) return false; 152 forn(i, n) assert(scanf("%d", &x[i]) == 1); 153 forn(i, m) assert(scanf("%d%d", &u[i], &t[i]) == 2); 154 return true; 155 } 156 157 pti segs[N]; 158 159 void solve() { 160 forn(i, m) segs[i] = mp(u[i] - t[i], u[i] + t[i]); 161 162 sort(x, x + n); 163 sort(segs, segs + m); 164 165 int ans = 0; 166 multiset<int> z; 167 for (int i = 0, j = 0; i < n; ) { 168 if (j < m && segs[j].x <= x[i]) { 169 z.insert(segs[j].y); 170 j++; 171 } else { 172 auto it = z.lower_bound(x[i]); 173 i++; 174 if (it != z.end()) { 175 ans++; 176 z.erase(it); 177 } 178 } 179 } 180 cout << ans << endl; 181 } 182 ``` 183 184 ### [648E - Собери число](/contest/648/problem/E "Технокубок 2016 - Отборочный Раунд 1") 185 186 Заметим, что при построении ответа нам в любой момент важен только лишь остаток от деления текущего его префикса на *k*. Действительно, если текущий префикс ответа имеет остаток от деления на *k*, равный *r*, то при приписывании к префиксу числа *a**i* этот остаток станет равный остатку от деления на *k* числа *r*·10*l**i* + *a**i* (*l**i* — количество цифр в записи числа *a**i*). 187 188 Тогда, очевидно, нас интересует получать любой остаток от деления такой операцией, используя минимальное количество цифр в записи. Конечно, остаток 0 мы можем получить сразу, используя пустой префикс, поэтому для остатка 0 нас будет интересовать второй по величине ответ. 189 190 Все описанное выше позволяет нам построить граф на *k* вершинах (от 0 до *k* - 1, соответственно остаткам), ребра в котором определяются числами *a**i*: из вершины *v* в вершину  длины *l**i*, означающее, что с помощью дописывания *l**i* цифр мы можем из префикса с остатком *v* получить префикс с остатком *u*. Легко заметить, что некоторые *a**i* в этом графе будут соответствовать одним и тем же ребрам (сейчас их *nk*) — это числа с одинаковой длиной десятичной записи и остатком от деления на *k*, поэтому стоит оставить лишь уникальные по такому критерию числа (их будет не больше 10*k*), и тогда количество ребер не будет превышать 10*k*2. 191 192 Теперь все, что от нас требуется — найти длину кратчайшего непустого пути из вершины 0 в саму себя же в построенном графе. Чтобы избежать столь неприятной цикличности, давайте просто добавим дополнительную вершину *k*, имеющую те же исходящие ребра, что и вершина 0, считая, что такой остаток может иметь лишь пустой префикс. Теперь задача сводится к нахождению кратчайшего пути из вершины *k* в вершину 0, которую можно решить алгоритмом Дейкстры за *O*(*k*2). Однако, в силу специфичности задачи, решение алгоритмом Форда-Беллмана (с правильными отсечениями, конечно) так же проходит все тесты, хоть в теории и имеет столь большие *O*(*k*3). 193 194 Восстановление ответа в задаче довольно стандартно, за исключением хранения дополнительного числа для каждой вершины, образовавшего ребро, по которому был осуществлен нужный в кратчайшем ответе переход. 195 196 **Пример решения алгоритмом Дейкстры** 197 198 Основная часть: 199 200 ``` 201 for (int i = 0; i < n; ++i) { 202 int x; 203 assert(scanf("%d", &x) == 1); 204 any[x % k][length(x)] = x; 205 } 206 207 p10[0] = 1; 208 for (int i = 0; i + 1 < P; ++i) 209 p10[i + 1] = (p10[i] * 10) % k; 210 211 for (int i = 0; i <= k; ++i) { 212 d[i] = int(1e9); 213 p[i] = -1; 214 used[i] = false; 215 } 216 217 d[k] = 0; 218 while (true) { 219 int v = -1; 220 for (int i = 0; i <= k; ++i) 221 if (!used[i] && (v == -1 || d[v] > d[i])) 222 v = i; 223 if (v == -1) 224 break; 225 if (v == 0) 226 break; 227 used[v] = true; 228 for (int r = 0; r < k; ++r) 229 for (int l = 0; l < P; ++l) 230 if (any[r][l] != -1) { 231 int to = (v * p10[l] + r) % k; 232 if (d[to] > d[v] + l) { 233 d[to] = d[v] + l; 234 p[to] = v; 235 w[to] = any[r][l]; 236 used[to] = false; 237 } 238 } 239 } 240 241 if (p[0] == -1) { 242 puts("NO"); 243 } else { 244 puts("YES"); 245 vector <int> res; 246 int v = 0; 247 do { 248 res.push_back(w[v]); 249 v = p[v]; 250 } while (v != k); 251 252 reverse(res.begin(), res.end()); 253 for (auto x: res) 254 printf("%d", x); 255 } 256 ```