Решение задачи № 3.3 с 1 этапа НТО 2022-2023 по информатике

1solution.cpp

#include <bits/stdc++.h>

using namespace std;

#define NUM_EPOCHS 250000

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	std::random_device rd;
	std::mt19937 rng(rd());

	int n;
	cin >> n;

	vector<int> a(n);
	for(int i = 0; i < n; ++i) cin >> a[i];

	vector<int> b(n);
	for(int i = 0; i < n; ++i) cin >> b[i];

	vector<double> alp(n);
	for(int i = 0; i < n; ++i) alp[i] = (double)b[i] / ((double)a[i] + b[i]);

	double cur_sum = 0;
	for(int i = 0; i < n; ++i) cur_sum += a[i] * alp[i];

	std::uniform_int_distribution<int> nrng(0, n-1);
	std::uniform_real_distribution<double> drng(0.0, 1.0);
	std::uniform_int_distribution<int> brng(0, 1);

	vector<int> ind(n);
	iota(ind.begin(), ind.end(), 0);

	for(int i = 0; i < NUM_EPOCHS; ++i){
		int ch1 = nrng(rng);

		double d1;
		if(brng(rng) == 1){
			d1 = drng(rng)*(1-alp[ch1]);
		}else{
			d1 = -drng(rng)*alp[ch1];
		}

		shuffle(begin(ind), end(ind), rng);
		for(int ch2 : ind){
			if(ch2 == ch1) continue;

			double d2 = -(a[ch1]+b[ch1]) * d1 / (a[ch2]+b[ch2]);
			if(alp[ch2]+d2 < 0 || alp[ch2]+d2 > 1){
				continue;
			}

			alp[ch1] += d1;
			alp[ch2] += d2;

			double new_sum = 0;
			for(int i = 0; i < n; ++i) new_sum += a[i] * alp[i];

			if(new_sum > cur_sum){
				cur_sum = new_sum;
			}else{
				alp[ch1] -= d1;
				alp[ch2] -= d2;
			}

			break;
		}
	}

	printf("%.16f", cur_sum);
}

problem.md

Задача 3.3. Справедливый дележ

[реализация]

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

Рассмотрим пример. Есть три вида пряностей: перец, ваниль и корица. Стоимость всей партии перца в первом и втором городах составляет 120 и 200 условных единиц соответственно. Аналогичная стоимость партии ванили равна 180 и 140 условных единиц, а корицы — 100 и 60 условных единиц. Допустимым способом дележа будет, например, следующий: первый купец возьмет всю ваниль, второй — весь перец, а корицу они поделят поровну. Тогда стоимость доли первого купца в первом городе будет равна 180 + 100 ⋅ 0.5 = 230. Стоимость доли второго купца во втором городе составит 200 + 60 ⋅ 0.5 = 230. Стоимости долей равны, поэтому такой вариант дележа допустим. Но более выгодным будет другой вариант. Первый купец возьмет всю корицу и 3/4 ванили, а второй купец — весь перец и 1/4 ванили. Тогда стоимость доли в первом городе составит 100 + 180 ⋅ 0.75 = 235 и 200 + 140 ⋅ 0.25 = 235 во втором городе. Таким образом, второй вариант является более предпочтительным.

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

Формат входных данных

На вход в первой строке подается одно натуральное число nnn — количество видов пряностей, 1 ≤ n ≤ 100. Во второй строке через пробел записаны nnn натуральных чисел a1, a2, …, an — цены всех видов пряностей в первом городе. Аналогично в третьей строке записаны числа b1, b2, …, bn — цены всех видов пряностей во втором городе, 1 ≤ ai, bi ≤ 10^6.

Формат выходных данных

Программа должна вывести одно число — максимальную стоимость долей. Это число может быть вещественным. Ответ будет считаться верным, если он отличается от ответа жюри не более чем на 0.01.

Методика проверки

Программа проверяется на 32 тестах. Прохождение каждого теста оценивается в 1 балл. В первых восьми тестах n ≤ 3. В первых 20 тестах n ≤ 10. Тесты из условия задачи при проверке не используются.

Sample Input 1:

3 120 180 100 200 140 60

Sample Output 1:

235.0

Sample Input 2:

1 100 200

Sample Output 2:

66.66666666666667

solution.md

Идея решения

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

Замечу, что такая идея решения довольно похожа на одно из решений задачи № 7 «Хорошие раскраски» с регионального этапа ВсОШ за 2021 год.

Реализация

Теория

Пусть α1, α2, ..., αn — доли первого купца по каждому товару. Тогда доли второго купца имеют вид 1-α1, 1-α2, ..., 1-αn. α1, α2, ..., αn ∈ [0, 1]

По условию имеем: α1⋅a1 + α2⋅a2 + ... + αn⋅an = (1-α1)b1 + (1-α2)b2 + ... + (1-αn)bn

Немного преобразовав, получим: α1(a1+b1) + ... + αn(an+bn) = b1 + b2 + ... + bn

Так как b1 + b2 + ... + bn = const, мы эту сумму примем за инвариант.

Поэтому задача сводится к поиску максимума выражения α1⋅a1 + α2⋅a2 + ... + αn⋅an при выполнении условия: α1(a1+b1) + ... + αn(an+bn) = const

Изменение переменных при сохранении суммы

Найдём способ изменять две переменные так, чтобы сумма α1(a1+b1) + ... + αn(an+bn) оставалась прежней; Пусть мы заменяем αi на αi + Δαi и αj на αj + Δαj. Тогда должно выполняться:

αi(ai+bi) + αj(aj+bj) = (αi+Δαi)(ai+bi) + (αj+Δαj)(aj+bj) Δαi(ai+bi) + Δαj(aj+bj) = 0 Δαj = -Δαi(ai+bi)/(aj+bj)

Таким образом, зная индесы i, j изменяемых элементов и изменение одного из них Δαi, мы можем найти изменение второго Δαj.

Алгоритм

Отсюда следует такой алгоритм:

• выбираем случайный элемент αi;
• изменяем его на случайное Δαi так, чтобы αi по-прежнему лежал на отрезке [0, 1];
• перебираем в случайном порядке остальные элементы αj, вычисляем Δαj. Если αj+Δαj по-прежнему лежит на отрезке [0, 1], то останавливаемся на данном j, иначе продолжаем перебор;
• если такое αj найдено, то изменяем αj на полученное Δαj и находим новую сумму выражения α1⋅a1 + α2⋅a2 + ... + αn⋅an. Если она оказывается больше предыдущей, то оставляем изменения и записываем новую сумму в промежуточный ответ, иначе откатываем изменения по αi и αj. Отправляемся на следующий цикл, взяв новое αi и новое Δαi;
• если же такое αj в итоге не найдено, то откатываем неудачное изменение αi и отправляемся на следующий цикл, взяв новое αi и новое Δαi;
• повторяем данную процедуру нужное количество раз.

Таким образом, алгоритм будет менять две случайные переменные так, чтобы:

• сумма выражения α1(a1+b1) + ... + αn(an+bn) не менялась;
• сумма выражения α1⋅a1 + α2⋅a2 + ... + αn⋅an не уменьшалась;
• была ненулевая вероятность, чтобы сумма выражения α1⋅a1 + α2⋅a2 + ... + αn⋅an увеличилась, если мы ещё не достигли максимума.

Третий пункт выполняется, ибо функция α1⋅a1 + α2⋅a2 + ... + αn⋅an непрерывна, так как представляет собой линейную комбинацию переменных.

Количество повторений цикла

Осталось определить количество раз, которое нужно эту процедуру запустить. Самый простой способ, раз на олимпиаде не ограничено количество посылок, — экспериментальный, то есть подобрать это количество раз так, чтобы было как можно больше OK и как можно меньше Time limit и Wrong answer.

На 500000 я получал несколько Time limit, на 100000 — несколько Wrong answer. На 250000 все тесты выдали OK, поэтому я остановился на данном значении.