математика

**Замечание: время на тест в этой задаче 4 сек, в два раза больше, чем по умолчанию.**

Фермер Джон распределил коров и пакеты по странной схеме на числовой оси, используя следующий процесс:

• ФД выбрал число \(M\) (\(1 \le M \le 10^{18}\)).
• ФД выбрал \(N\) (\(1 \le N \le 2 \cdot 10^4)\) интервалов \([L_i, R_i]\) чтобы распределить коров (\(1 \le L_i \le R_i \le 10^{18}\)). Затем он разместил коров в позициях \(L_i, L_i + M, L_i + 2M, \ldots, R_i\). Гарантируется, что \(R_i - L_i\) кратно \(M\).
• ФД выбирает \(P\) (\(1 \le P \le 2 \cdot 10^4)\) интервалов \([A_i, B_i]\) чтоб распределить пакеты (\(1 \le A_i \le B_i \le 10^{18}\)). Затем он размещает пакеты в позициях \(A_i, A_i + M, A_i + 2M, \ldots, B_i\). Гарантируется, что \(B_i - A_i\) кратно \(M\).

Бесси экспериментирует с мощным имплантатом копыта, который способен создавать мощные ударные волны. Перед ней выстроено \(N\) (\(2 \leq N \leq 10^5\)) плиток, для разрушения которых требуется мощность не менее \(p_0,p_1,\dots,p_{N-1}\), соответственно (\(0 \leq p_i \leq 10^{18}\)).

Бесси может применить силу, ударив по определенной плитке, но из-за странной природы ее имплантата, она не применит никакой силы к плитке, которую она пробьет. Вместо этого, если она решит ударить плитку \(x\) один раз, где \(x\) — это целое число в диапазоне \([0,N-1]\), она применит \(|i-x|\) силу к плитке \(i\) для всех целых чисел \(i\) в диапазоне \([0,N-1]\). Эта сила также является кумулятивной, поэтому применение \(2\) силы дважды к плитке применит в общей сложности \(4\) силы к плитке.

Определите наименьшее количество ударов, необходимое для разбивания всех плиток.

У Фермера Джона есть массив \(a\) из \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) неотрицательных целых чисел и целое число \(M\) (\(1 \leq M \leq 10^9\)). Затем ФД спрашивает у Беси число \(x\). За одну операцию ФД может выбрать индекс \(i\) и вычесть или прибавить \(1\) к \(a_i\). ФД называет число скучным - если оно равно минимальному количеству операций, которые он должен выполнить, чтобы \(a_i-x\) стало делится на \(M\) для всех \(1 \leq i \leq N\).

Среди всех возможных \(x\) выберите минимально возможное скучное число.

Для любых двух положительных целых чисел \(a\) и \(b\) определим функцию \(\texttt{gen_string}(a,b)\) следующим кодом Python:

def gen_string(a: int, b: int):
	res = ""
	ia, ib = 0, 0
	while ia + ib < a + b:
		if ia * b <= ib * a:
			res += '0'
			ia += 1
		else:
			res += '1'
			ib += 1
	return res

Эквивалентный код C++:

string gen_string(int64t a, int64t b) {
	string res;
	int ia = 0, ib = 0;
	while (ia + ib < a + b) {
		if ((__int128)ia * b <= (__int128)ib * a) {
			res += '0';
			ia++;
		} else {
			res += '1';
			ib++;
		}
	}
	return res;
}

\(ia\) будет равно \(a\), а \(ib\) будет равно \(b\), когда цикл завершится, так что это функция возвращает битовую строку длины \(a+b\), содержащую ровно \(a\) нулей и \(b\) единиц. Например, \(\texttt{gen_string}(4,10)=01110110111011\).

Назовём строку битов \(s\) \(\textbf{хорошей}\), если существуют положительные целые числа \(x\) и \(y\) такие, что \(s=\texttt{gen_string}(x,y)\). Даны два натуральных числа \(A\) и \(B\) (\(1\le A,B\le 10^{18}\)), ваша задача состоит в том, чтобы вычислить количество хороших префиксов \(\texttt{gen_string}(A,B)\). Например, есть \(6\) хороших префиксов \(\texttt{gen_string}(4,10)\):

х = 1 | у = 1 | gen_string(х, у) = 01
х = 1 | у = 2 | gen_string(х, у) = 011
х = 1 | у = 3 | gen_string(х, у) = 0111
х = 2 | у = 5 | gen_string(х, у) = 0111011
х = 3 | у = 7 | gen_string(х, у) = 0111011011
х = 4 | у = 10 | gen_string(х, у) = 01110110111011

ОБРАЗЕЦ ВВОДА:

6
1 1
3 5
4 7
8 20
4 10
27 21

ОБРАЗЕЦ ВЫВОДА:

1
5
7
10
6
13

Автор: Benjamin Qi

Беси открыла пекарню!

Она может делать печенье за \(t_C\) единиц времени или булочку за \(t_M\) единиц времени (\(1\le t_C,t_M\le 10^9\)). В каждый момент времени она может делать только один вид выпечки, поэтому чтобы произвести \(A\) печенек и \(B\) булочек, её требуется \(A \cdot t_C + B \cdot t_M\) единиц времени.

У Беси есть \(N\) (\(1\le N\le 100\)) друзей, которые любят заглядывать в пекарню по одному. \(i\)-ый друг делает заказ на \(a_i\) (\(1 \leq a_i\leq 10^9\)) печенек и \(b_i\) (\(1 \leq b_i \leq 10^9\)) булочек немедленно после входа. У Беси нет места хранить выпечку, поэтому она начинает изготовление сразу после получения заказа. Кроме того, друзья Беси очень заняты и не могут ждать более \(c_i\) (\(a_i + b_i \leq c_i \leq 2 \cdot 10^{18}\)) единиц времени, после чего печалятся и уходят.

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

Для каждого из \(T\) (\(1 \leq T \leq 100\) подтестов помогите Беси вычислить минимальное количество муни, которое ей требуется потратить так, чтобы её пекарня могла удовлетворить всех друзей.

**Замечание: Время на тест 3 сек, в 1.5 раза больше чем по умолчанию.**

Фермер Джон дал Беси масив \(a\) длины \(N\) (\(2\le N\le 500, -10^{15}\le a_i\le 10^{15}\)) и все \(\frac{N(N+1)}{2}\) суммы непрерывных подмассивов различны. Для каждого индекса \(i\in [1,N]\), помогите Беси вычислить минимальное количество действий, чтобы изменить \(a_i\) так, чтобы появились два различных непрерывных подмассива \(a\) с равными суммами.

Беси устала и потому не хочет решать задачу, но у неё есть план. Поскольку ответы только "yes" и "no", она решила непрерывно посылать такое решение

if input == sample_input:
  print sample_output
else:
  print "yes" или "no" с независимой вероятность 1/2 для каждого теста. 

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

Беси знает, что она может послать решение не более чем \(K\) (\(1\le K\le 10^9\)) раз поскольку иначе она будет дисквалифицирована. Каково максимальное значение счета Беси, если она будет придерживаться оптимальной стратегии?

В любой момент времени, когда два мира находятся на одной и той же \(y\)-координате (возможно в дробное время), порталы "выравниваются". Это означает, что корова из одного из этих миров, может используя эти порталы мгновенно перебраться в другой мир.

Для каждого \(i\) корова из мира \(i\) хочет перебраться в мир \(Q_i\) (\(Q_i\neq i\)). Определите для каждой коровы, сколько времени ей понадобиться, чтобы перебраться в желаемый мир, если она будет путешествовать оптимально.

Ответ на каждый запрос необходимо вывести в виде дроби \(a/b\), где \(a\) и \(b\) положительные и взаимно простые целые числа. Выведите \(-1\) если путешествие невозможно.

Замечание: Здесь, \(a\oplus b\) обозначает побитовое исключающее ИЛИ неотрицательных целых чисел \(a\) и \(b\). Эта операция эквивалентна сложению соответствующих пар битов по модулю 2 и игнорированию переноса. Например

У Беси есть \(N\) (\(1\le N\le 2\cdot 10^4\)) ящиков с компонентами. \(i\)-ый ящик содержит компоненты с номерами от \(l_i\) до \(r_i\) включительно \((0\le l_i \le r_i \le 10^9)\). Никакие два ящика не содержат одинаковые компоненты. Беси хочет узнать, сколько уникальных микстур из трёх различных компонент она может создать. Две микстуры рассматриваются как различные, если хотя бы одна компонента есть в одной микстуре и отсутствует в другой. Ответ выводите по модулю \(10^9 + 7\).

SCORING

• В тестах 3-4 \(\max(K,r_N)\le 10^4\).
• В тестах 5-6 \(K=2^k-1\) для некоторого целого \(k\ge 1\).
• В тестах 7-11 \(\max(K,r_N)\le 10^6\).
• В тестах 12-16 \(N\le 20\).
• В тестах 17-21 нет дополнительных ограничений.