Смешанные задачи на реализацию

До сих пор каждая неделя давала вам инструмент, а потом задачи, которым явно нужен именно он. На контесте так не бывает: задача описывает ситуацию и просит найти ответ, и никто не пишет в начале «это задача на сортировку». Понять, какие инструменты нужны в этой ситуации, и соединить их в одну программу — вот о чём эта неделя. Сами инструменты у вас уже есть: ввод и вывод, условия, циклы, массивы, строки, функции, сортировка, стеки, очереди, множества и словари.

Длинная задача редко бывает трудной из-за одного трудного шага. Она трудна потому, что шагов много, и одно неверно понятое слово уводит их все не туда. Поэтому работайте в одном и том же порядке:

Прочитайте дважды и перескажите

Первое чтение — для истории, второе — для деталей. При втором чтении найдите четыре вещи: что именно дано, что именно нужно вывести, какие ограничения и что условие говорит о необычных случаях — «если такой пары нет, выведите −1», «если ответов несколько, выведите наименьший». Заметьте и то, есть ли во входных данных несколько тестов: тогда все суммы и счётчики для каждого теста заводятся заново.

Потом сформулируйте задачу одним предложением, без истории. «Бекзод торгует на рынке и записывает каждую заработанную монету…» превращается в «выведите сумму n чисел». Если одним предложением сформулировать не получается, вы ещё не поняли задачу: перечитайте её и разберите пример вручную, пока не получится.

Проверьте ограничения

Ограничения под условием — не украшение. Два из них решают, какой будет программа, ещё до того, как вы напишете первую строку.

Они определяют типы. int вмещает значения до 2 147 483 647, примерно 2,1 · 10⁹. Подставьте в формулу самые большие допустимые значения: 10⁵ чисел до 10⁹ каждое дают в сумме 10¹⁴. Если результат может превысить 2 · 10⁹, берите long long — он вмещает примерно до 9,2 · 10¹⁸.

Они определяют скорость. Компьютер делает примерно 10⁸ простых шагов в секунду. Посчитайте шаги своей идеи для самого большого n: