Хімія#41

Хімія (Editorial)

Запишемо умову змішування. Маса солі в -й пробірці дорівнює m_i \cdot \frac{p_i}{q_i}. Змішавши пробірки та , отримаємо концентрацію

\frac{m_i \frac{p_i}{q_i} + m_j \frac{p_j}{q_j}}{m_i + m_j} = \frac{p_0}{q_0}.

Позбудемось дробу, помноживши навхрест:

q_0\left(m_i \frac{p_i}{q_i} + m_j \frac{p_j}{q_j}\right) = p_0 (m_i + m_j).

Згрупуємо доданки за номером пробірки:

\underbrace{m_i \frac{p_i q_0 - p_0 q_i}{q_i}}_{v_i} + \underbrace{m_j \frac{p_j q_0 - p_0 q_j}{q_j}}_{v_j} = 0.

Отже, кожній пробірці відповідає одне число v_i — її «відхилення» від цільової концентрації, зважене масою, — і треба знайти пару з v_i + v_j = 0.

Це вже стандартна задача «знайти два числа із заданою сумою»: проходимо пробірки по одній, для кожної шукаємо в хеш-таблиці значення -v_i; якщо знайшли — відповідь, інакше додаємо v_i до таблиці. Так кожна пара розглядається рівно раз, а складність — у середньому.

Головна технічна деталь: v_i — раціональне число, і порівнювати його через дійсні типи не можна через похибку. Зберігайте його як нескоротний дріб: чисельник m_i (p_i q_0 - p_0 q_i) і знаменник q_i, поділені на свій НСД, зі знаком, віднесеним до чисельника. Тоді ключем хеш-таблиці буде пара цілих чисел.

Чисельники сягають великих значень, тому рахуйте у 64-бітному типі. Якщо жодної пари немає, повідомте про це згідно з форматом умови.