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;
}

649E - Автобус

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

Целевая функция бинарного поиска должна работать следующим образом. Пусть mid — количество мест в автобусе. Тогда найдем cnt — максимальное количество путешественников, которых мы сможем подвезти на таком автобусе. Это можно сделать с помощью set-a, в котором мы будем хранить позиции выходов путешественников, которые зашли в автобус, и их индексы.

Переберем всех путешественников слева направо (в том порядке, в котором они были отсортированы). Пока в set-е есть путешественники, которые выйдут из автобуса не позднее момента, когда зайдет текущий путешественник, удалим позиции их выходов из set и добавим их индексы в отдельный вектор ans. В противном случае, если самая дальняя позиция выхода путешественника в set-е больше, чем потенциальная позиция выхода текущего путешественника, заменим в set-е самого дальневыходящего путешественника на текущего.

После того, как мы переберем всех путешественников, добавим индексы всех оставшихся в set-е путешественников в ans. Если размер вектора ans меньше a, сдвинем в mid левую границу бинарного поиска, иначе сдвинем в mid правую границу бинарного поиска. После бинарного поиска, запустим еще раз целевую функцию от ответа и выведем индексы путешественников из вектора ans.

int n, a;
vector<pair<pair<int, int>, int > > v;
set<pair<int, int> > s;
vector<int> ans;

int ok (int x) {
	s.clear();
	ans.clear();
	for (int i = 0; i < n; i++) {
		int l = v[i].first.first, r = v[i].first.second;
		while (!s.empty() && s.begin()->first <= l) {
			ans.push_back(s.begin()->second);
			s.erase(s.begin());
		}
		if ((int)s.size() + 1 <= x)	s.insert(mp(r, v[i].second));
		else {
			s.insert(make_pair(r, v[i].second));
			set<pair<int, int> > :: iterator it = s.end();--it;
			s.erase(it);
		}
	}
	while (!s.empty()) {
		ans.push_back(s.begin()->second);
		s.erase(s.begin());
	}
	return (int)ans.size();
}

int main() {
	cin >> n >> a;
	v.resize(n);
	for (int i = 0; i < n; i++)
		cin >> v[i].first.first >> v[i].first.second, v[i].first.second += v[i].first.first, v[i].second = i;
	sort(v.begin(), v.end());
	int l = 0, r = a;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if(ok(mid) >= a)
			r = mid;
		else
			l = mid;
	}
	ok(r);
	cout << r << endl;	
	for (int i = 0; i < a; i++)
		cout << ans[i] + 1 << ' ';	
	cout << endl;
}