Разбор задач Experimental Educational Round: VolBIT Formulas Blitz

Revision ru2, by mfv, 2016-02-19 02:02:11

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

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

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

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

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

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

B. Закон Мура

Каждую секунду число умножается на 1.000000011. Умножение несколько раз на одно и то же число эквивалентно возведению в степень. Таким образом, формула n·1.000000011t (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 равно 2n. Но в задаче требуется найти количество счастливых номеров длины \textit{не более} n. Давайте просуммируем их. 21 = 2, 21 + 22 = 2 + 4 = 6, 21 + 22 + 23 = 2 + 4 + 8 = 14, 21 + 22 + 23 + 24 = 2 + 4 + 8 + 16 = 30. Можно заметить, что сумма всех предыдущих степеней двойки равна следующей степени двойки минус первая степень двойки. Так что ответ задачи 2n + 1 - 2.

Одна из возможных реализаций формулы 2n + 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. Без "минус единиц" все столбцы имеют равный размер, и общее количество ячеек равно размеру первого столбца умноженному на количество столбцов. Размер первого столбца (y2 - y1) / 2 + 1. Количество столбцов x2 - x1 + 1. Таким образом, окончательная формула ((y2 - y1) / 2 + 1)·(x2 - x1 + 1) - (x2 - x1) / 2.

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

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

Количество способов выбрать группу из 5 человек из n кандидатов равно количеству сочетаний Cn5, количество способов выбрать группу из 6 человек из n кандидатов равно Cn6, количество способов выбрать группу из 7 человек из n кандидатов равно Cn7, количество способов выбрать группу из 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. Каждое деление даёт целое число, поскольку каждый префикс этой формулы после деления также является числом сочетаний Cni.

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·4n - 3.

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

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

J. Делимость

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

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

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

Tags разбор задач, учебные раунды, вологодский бит, эксперимент

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru9 Russian mfv 2016-02-25 10:30:53 3829
en10 English mfv 2016-02-25 10:20:46 3741
ru8 Russian mfv 2016-02-20 15:03:45 4
ru7 Russian mfv 2016-02-20 11:13:31 1650 O добавлена
en9 English mfv 2016-02-20 11:11:08 1641 O added
ru6 Russian mfv 2016-02-20 11:03:45 4 n-4 пофиксено
en8 English mfv 2016-02-20 11:03:00 4 n-4 bug fixed
en7 English mfv 2016-02-19 19:30:39 10 Tiny change: 'n#### [R. Forecast](http://c' -> 'n#### [R. Game](http://c'
ru5 Russian mfv 2016-02-19 17:08:44 6849 Добавлены задачи.
en6 English mfv 2016-02-19 16:56:04 6778 Some problems added.
ru4 Russian mfv 2016-02-19 02:11:22 38
en5 English mfv 2016-02-19 02:10:32 38
ru3 Russian mfv 2016-02-19 02:08:30 22
en4 English mfv 2016-02-19 02:08:00 22
en3 English mfv 2016-02-19 02:02:33 0 (published)
ru2 Russian mfv 2016-02-19 02:02:11 77 Мелкая правка: 'о правилам модульной ' -
en2 English mfv 2016-02-19 02:00:10 92 Tiny change: ' is `(2LL \
ru1 Russian mfv 2016-02-19 01:54:48 9884 Первая редакция перевода на Русский
en1 English mfv 2016-02-19 01:41:04 10018 Initial revision (saved to drafts)