Запишемо умову змішування. Маса солі в -й пробірці дорівнює m_i \cdot \frac{p_i}{q_i}. Змішавши пробірки та , отримаємо концентрацію
Позбудемось дробу, помноживши навхрест:
Згрупуємо доданки за номером пробірки:
Отже, кожній пробірці відповідає одне число 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-бітному типі. Якщо жодної пари немає, повідомте про це згідно з форматом умови.