648A - Наибольший подъем

Для решения данной задачи насчитаем высоту каждой горы и сохраним ее в массиве h[], где h[j] равно высоте j-й горы. Для этого обойдем заданную матрицу, и если элемент, стоящий в строке i и в столбце j (строки и столбцы 0-индексированы), равен звездочке, обновим высоту j-й горы: h[j] = max(h[j], n - i). Осталось просто проитерироваться по столбцам от 0 до m — 2 включительно, и, если текущий столбец равен j, обновить величину максимального подъема или максимального спуска величиной |h[j + 1] - h[j]|.

int n, m;
int h[N];
char c;

void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c;
			if (c == '*') {
				h[j] = max(h[j], n - i);
			}
		}
	}
	int maxU = 0, maxD = 0;
	for (int i = 0; i < m - 1; i++) {
		int diff = h[i + 1] - h[i];
		if (diff > 0) {
			maxU = max(maxU, diff);
		} else {
			maxD = max(maxD, -diff);
		}
	}
	cout << maxU << ' ' << maxD << endl;
}

648B - Собери стол

Для решения данной задачи сначала посчитаем длину одной собранной ножки стола и сохраним ее в переменную len (len = sum / n, где sum — это суммарная длина всех частей, а n — количество ножек стола). Сохраним длины всех частей ножек в массив a[] и отсортируем его по возрастанию. Затем переберем части ножек переменной i от 0 до n - 1 включительно и будем выводить в ответ пары вида (a[i], len - a[i]).

int n, len, sum;
int a[N];

int main() {
	cin >> n;
	for (int i = 0; i < 2 * n; i++) {
		cin >> a[i];
		sum += a[i];
	}   	
	len = sum / n;
	sort(a, a + 2 * n);
	for (int i = 0; i < n; i++) {
		cout << a[i] << ' ' << len - a[i] << endl;
	}
}

648C - Путь Робота

Сначала найдем стартовую позицию Робота, сохраним ее и присвоим значение стартовой позиции звездоке. Так как по условию задана ломаная без самопересечений и самокасаний верен следующий алгоритм: если есть соседняя с текущей клетка, в которой стоит звездочка, перейдем в соседнюю клетку, значение которой равно звездочке, и присвоим ее значение точке (при этом выведем букву, соответствующую направлению, в котором мы перешли). При этом соседняя клетка должна быть отлична от той, из которой мы пришли в текущую клетку. Если нет соседней клетки с звездочкой, значит мы обошли всю ломаную и нужно закончить работу программы.

int n, m, sx, sy;
char a[N][N];   

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char dir[] = {'U', 'D', 'L', 'R'}; 

void solve() 
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 'S') {
				sx = i, sy = j;
			}
		}
	}
	a[sx][sy] = '*';
	int px = -1, py = -1;
        while (true) {
    	    bool wasMove = false;
    	    for (int i = 0; i < 4; i++) {
    		int nx = sx + dx[i];
    		int ny = sy + dy[i];
    		if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
    			continue;
    		}
    		if (a[nx][ny] != '*') {
    			continue;
    		}
    		if (nx == px && ny == py) {
    			continue;    		
    		}
    		a[nx][ny] = '.';
    		px = sx, py = sy;
    		sx = nx, sy = ny;    		
    		cout << dir[i];	
    		wasMove = true;
    		break;
            }         
            if(wasMove) {
           	break;
            }
        }
    puts("");
}

648D - Собачки и миски

Если представить каждую миску в виде отрезка [u_j - t_j, u_j + t_j], то i-я собачка сможет покушать из j миски, если u_j - t_j ≤ x_i ≤ u_j + t_j.

Будем решать задачу жадно. Рассмотрим самую левую собачку и те миски из которых она может покушать. Если таких мисок нет, то собачка не сможет покушать. В противном случае из мисок доступных самой левой собачке выберем для неё миску с самым левым правым концом. Далее не будем рассматривать эту собачку и эту миску и продолжим аналогично наши рассуждения.

Легко видеть, что такая жадность приводит к оптимальному ответу:

• Если самая левая собачка может покушать, то нет смысла ей не кушать, поскольку этим мы убираем одну миску и ухудшим ответ на единицу;
• Рассмотрим те миски из которых может покушать самая левая собачка. Все эти миски будут доступны и остальным собачкам кроме тех у которых правая граница находится слишком далеко влево. Таким образом, если мы хотим взять какую-либо миску (а мы уже поняли из пункта 1, что это стоит сделать), то выгоднее будет взять миску с самым левым правым концом, так мы не ухудшим выбор для собачек справа.

По этой задаче можно было попробовать написать другие жадности, но многие являются неправильными.

Для того, чтобы это реализовать отсортируем собачек и миски (по левому концу) слева направо. Будем идти слева-направо обрабатывая события появилась миска (в этом случае добавим её правый конец в какую-нибудь структуру данных) и появилась собачка (нужно для собачки в структуре данных найти самый левый подходящий правый конец).

Сложность: O(nlogn) или O(n) в зависимости от структуры данных (*set* или queue).

const int N = 200200;

int n, m;
int x[N];
int u[N], t[N];

bool read() {
	if (!(cin >> n >> m)) return false;
	forn(i, n) assert(scanf("%d", &x[i]) == 1);
	forn(i, m) assert(scanf("%d%d", &u[i], &t[i]) == 2);
	return true;
}

pti segs[N];

void solve() {
	forn(i, m) segs[i] = mp(u[i] - t[i], u[i] + t[i]);

	sort(x, x + n);
	sort(segs, segs + m);

	int ans = 0;
	multiset<int> z;
	for (int i = 0, j = 0; i < n; ) {
		if (j < m && segs[j].x <= x[i]) {
			z.insert(segs[j].y);
			j++;
		} else {
			auto it = z.lower_bound(x[i]);
			i++;
			if (it != z.end()) {
				ans++;
				z.erase(it);
			}
		}
	}
	cout << ans << endl;
}

648E - Собери число

Заметим, что при построении ответа нам в любой момент важен только лишь остаток от деления текущего его префикса на k. Действительно, если текущий префикс ответа имеет остаток от деления на k, равный r, то при приписывании к префиксу числа a_i этот остаток станет равный остатку от деления на k числа r·10^l_i + a_i (l_i — количество цифр в записи числа a_i).

Тогда, очевидно, нас интересует получать любой остаток от деления такой операцией, используя минимальное количество цифр в записи. Конечно, остаток 0 мы можем получить сразу, используя пустой префикс, поэтому для остатка 0 нас будет интересовать второй по величине ответ.

Все описанное выше позволяет нам построить граф на k вершинах (от 0 до k - 1, соответственно остаткам), ребра в котором определяются числами a_i: из вершины v в вершину длины l_i, означающее, что с помощью дописывания l_i цифр мы можем из префикса с остатком v получить префикс с остатком u. Легко заметить, что некоторые a_i в этом графе будут соответствовать одним и тем же ребрам (сейчас их nk) — это числа с одинаковой длиной десятичной записи и остатком от деления на k, поэтому стоит оставить лишь уникальные по такому критерию числа (их будет не больше 10k), и тогда количество ребер не будет превышать 10k².

Теперь все, что от нас требуется — найти длину кратчайшего непустого пути из вершины 0 в саму себя же в построенном графе. Чтобы избежать столь неприятной цикличности, давайте просто добавим дополнительную вершину k, имеющую те же исходящие ребра, что и вершина 0, считая, что такой остаток может иметь лишь пустой префикс. Теперь задача сводится к нахождению кратчайшего пути из вершины k в вершину 0, которую можно решить алгоритмом Дейкстры за O(k²). Однако, в силу специфичности задачи, решение алгоритмом Форда-Беллмана (с правильными отсечениями, конечно) так же проходит все тесты, хоть в теории и имеет столь большие O(k³).

Восстановление ответа в задаче довольно стандартно, за исключением хранения дополнительного числа для каждой вершины, образовавшего ребро, по которому был осуществлен нужный в кратчайшем ответе переход.

    for (int i = 0; i < n; ++i) {
        int x;
        assert(scanf("%d", &x) == 1);
        any[x % k][length(x)] = x;
    }

    p10[0] = 1;
    for (int i = 0; i + 1 < P; ++i)
        p10[i + 1] = (p10[i] * 10) % k;

    for (int i = 0; i <= k; ++i) {
        d[i] = int(1e9);
        p[i] = -1;
        used[i] = false;
    }

    d[k] = 0;
    while (true) {
        int v = -1;
        for (int i = 0; i <= k; ++i)
            if (!used[i] && (v == -1 || d[v] > d[i]))
                v = i;
        if (v == -1)
            break;   
        if (v == 0)
            break;
        used[v] = true;
        for (int r = 0; r < k; ++r)
            for (int l = 0; l < P; ++l)
                if (any[r][l] != -1) {
                    int to = (v * p10[l] + r) % k;
                    if (d[to] > d[v] + l) {
                        d[to] = d[v] + l;
                        p[to] = v;
                        w[to] = any[r][l];
                        used[to] = false;
                    }
                }               
    }   

    if (p[0] == -1) {
        puts("NO");
    } else {
        puts("YES");
        vector <int> res;
        int v = 0;
        do {
            res.push_back(w[v]);
            v = p[v];
        } while (v != k);

        reverse(res.begin(), res.end());
        for (auto x: res)
            printf("%d", x);
    }