A. Опять двадцать пять!

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

Таким образом,

Заметим, что 5² = 25. Затем

И так далее. Все равны 25 для всех n ≥ 2.

Таким образом, чтобы решить задачу, требуется всего лишь вывести число 25. Даже не требуется читать n.

B. Закон Мура

Каждую секунду число умножается на 1.000000011. Умножение несколько раз на одно и то же число эквивалентно возведению в степень. Таким образом, формула n·1.000000011^t (1.000000011 в степени t, умноженное на n). При написании программы не следует использовать цикл для вычисления степени, поскольку это слишком долго для такого большого n, обычно язык программирования предоставляет функцию для возведения в степень такую как pow.

C. Счастливые номера

Существует 2 счастливых номера длины 1. Это 7 и 8. Существует 4 счастливых номера длины 2. Это 77, 78, 87 и 88. Существует 8 счастливых номеров длины 3. Это 777, 778, 787, 788, 877, 878, 887, 888. При каждом добавлении 1 к длине числа количество счастливых номеров увеличивается в 2 раза. Это легко доказывается: к любому числу предыдущей длины можно дописать 7 или 8, так что число предыдущей длины создаёт два числа следующей длины.

Таким образом, для длины n количество счастливых номеров длины \textit{ровно} n равно 2ⁿ. Но в задаче требуется найти количество счастливых номеров длины \textit{не более} n. Давайте просуммируем их. 2¹ = 2, 2¹ + 2² = 2 + 4 = 6, 2¹ + 2² + 2³ = 2 + 4 + 8 = 14, 2¹ + 2² + 2³ + 2⁴ = 2 + 4 + 8 + 16 = 30. Можно заметить, что сумма всех предыдущих степеней двойки равна следующей степени двойки минус первая степень двойки. Так что ответ задачи 2^n + 1 - 2.

Одна из возможных реализаций формулы 2^n + 1 в языке программирования — это сдвинуть 1 побитово влево на n + 1 двоичный разряд или сдвинуть 2 побитово влево на n двоичных разрядов. Например, в Java формула ответа задачи (2L << n) - 2, в C++ (2LL << n) - 2. Суффиксы L и LL соответственно требуются, чтобы результат выражения сдвига имел 64-битный целый тип (long в Java и long long в C++). Тип второго операнда не влияет на тип выражения сдвига, только тип первого операнда. Также требуются скобки, поскольку без них сначала производится вычитание и только затем битовый сдвиг.

D. Шестиугольники!

Посчитаем количество ячеек, имеющих расстояние ровно n. Для n = 0 это 1, для n = 1 это 6, для n = 2 это 12, для n = 3 это 18 и так далее. Можно заметить, что n = 0 является особым случаем, а дальше количество увеличивается каждый раз на 6. Эти числа составляют арифметическую прогрессию. В задаче нам нужно просуммировать эти числа. Формула суммы арифметической прогрессии (первый + последний)·количество / 2. Первый 6, последний 6n, количество n. Сумма получается (6 + 6n)n / 2 = 3(n + 1)n. И плюс 1, которая не входит в арифметическую прогрессию. Таким образом, окончательная формула 1 + 3n(n + 1).

Чтобы избежать переполнения, умножение в формуле нужно выполнять в 64-битном целом типе. Для этого хотя бы один из членов выражения (3 или 1 или n) должен иметь 64-битный целый тип. Литералы имеют 64-битный целый тип, когда у них есть суффикс L в Java или LL в C++.

E. Прямоугольник

Посмотрим, как меняется количество затронутых ячеек в зависимости от столбца. Например, 3, 2, 3, 2, 3. То есть оно чередуется между размером первого столбца и размером первого столбца минус один. Количество "минус единиц" равно количеству столбцов делённому нацело на 2. Без "минус единиц" все столбцы имеют равный размер, и общее количество ячеек равно размеру первого столбца умноженному на количество столбцов. Размер первого столбца (y₂ - y₁) / 2 + 1. Количество столбцов x₂ - x₁ + 1. Таким образом, окончательная формула ((y₂ - y₁) / 2 + 1)·(x₂ - x₁ + 1) - (x₂ - x₁) / 2.

Чтобы избежать переполнения, произведение должно вычисляться в 64-битном целом типе.

F. Подбор кадров

Количество способов выбрать группу из 5 человек из n кандидатов равно количеству сочетаний C_n⁵, количество способов выбрать группу из 6 человек из n кандидатов равно C_n⁶, количество способов выбрать группу из 7 человек из n кандидатов равно C_n⁷, количество способов выбрать группу из 5, 6 или 7 человек из n кандидатов равно .

Чтобы избежать переполнения 64-битного целого типа, можно вычислить следующим образом: n/1*(n-1)/2*(n-2)/3*(n-3)/4*(n-4)/5*(n-5)/6*(n-6)/7. Каждое деление даёт целое число, поскольку каждый префикс этой формулы после деления также является числом сочетаний C_nⁱ.

G. Переходящие вымпелы

Прежде всего, способы разместить оба типа вымпелов независимы. То есть каждый способ разместить вымпелы "Исправил критичный баг" по n столам совместим с каждым способом разместить вымпелы "Предложил новую фичу" по n столам. Таким образом, ответ задачи равен количеству способов разместить вымпелы "Исправил критичный баг" умножить на количество способов разместить вымпелы "Предложил новую фичу".

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

Таким образом, полная формула для задачи .

Чтобы избежать переполнения 64-битного целого типа рекомендуемые формулы для вычислений (n + 2) / 1 * (n + 1) / 2 * n / 3 и (n + 4) / 1 * (n + 3) / 2 * (n + 2) / 3 * (n + 1) / 4 * n / 5.

H. Скамейки

Количество способов выбрать 5 дорожек, идущих с востока на запад, на которых будут скамейки, из n составляет . Есть n способов разместить скамейку на первой из этих дорожек. При фиксированном месте первой скамейки существует n - 1 способ размещения скамейки на второй из этих дорожек, потому что одна из дорожек, идущих с севера на юг, уже занята ранее расставленной скамейкой. При фиксированном месте первой и второй скамейки существует n - 2 способа размещения скамейки на третьей из этих дорожек, потому что два дорожки, идущие с севера на юг, уже заняты ранее расставленными скамейками. Аналогично получаем n - 3 и n - 4 для четвёртой и пятой скамеек. Общее количество способов разместить скамейки на выбранных 5 дорожках, идущих с востока на запад, составляет n(n - 1)(n - 2)(n - 3)(n - 4). Таким образом, формула для задачи .

Чтобы избежать переполнения 64-битного целого типа рекомендуемый порядок вычислений ровно такой как в формуле выше, деление не должно быть последней операцией.

I. Автостоянка

Есть следующие способы разместить n машин одной марки. Они могут быть первыми n, последними n, а также они могут быть где-то в середине стоянки.

Когда n машин одной марки первые или последние, существует 4 способа выбрать марку этих n машин, затем существует 3 способа выбрать марку одной машины, смежной с ними (марка должна отличаться от марки этих n машин), и 4 способа выбрать марку каждой из оставшихся n - 3 машин. Таким образом, формула для случая n машин одной марки на любом из концов стоянки 4·3·4^n - 3.

Когда n машин одной марки расположены где-то в середине стоянки, существует 4 способа выбрать марку этих n машин, затем существует 3 способа выбрать марку каждой из двух машин, соседствующих с ними (марки этих двух машин должны отличаться от марки этих n машин), и 4 способа выбрать марку каждой из оставшихся n - 4 машин. Таким образом, формула для случая n машин одной марки в конкретной позиции где-то в середине стоянки 4·3²·4^n - 4.

Существует 2 позиции n машин одной марки на концах стоянки и n - 4 позиции n машин одной марки где-то в середине стоянки. Окончательная формула 2·4·3·4^n - 3 + (n - 4)·4·3²·4^n - 4.

J. Делимость

Разложим на простые множители числа от 2 до 10. 2 = 2, 3 = 3, 4 = 2², 5 = 5, 6 = 2·3, 7 = 7, 8 = 2³, 9 = 3², 10 = 2·5. Если число делится на все числа от 2 до 10, его разложение на простые множители должно содержать 2 хотя бы в степени 3, 3 хотя бы в степени 2, 5 и 7 хотя бы в степени 1. Так что оно может быть записано как x·2³·3²·5·7 = x·2520. Таким образом, любое число, делящееся на 2520, является делящимся на все числа от 2 до 10.

Существует чисел от 1 до n делящихся на все числа от 2 to 10. В языке программирования обычно это реализуется как просто деление нацело.

Разбор задач K-R появится здесь через несколько часов.