codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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* в вершину ![](https://espresso.codeforces.com/f5db105b52703edd30c6c2904569fe2f7b41a1e3.png) длины *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 ```