649A - Любимые числа Поликарпа

Для решения данной задачи нужно воспользоваться фактом, что степени двойки быстро растут, и максимальная степень двойки, на которую может делится число, не превосходящее 10⁹, равна 29. Поэтому нужно просто проитерироваться по заданным числам, найти максимальную степень двойки, на которую делится текущее число и обновить ответ этой максимальной степенью.

int n, x;

int main() {
	cin >> n;	
	int ans = -1, cnt = 0;
	for (int i = 0; i < n; i++) {
		cin >> x;
		int cur = 1, power = 0;
		while (true) {
			cur *= 2;
			if (x % cur) break;			
                        power++;
		}
		if (ans < power) {
			ans = power;
			cnt = 1;
		} else if (ans == power) {
			cnt++;
		}
	}
	cout << ans << ' ' << cnt << endl;
}

649B - Этажи

Для решения данной задачи нужно было аккуратно реализовать то, что написано в условии. Основная сложность заключалась в определении номера подъезда и номера этажа по номеру квартиры. Это можно было сделать следующим образом: если в доме n подъездов, в каждом подъезде по m этажей, а на каждом этаже по k квартир, то квартира с номером a находится в подъезде номер (a - 1) / (m * k) и на этаже номер ((a - 1)%(m * k)) / k, причем эти номера 0-индексированы, что удобно для дальнейших вычислений. После определения номеров подъездов и этажей, нужно было рассмотреть два случая — когда номера подъездов Эдварда и Наташи равны (тогда нужно было выбрать, что оптимальнее — доехать на лифте или подняться/спуститься по лестнице), и когда эти номера различны (тут нужно было не забыть, что дом круглый, и выбрать нужное направление).

int n, m, k, a, b;

int main() {	
	cin >> n >> m >> k >> a >> b;
	a--, b--;
	int p1 = a / (m * k), p2 = b / (m * k);
	int f1 = (a % (m * k)) / k, f2 = (b % (m * k)) / k;
	if (p1 == p2) {
		cout << min(abs(f1 - f2) + 10, abs(f1 - f2) * 5) << endl;
	} else {
	    if(p1 > p2) swap(p1, p2);
	    cout << min((p2 - p1) * 15, (p1 + n - p2) * 15) + min(f1 * 5, 10 + f1) + min(f2 * 5, 10 + f2) << endl;
	}
}

649C - Печать условий

Сначала отсортируем заданные размеры комплектов задач в неубывающем порядке. Затем нужно начать перебирать комплекты задач, начиная с наименьшего. Если мы не можем напечатать текущий комплект, то никакой следующий комплект мы гарантированно не сможем напечатать, поэтому нужно вывести ответ и закончить алгоритм. В противном случае нужно напечатать текущий комплект, увеличить ответ на единицу и перейти к следующему комплекту. Каждый комплект оптимально печатать следующим образом. Пусть x — это оставшееся количество двусторонних листов, y — это оставшееся количество односторонних листов, а a — это количество страниц в текущем комплекте задач. Если x = 0 и y = 0, то напечатать текущий комплект мы точно не сможем. Если a нечетно и y > 0, напечатаем одну страницу на одностороннем листе и уменьшим a и y на единицу, иначе если a нечетно и x > 0, напечатаем одну страницу на двустороннем листе (который больше использовать не будем) и уменьшим a и x на единицу. Теперь a это всегда четное число. Поэтому выгодно сначала по максимуму использовать для печати двусторонние листы, а если их не хватает — односторонние. Если и односторонних листов не хватает, то текущий комплект распечатать мы не сможем.

int n, x, y;
int a[N];

bool can(int a)
{
	if (a % 2) {
		if (y > 0) a--, y--;
		else if (x > 0)	a--, x--;
		else return false;
	}		
	if (x * 2 >= a)	{
		x -= a / 2;
		return true;
	}
	a -= 2 * x, x = 0;
	if (y >= a) {
		y -= a;
		return true;
	}
	return false;
}

int main() {
	cin >> n >> x >> y;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	int ans = 0;
	for (int i = 0; i < n; i++)	
		if(can(a[i])) ans++;
		else break;					
	cout << ans << endl;
}

649D - Дефрагментация памяти

Для решения данной задачи нужно сформировать массив, который будет равен памяти компьютера после дефрагментации. Для этого, например, можно запомнить про каждый процесс (в порядке слева направо) количество ячеек, которые он занимает. Верно следующее утверждение — пока дефрагментация не закончена, всегда будет две такие ячейки с номерами pos1 и pos2 в памяти компьютера, что ячейка pos1 пуста, а ячейка pos2 занята процессом, который по окончании дефрагментации должен находится в ячейке номер pos1. Таким образом, ответ на задачу, это количество таких ячеек в памяти, которые должны быть заняты каким-то процессом после окончания дефрагментации, причем до начала дефрагментации эти ячейки либо пусты, либо в них записаны другие процессы (отличные от тех, которые должны быть записаны после дефрагментации).

int n;
int a[N], need[N];
int szneed;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] != 0) need[szneed++] = a[i];			
	}
        int ans = 0; 
        for (int i = 0; i < n; i++) {
        	if (need[i] != 0 && need[i] != a[i]) ans++;
        }	
        cout << ans << endl;
}