В неделе 12 стресс-тест был собран внутри одной программы: перебор и быстрое решение были двумя функциями, а цикл подавал им случайные тесты. Это работает, но проверяется копия решения, переписанная в виде функции. Этот урок собирает стресс-тест так, как это обычно делают на контестах: файл решения ровно в том виде, в каком вы его отправите, перебор во втором файле, генератор в третьем и короткий скрипт, который запускает их друг против друга — вместе с чтением ввода и печатью вывода. Потом урок показывает, как уменьшить найденный тест, что делать, когда правильных ответов несколько, и чего маленькие тесты не поймают никогда.
Задача
Даны n целых чисел и число k. Посчитайте пары позиций i
<j, для которых aᵢ + aⱼ = k. Ограничения: 1 ≤ n ≤ 2 · 10⁵, −10⁹ ≤ aᵢ, k ≤ 10⁹.
Ввод
Вывод
Перебор всех пар — это 2 · 10¹⁰ шагов при самом большом n, поэтому решение
считает с помощью map (неделя 11): для каждого числа x его партнёры — числа,
равные k − x. Посчитаем каждое значение один раз, сложим партнёров всех
элементов и разделим сумму пополам, ведь каждая пара находится с обоих концов:
Пример оно проходит. Но верно ли оно? Вместо того чтобы гадать, проверим.
Три программы и скрипт
Перебор пробует все пары. Для 2 · 10⁵ чисел он слишком медленный, но на десяти числах отвечает мгновенно, и ошибиться в нём негде:
Генератор печатает один случайный тест. Он берёт два числа из командной строки: номер теста, который становится зерном генератора случайных чисел, и наибольшее n, которое можно создать.
int main(int argc, char* argv[]) — так программа получает слова, набранные
после её имени: при запуске gen 17 10 в argv[1] будет "17", а в argv[2] —
"10", и atoi превращает каждое в int. Раз зерно — это номер теста, тест 17
каждый раз получается одним и тем же: gen 17 10 > in.txt вернёт его, когда он
понадобится.
Скрипт запускает три программы тысячу раз. Он рассчитан на то, что решение,
перебор и генератор скомпилированы в sol, brute и gen в одной папке
(например, g++ -O2 pairs.cpp -o sol). В Linux или macOS сохраните это как
stress.sh и запустите bash stress.sh:
В Windows сохраните это как stress.bat и запустите из командной строки в этой
папке, набрав stress.bat:
Оба делают одно и то же для теста 1, 2, 3 и так далее: создают тест, запускают на нём обе программы и сравнивают их вывод с помощью или , которым, как и большинству проверяющих систем, лишние пробелы безразличны. При первом расхождении скрипт печатает тест и оба ответа и останавливается. Обе версии печатают: