Задачи Областной школьной олимпиады 2018

На Одесской областной олимпиаде школьников 2018 года мы предложили 12 задач различной степени сложности. Результаты можно найти здесь.
Условия задач, их короткий разбор мы попытались сделать на этой странице.
Решать задачи можно на сайте acm.pp.ua после простой регистрации. Соревнование №12.


Первые три задачи получились разбиением одной задачи, на три этапа для последовательного решения.

Задача A. Секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

На часах сейчас $s$ секунд. Сколько секунд они будут показывать через $t$ секунд?

Входные данные: Два целых числа через пробел – $s \left(0 \le s \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Одно целое число – новые показания секунд на часах.

Вход Выход
2 3 4
25 50 15

На что обратить внимание

  • Значения параметра t выходит за пределы знакового 32-битного числа $\left[-2^{31};2^{31}-1\right]$
  • . Необходимо знать как кодируются целые числа и выбрать такой тип, чтобы данные и результаты вычислений не выходили за его пределы.

  • Нужно заметить, что каждые $60$ секунд показания возвращаются к исходному значению. Значит для решения следует использовать операцию остатка от деления на $60.$
A. Решение на С++
A. Решение на Java
A. Решение на C#

Задача B. Минуты и секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Часы сейчас показывают $s$ секунд и $m$ минут. Сколько они будут показывать через $t$ секунд?

Входные данные: Три целых числа через пробел – $s, m \left(0 \le s, m \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Два целых числа через пробел – новые показания минут и секунд.

Вход Выход
44 25 22 26 6
59 58 121 1 0

На что обратить внимание

  • Если предыдущая задача решена, то следует разобраться только с минутами. Нужно разобраться сколько пройдёт минут, если было $s$ секунд и прошло ещё $t$. Для этого придётся суммарное количество секунд разделить на $60$ — число секунд в минуте.
  • Поскольку минутная стрелка через $60$ минут вернётся к тем же показаниям, нужно снова взять остаток от деления на $60.$
  • Хотя условие задачи укладывается всего в пару строк, читать его нужно внимательно. Небольшое упражнение на внимательность состоит в том, что минуты и секунды на входе и выходе должны следовать в различном порядке.
B. Решение на C++

Задача C. Часы, минуты, секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

На часах сейчас $h$ часов, $m$ минут и $s$ секунд. Сколько они будут показывать через $t$ секунд?

Входные данные: Четыре целых числа через пробел – $h \left(0 \le h \le 23\right), m, s \left(0 \le s, m \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Три целых числа через пробел – новые показания часов, минут и секунд.

Вход Выход
23 59 59 66 0 1 5

На что обратить внимание

  • Кроме того, что период повторения часов составляет $24 \times 60 \times 60$ секунд особенно добавлять здесь нечего.
C. Решение на C++
В решении предлагается другой подход решения задачи. Предлагается перевести текущие показания часов в секунды. После этого увеличим текущее время на требуемое число секунд. Полученный результат можно будет снова перевести в часы, минуты и секунды. такой подход работает для самых разных задач в которых данные задаются в сложной системе единиц. Например, фунт стерлингов, шиллинг, пенс, фартинг, гинея, крона. Достаточно перевести все в наименьшие единицы, если все остальные соответствуют их целому числу. В общем случае, такой универсальной единицей может стать наибольший общий делитель всех используемых единиц.

Следующие две задачи также укладываются в некоторую цепочку. Вторая задача отличается от первой снятием ограничения на направление вырезания и это делает ее гораздо более сложной.

Задача D. Вырезаем прямоугольник в клеточку

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется лист из тетради в клеточку размером $H \times W$ клеток. Определите, можно ли из него вырезать прямоугольник размером $h \times w$. Резать можно только по линиям.

Входные данные: Четыре целых числа через пробел – $H, W, h, w$. Все числа положительные и меньше $2^{31}.$

Выходные данные: Выведите $1$ если требуемый прямоугольник вырезать можно или $0$ если нельзя.

Вход Выход
5 8 10 1 0
5 8 6 4 1

На что обратить внимание

  • Вырезать можно двумя способами — вдоль листа или поперек. Нужно убедиться, что в каком-то из этих положений все поместится.
D. Решение на C++

Задача E. Вырезаем прямоугольник снова

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется лист бумаги размером $H \times W$ миллиметров. Определите, можно ли из него вырезать прямоугольник размером $h \times w$ миллиметров.

Входные данные: Четыре целых числа через пробел – $H, W, h, w.$ Все числа не превышают $500$.

Выходные данные: Выведите $1$ если требуемый прямоугольник вырезать можно или $0$ если нельзя.

Вход Выход
5 8 7 7 0
8 8 10 1 1

На что обратить внимание

  • Конечно главное отличие задачи от предыдущей совсем не в том, что клеточки заменили на миллиметры.
  • В этой задаче вырезать можно не только вдоль сторон листа, но и под любым углом к ним.
  • Если Вы уже знаете тригонометрию, то вам достаточно разместить прямоугольник под некоторым углом $\alpha$ и просчитать ширину и высоту охватывающего его листа. Останется только подобрать правильный угол. Недостаток этого способа состоит в том, что необходимо уметь пользоваться тригонометрическими функциями и обратными к ним.
  • Школьники в 8-м классе ещё не знают тригонометрических функций. Но есть возможность получить более изящное решение, без их использования. Это решение приводится под спойлером, но лучше попытайтесь найти его самостоятельно.
E. Решение на C++

И снова две задачи, вторая из которых лишена одного из ограничений. И снова, снятие ограничения делает вторую задачу более сложной. Точнее менее очевидной.

Задача F. Режем масло

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется прямоугольный брусок масла размером $X \times Y \times Z.$ Плоскими разрезами его нужно разделить на кубики со стороной $1.$
Какое минимальное число разрезов нужно будет сделать если каждый из полученных при разрезании кусочков нужно резать отдельно от остальных?

Входные данные: Три целых положительных числа через пробел – $X, Y$ и $Z$ каждое из которых не превышает $2^{21}.$

Выходные данные: Одно целое число — минимальное количество разрезов.

Вход Выход
1 1 2 1
3 2 5 29

На что обратить внимание

  • Я сторонник аналитического подхода к этой задаче. Рассуждаем так. У нас один кусочек. Каждый разрез добавляет ещё один кусочек. Т.е. кусочков получается на $1$ больше, чем разрезов. Но мы легко можем вычислить сколько должно получиться кусочков — мы ведь знаем размеры.
F. Решение на C++

Задача G. Режем масло снова

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется прямоугольный брусок масла размером $X \times Y \times Z.$ Плоскими разрезами его нужно разделить на кубики со стороной 1.
Какое минимальное число разрезов нужно будет сделать если разрезать можно сразу стопку из любого количества кусочков?

Входные данные: Три целых положительных числа через пробел – $X, Y$ и $Z$ каждое из которых не превышает $2^{21}.$

Выходные данные: Одно целое число — минимальное количество разрезов.

Вход Выход
1 1 2 1
3 2 5 6

На что обратить внимание

  • Теперь можно резать по несколько кусков сразу. Если не знаете как это, понаблюдайте как мама нарезает картошку маленькими кубиками. Она ведь режет сразу несколько пластинок, а не по одной?
  • Представьте, что у на некоторой стадии у Вас получилось два кусочка и один из них больше другого по всем размерам. Если Вы будете резать больший из них, то при этом заодно разрежется и второй.
    Это справедливо для любого числа кусков. Значит стоит рассматривать только самый большой кусок.
  • Стоит резать так, чтобы больший из кусков был поменьше. Т.е. примерно пополам (с округлением вверх).
  • Делим на два каждую из сторон до тех пор пока не получим единицу. Количество делений и есть ответ.
G. Решение на C++
Я привожу решение, которое использует логарифм по основанию два. Логарифмы изучаются только в конце выпускного класса. Если вы еще не добрались до логарифмов в школе, не беда. Просто напишите функцию f() при помощи цикла деления пополам с округлением в большую сторону и сосчитайте сколько раз придется делить. Код от этого не станет намного длиннее и работать будет также с близкой скоростью.

Задача H. Ибн аль-Хайсам задумался!

Лимит времени: 0.5 сек
Лимит памяти: 128MiB

Дано целое число $n$. Вычислите остаток от деления на $n$ произведение всех чисел от $1$ до $n-1.$

Входные данные: Целое число $n \left( 1 \lt n \lt 2^{31}\right).$

Выходные данные: Выведите значение выражения, требуемое в условии.

Вход Выход
7 6
10 0

На что обратить внимание

  • Если $n$ не является простым, то все его делители обязательно встретятся в качестве сомножителей при вычислении этого длинного произведения. Значит остаток будет равен нулю.
  • Ой! Число $4$ явно исключение из этого правила. Добавим для него условный оператор.
  • Остались простые числа. Понаблюдаем за ними написав цикл вычисления требуемого значения.
    Везде получается $n-1$? Попробуем отправить решение.
  • Если Вас заинтересовал последний факт и Вы хотите доказать его (хотя на соревновании достаточно простого удачного наблюдения), то Вы повторяете путь, который проделал в своё время Ибн аль-Хайсам. Сейчас этот результат принято называть теоремой Вильсона. Для неё напридумывали много простых и изящных доказательств. Даже геометрических. Но гораздо интереснее попытаться доказать ее самому. Там совсем не сложно догадаться.
H. Решение на C++
Функция prime() осуществляет прямую проверку числа на простоту. Т.е. просто перебираются все возможные нетривиальные делители. В приведенной ниже реализации сделаны некоторые весьма наивные попытки ускорить работу. Например, сразу исключены числа десятичная запись которых заканчивается на 0, 2, 4, 5, 6 или 8. Конечно, кроме самих чисел 2 и 5, которые являются простыми. Далее в цикле проверяются все возможные нечетные делители, т.к. чётные уже исключены. Перебор ведётся до $\sqrt{n}$. Из-за погрешности вычислений может быть пропущен делитель в точности равный $\sqrt{n}$. Чтобы избежать этой ситуации проверка ведется до $\sqrt{n+1}$. Задание единицы в виде 1.L приводит к тому, что вычисления выполняются с повышенной точностью ( long double). В данном случае эта перестраховка используется только как повод упомянуть этот полезный иногда тип данных.

Задача I. Настолько ли просты эти числа?

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Число называется простым если оно делится только на 1 и на само себя. Найдите наибольший общий делитель всех введенных простых чисел.

Входные данные: В первой строке указывается количество простых чисел 1 < n < 10000. Во второй строке через пробел следуют n простых чисел меньших 231.

Выходные данные: Одно целое число — наибольший общий делитель всех введенных простых чисел.

Вход Выход
4
2 3 5 7
1

На что обратить внимание

  • В предыдущей задаче пришлось поработать с простыми числами. В этой почти тривиальной задаче мы закрепляем понимание их определения. Те участники, которые не смогли справится с предыдущей задачей получают эту в качестве некоторого утешительного приза.
  • Простые числа делятся только на 1 и на само себя. Значит наибольшим общим делителем может быть только один из этих двух вариантов.
  • Типичная ошибка — всегда выводить 1. Правильно было бы заметить, что если все числа одинаковы, то НОД всё же не 1, а само число.
I. Решение на C++

Задача J. Деньги

Лимит времени: 0.4 сек
Лимит памяти: 128MiB

В стране выпущены банкноты номиналом 500, 200, 100, 50, 20, 10, 5 и 1 гривну. А также монеты достоинством 0.5, 0.25, 0.1, 0.05, 0.02 и 0.01 гривны. Требуется найти способ выдать сумму в n гривен, используя наименьшее количество банкнот и монет.

Входные данные: Одно положительное действительное число n, не превышающее 1010, которое задаёт сумму с точностью до копеек.

Выходные данные: В одной строке следует вывести пары чисел через пробел — номинал банкноты (или монеты) и количество банкнот (или монет) этого номинала к выдаче. Значения следует перечислять в порядке увеличения номиналов денежных знаков.

Вход Выход
436.24 0.02 2 0.1 2 1 1 5 1 10 1 20 1 200 2

На что обратить внимание

  • Задача и простая и глубокая одновременно. Простая, поскольку решается интуитивно понятным жадным методом. Глубокая, поскольку может (и должна!) навести на мысли о поисках условия при которых этот жадный метод действительно даёт решение задачи. Т.е. каким условиям должны удовлетворять номиналы монет, чтобы жадный выбор давал оптимальное решение? Речь идёт о так называемых канонических монетных системах.
  • Жадный принцип требует начинать выдавать сумму с самых крупных купюр. Условие требует печатать ответ с самых мелких монет. Автор вредничает. Что делать? Конечно можно записать все количества в массив и напечатать его с конца. В приведенном ниже авторском решение используется другой подход — формируется строка ответа в которой новые данные вставляются в начало. Т.е. для формирования ответа можно использовать массивы или строки.
J. Решение на C++

Задача K. Одни плюсы

Лимит времени: 2 сек
Лимит памяти: 128MiB

Для заданного целого положительного числа n составьте равное ему арифметическое выражение, используя только операции сложения, умножения, скобки и число 1, содержащее минимально возможное число единиц.
Например, 7 = (1 + 1 + 1) * (1 + 1) + 1.

Входные данные: Одно целое положительное число n ≤ 104.

Выходные данные: Минимально возможное количество единиц.

Вход Выход
7 6

На что обратить внимание

  • Планировалась как самая сложная задача соревнования. Решение занимает целых 18 строк.
  • Задача относится к одному из самых красивых и популярных направлений в олимпиадном программировании. Имеется в виду так называемая «динамика» — динамическое программирование. Конечно, для решения задачи совсем не обязательно об этом знать, можно и так догадаться. Но знания и тренировка лучший помощник природной смекалке и сообразительности.
  • Для каждого числа есть возможность либо представить его в виде суммы единицы и числа на единицу меньшего, либо в виде произведения двух других чисел. Из этих двух вариантов выбираем тот в котором меньше единиц. А как узнать количество единиц в этих новых числах? Рекурсивным применением этого подхода. Рано или поздно мы получим просто 1 и процесс завершится.
  • Меморизация! Т.е. запоминание полученных результатов. Если мы уже вычислили кратчайшее представление некоторого числа (например, 2=1+1 или 5=(1+1)(1+1)+1), то это нужно запомнить и когда это число встретится в вычислениях снова, без повторных вычислений сразу использовать ранее полученный результат.
K. Решение на C++

Задача L. Комплексный обед

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

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

Входные данные: В первой строке заданы два целых положительных числа n ≤ 105 и k ≤ 109. Во второй строке следуют через пробел целые положительные числа задающие стоимости каждого из этих n блюд.

Выходные данные: Максимально возможное количество вариантов комплексных обедов.

Вход Выход
5 8
1 9 7 2 4
2

На что обратить внимание

  • Задача «на сортировку» или «на жадные алгоритмы».
  • Если расположить все блюда по возрастанию (или убыванию) цены, то нам останется найти для каждого блюда из числа более дорогих парное из числа более дешевых.
  • Логика решения такова. Каждое блюдо из числа более дешевых (в порядке увеличения цены) должно найти себе пару из числа более дорогих. Если какое-то не нашло, то дальше нечего и пытаться — будет только дороже. Дорогие блюда просматриваем в порядке уменьшения цены. Если не подошло для данного блюда, то и для более дорогого тоже не подойдёт.
  • Никакого перебора не понадобится. Просто движемся по отсортированному массиву с двух сторон на встречу друг другу. Если текущее дорого блюдо образует с текущим дешевым пару, то увеличиваем счётчик комплексных обедов и переходим к следующему дорогому и следующему дешевому. Если цена этой пары блюд слишком велика, переходим к следующему блюду из числа дорогих.
L. Решение на C++

В завершение вставим таблицу результатов соревнования:

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

С чего начать?

Будем предполагать, что Ваша цель не просто изучить программирование, но и научиться решать задачи. Это означает, что Вы вероятно хотите получить в дальнейшем какую-то пользу от своих новых знаний и навыков, а не просто убиваете время. Сразу должен предупредить, что это потребует во много раз больше усилий, чем простое изучение синтаксиса и лексики С++, урду или клингонского языка.

Нам понадобится не только хороший учебник, но и хороший задачник с системой автоматической проверки. Ещё для занятия потребуют довольно много времени. А значит иногда придется работать не за привычным компьютером с установленной средой разработки, а с планшета или телефона. Предлагаю воспользоваться таким комплектом:

  • В качестве учебника возьмём книгу Липмана или Прата. — СКАЧИВАЕМ
  • В качестве задачника и тестирующей системы используем сайт e-olymp.com. — РЕГИСТРИРУЕМСЯ
  • Вместо установки на компьютер компилятора и среды разработки воспользуемся облачными технологиями через одну из простых онлайн IDE: IdeOne, TutorialsPoint C++, jDoodle. — РЕГИСТРИРУЕМСЯ при желании.
  • В качестве справочника стоит выбрать сайт cplusplus.com. Те немногие английские слова, которые придется запомнить для чтения материалов сайта в дальнейшем будут встречаться постоянно. — ИСПОЛЬЗУЕМ

Более подробные рекомендации и важные дополнения можно найти здесь.

Вы наверняка заметили, что в качестве языка программирования я без долгих пояснений выбрал С++. Вокруг выбора первого языка для начального изучения программирования ведутся бесконечные споры. Я не хочу даже пытаться включиться сейчас в эти святые войны. Хотя признаюсь, я не считаю, что у Вас в этом вопросе реально есть какой-то выбор. Даже если вам придется в дальнейшем перейти, например, на Java или C#, попытка использования С++ вероятно будет вполне рациональным расходованием времени.

Начинать следует с чтения учебника. Все понятные вещи стоит тут же попытаться закодировать и проверить на примерах. Если что-то не поняли, то тем более стоит попытаться закодировать. Прочитав две-три главы стоит взяться за решение задач. Я рекомендую прочесть этот текст и решать задачи по приведенному в нем списку. Здесь Вас будет ожидать неприятный сюрприз — во многих задачах придется много думать не о самом программировании, а о задаче. Не спешите писать 100500 строк лапшеобразного кода — подумайте. Практически все перечисленные задачи решаются в несколько строк.

План решения задач может быть таким
1. Линейные вычисления (147)
2. Программы с ветвлением (188)
3. Циклы (204)
4. Потоковая обработка (72)
5. Массивы (64)
6. Многомерные массивы (78)
7. Строки c-string (40)
8. Строки string (73)
9. Последовательные контейнеры (37)
A. Сортировки и жадность (8)
B. Стеки-деки-очереди (49)
C. Ассоциативные контейнеры (9)
D. Графы (44)
E. Дерево отрезков (16)
F. Динамическое программирование (7)

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

Как не нужно решать задачи

Есть довольно подробные рекомендации, как нужно решать задачи по программированию (в т.ч. для студентов). В конце заметки я дам ссылки на одну из таких статей.
Но я хотел бы сейчас привести наглядный пример того, как не надо решать задачи.
Вот довольно простая задача про разрезание брусочка сыра (точнее прямоугольного параллелепипеда) на кубики со стороной 1. Это одна из задач с которых первокурсники начинают у нас изучать программирование. Решается она одной формулой:

Моделирование и системный подход. Вся супер идея решения состоит в наблюдении, что разрезая что-либо несколькими параллельными разрезами, вы получаете на один кусок больше чем было разрезов. Например, один разрез — два куска. Правда сложно заметить?
Да, придется понаблюдать за тем, что происходит если производить дополнительные разрезы в перпендикулярном направлении. Т.е. после разрезов в одной плоскости получаются пластины, во второй — соломка, в третьей — кубики. Понаблюдайте:

    Именно так человек решает задачи.

  1. Читает условие — иногда несколько раз и обязательно все буквы. Отделяет существенное от неважного.
  2. Представляет себе описанный процесс и его конечный результат отсекая ненужные для решения детали.
  3. Пытается описать формулами процесс или результат. Упрощает формулы.
  4. И наконец — кладет руки на клавиатуру и кодирует.

Возможно Вы заметили, что в первом коротком решении мы не выполнили собственную рекомендацию — не упростили формулу. Действительно, хотя все измерения абсолютно равнозначны, формула не выглядит симметричной. Это сделано чтобы понятнее был процесс вывода формулы. Первое слагаемое [latex]A-1[/latex] в общем числе разрезов показывает как мы резали перпендикулярно оси [latex]Ox[/latex]. Мы сделали [latex]A-1[/latex] разрез и получили [latex]A[/latex] пластин. Второе слагаемое [latex]A\cdot\left(B-1\right)[/latex] показывает как мы резали перпендикулярно оси [latex]Oy[/latex]. Мы сделали [latex]B-1[/latex] разрез в каждой из [latex]A[/latex] пластин полученных при предыдущей серии разрезов. И наконец, на последнем этапе, мы режем каждый из [latex]A\cdot B[/latex] брусочков на кубики при помощи [latex]С-1[/latex] разрезов. Получаем [latex]A\cdot B\cdot\left(C-1\right)[/latex] разрезов. Конечно, результат не должен измениться, если резать в каком-то другом порядке. Если раскрыть скобки и привести подобные мы увидим короткую симметричную относительно измерений формулу.

[latex]\left(A-1\right) + A \cdot \left(B-1\right) + A \cdot B \cdot \left(C-1\right) = ABC-1[/latex]

Аналитический подход. Эта новая формула может быть получена другими очень простыми рассуждениями.

Вначале был один большой кусок. После каждого разреза количество кусочков увеличивается на 1. В самом конце получится [latex]ABC[/latex] кусочков, значит разрезов было на 1 меньше — [latex]ABC-1[/latex].

Это последнее рассуждение демонстрирует подход к которому нужно стремиться — все просто, ясно, лаконично. Не всегда он срабатывает. Часто именно моделирование и системный подход с разбиением на системы и подсистемы позволяет найти решение. Но обычно этот путь более громоздкий. Зато аналитический иногда похож на некий волшебный трюк, когда задача с хлопком исчезает и на её месте появляется ответ. Подробнее об этом, например, здесь

Общим является для всех правильных подходов к решению задачи является необходимость читать и подумать перед тем как решать.

Код программы с новой формулой

Это правильный подход. Но как решает задачу человек, который полностью сконцентрирован на программировании. А он её вообще не решает! Он её программирует. Прочитав про разрезание пространственной фигуры в трех областях он уже кодирует трехмерный массив.

Я позаимствовал это решение с форума, но у нас имеются и свои подобные решения. Они работают правильно. Вот только долго. Но это еще не всё. Представляете количество времени потраченное на его качественную отладку и тестирование? А в реальных проектах этот код возможно потом придется долгие годы поддерживать и переписывать на новые языки программирования!
Чтобы разобраться как работает это второе решение достаточно посмотреть следующее видео

Пожалуйста! Не решайте задачи так!

В продолжение обсуждения этой темы советую прочесть, пока не очень вникая в детали этот текст на английском языке. Здесь довольно простая, но актуальная лексика. Т.е. от чтения двойная польза — и программирование, и английский.
Если чего-то не поняли, то лучше прочесть еще несколько раз. Но некоторые принципиально не читают на английском языке и для них сделали перевод.

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

Ровно 20 простых делителей

Задача. За 2 секунды проверить предположение о том, что у некоторого числа [latex]n \le 10^{18}[/latex] имеется ровно 20 простых делителей.
Попытаться решить задачу и проверить своё решение можно здесь.

Тесты

Вход Выход Примечание
10000000000 Yes [latex]2^{10}\cdot 5^{10}[/latex]
1048576 Yes [latex]2^{20}[/latex]
999999999987679232 Yes [latex]2^19 \cdot 1907348632789[/latex]
2 No [latex]2^{1}[/latex]
1000000000000000003 No Простое число. Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
1000000000012845056 Yes [latex]2^{19}\cdot 1907348632837[/latex] Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
99999989699999923 No [latex]99999989 \cdot 1000000007[/latex]
8388608 No [latex]2^{23}[/latex] — слишком много делителей

Решение

Идея решения состоит в попытках деления исходного числа [latex]n[/latex] на последовательно увеличивающиеся целые числа [latex]d,[/latex] начиная с двойки. Если удается произвести деление без остатка, то очередной делитель найден. Исходное число можно разделить на этот делитель и в дальнейшем искать делители полученного частного, т.е. [latex]n \leftarrow \frac{n}{d}.[/latex] Теперь нам остается найти на один делитель меньше. Такая процедура должна будет успешно завершиться ровно 19 раз. Частное от последнего 19-го деления должно оказаться простым числом — тогда простых делителей окажется ровно 20.
При подготовке тестов выяснилось, что трудности могут вызывать следующие ситуации:

  1. No — отрицательный вердикт: слишком мало делителей. В худшем случае одно большое простое число.
  2. Yes — положительный вердикт: 19 небольших делителей и большой 20-й. В худшем случае рассматривается число [latex]2^{19} \cdot 1907348632789 = 999999999987679232[/latex]

В обоих случаях трудности вызывает поиск делителей довольно большого простого числа. Необходимо аккуратно ограничить диапазон поиска возможных делителей так, чтобы не выполнять излишней работы, но и не пропустить делителей.
Зададимся вопросом, как долго нам придётся перебирать возможные делители (начиная с числа 2) пока не встретим первый (наименьший) делитель?
Рассмотрим первый случай (слишком мало делителей). Пусть нам известно, что число имеет [latex]m[/latex] делителей. Первый, встретившийся нам делитель (т.е. наименьший) должен быть таким, чтобы [latex]d^{m} \le n, [/latex] т.е. [latex]d \le n^{\frac{1}{m}} = \sqrt[m]{n}.[/latex] Это очень хорошее ограничение, т.к. в первом случае нам придется перебирать возможные делители до [latex]\left( 10^{18} \right)^{\frac{1}{20}} = 10^{\frac{18}{20}} \le 7.[/latex] Это совсем немного вариантов. Т.е. достаточно проверить деление на 3, 5 и 7 для самого большого возможного [latex]n[/latex]. При правильном выборе границ поиска «страшный» случай огромного простого числа [latex]n[/latex] оказывается очень лёгким.

Границы поиска делителей в худшем случае
Чуть сложнее оказывается ситуация когда есть один маленький делитель (например, 2). Тогда при поиске следующего делителя нам придутся работать с числами [latex]n \le \frac{10^{18}}{2} = 5 \cdot 10^{17}.[/latex] Поскольку теперь останется найти не 20 а только 19 делителей? то ограничение на возможное значение минимального делителя станет таким: [latex]\left( 5 \cdot 10^{17} \right)^{\frac{1}{19}} = \sqrt[19]{5 \cdot 10^{17}} \le 8.[/latex] Что даёт тот же набор возможных простых делителей. Давайте посмотрим, как у нас будут изменяться границы поиска в худшем случае. Т.е. для максимально большого [latex]n[/latex] и делителях равных 2. Рассуждая аналогичным образом можно рассчитать границы поиска остальных делителей в худшем случае:

[latex]m[/latex] Граница поиска в худшем случае
20 7
19 8
18 9
17 10
16 11
15 12
14 14
13 16
12 19
11 24
10 31
9 42
8 62
7 102
6 198
5 497
4 1976
3 19686
2 1 953 125
1 1 381 067

Как видим значения вполне доступны для полного перебора за 1-2 секунды на обычном персональном компьютере.
Случай с последним делителем будет рассмотрен отдельно далее.

Теперь рассмотрим второй случай. У нас имеется 19 маленьких делителей (в худшем случае это двойки) и одно большое простое число. Насколько большие делители нужно проверить прежде чем заключить, что оставшееся число простое?
Оставшееся после 19 делений на два число не может превышать [latex]\frac{10^{18}}{2^{19}}=0.5 \cdot 5^{18}.[/latex] Если оставшееся число не является простым, то у него должен быть делитель не превышающий квадратного корня из этого числа. Т.е. поиск делителей в этом последнем случае не может продлиться дольше чем до [latex]\sqrt{0.5 \cdot 5^{18}} = 1381067.[/latex]

Код

Составим простую программу по описанному алгоритму.
Код программы можно запустить здесь.
В программе есть два нюанса, на которые следует обратить внимание. Оба они относятся к 8-й строке кода и касаются вычисления верхней границы в цикле подбора делителей.

  • При извлечении корня может быть получено неточное значение. Это связано как с ошибкой округления. Например, при работе с числами типа double [latex]\sqrt[3]{1000000}[/latex] оказывается не 100, как мы ожидаем, а примерно [latex]99.9999999999999716.[/latex] Из-за этого мы можем не найти делитель в точности равный правой границе интервала поиска. Для компенсации возможной ошибки к правой границе была добавлена некоторая небольшая величина. Конкретное значение выбирается на основании пессимистической оценки возможной погрешности.
  • Верхняя граница поиска делителей не превышает [latex]\sqrt[m]{n}[/latex] если число делителей [latex]m \ge 2.[/latex]. Когда мы хотим убедиться, что последнее [latex]\left(m=1\right)[/latex] оставшееся число является простым, мы ищем его делители до [latex]\sqrt[2]{n}.[/latex]. Т.е. предполагаем, что число не простое и ищем его делители.

Задание

Существенным недостатком программы является то, что она перебирает в качестве возможных простых делителей все чётные числа. Естественно, ни одно из них (кроме 2) не может оказаться простым делителем и работа выполняется впустую. Можно надеяться существенно уменьшить время работы программы за счёт правильной организации перебора возможных делителей.
Попытайтесь это сделать.

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

Числа Фибоначчи

Рассмотрим общеизвестный ряд чисел A000045:
[latex]0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots[/latex] Этот ряд представляет собой неотрицательную ветвь последовательности Фибоначчи. Будем считать, что последовательность задаётся следующим рекуррентным соотношением
[latex]f_n=\left\{\begin{matrix}
0, & n=0\\
1, & n=1\\
f_{n-1}+f_{n-2}, & n>1
\end{matrix}\right.[/latex]

Давайте напишем функцию, которая вычисляет [latex]n[/latex]-е по порядку число Фибоначчи, используя приведенное соотношение:

Для теста мы вывели на печать вычисленное этим способом 6-е по порядку число Фибоначчи. Программа напечатала 8. И не ошиблась. Давайте посмотрим как происходили вызовы функций:

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Легко видеть, что для вычисления каждого числа Фибоначчи (кроме двух первых) выполняется строго два вызова функции. Т.е. если нам понадобится вычислить, следующее (седьмое) число Фибоначчи, то количество вызовов практически удвоится. И действительно, каждое следующее число вычисляется вдвое дольше, чем предыдущее. При наличии терпения ещё можно как-то дождаться конца вычисления 50-го числа, но дальше вычисляется уж очень долго.
В чём причина? Почему человек, вычисляя на листе бумаги, легко обгоняет компьютер?
Конечно, неэффективный алгоритм.
На рисунке цветом выделены те блоки, вычисление которых действительно необходимо. Число таких блоков растёт с увеличением номера числа линейно, говорят [latex]O\left( n\right)[/latex]. А вот остальные блоки — сплошные повторы и их число растёт как [latex]O\left( 2^n\right)[/latex].
Попробуйте изменить программу так, чтобы она работала быстро (без повторных вычислений.
В качестве упражнения, я попрошу не использовать циклов.
После того, как у Вас всё получится (или окончательно опустятся руки), загляните под спойлер и постарайтесь разобраться с моим вариантом решения задачи.
Рекурсивное решение без повторов

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

Мотивация

Мотивация это то, что заставляет нас поступать так, как мы поступаем. В этой заметке я хотел бы предложить несколько причин, по которым стоит глубоко изучать (и практиковать!) математику, алгоритмы и программирование именно с точки зрения студентов нашего университета.
Конечно, основной мотивацией является хорошее трудоустройство, интересные проекты, высокая зарплата и хорошее интересное общение. Всем этим не обделены специалисты в области информационных технологий и разработки программного обеспечения. Я уже рассказывал о наших студентах, успешно занимающихся спортивным программированием, которые проходят стажировки в Google, Facebook и конечно в местных филиалах компьютерных фирм. Рассказывал также об основанном нашими студентами успешном стартапе Looksery, который весной этого года был приобретён компанией Snapchat за 150 миллионов долларов.

Письмо из Google

Письмо из Google

Недавно появилось ещё одно свидетельство внимания крупных компаний к нашим выпускникам.
За последнюю неделю выпускники прикладной математики разных лет получили похожие письма от компании Google с приглашением на работу. Приглашение в частности обосновывается высоким уровнем подготовки выпускников ОНУ уже работающих в компании. Здесь приводится копия экрана с текстом письма Андрею Терещенко. Аналогичные письма получили Кирилл Чеканов, Михаил Герасименко, Денис Щелконогов и др. Поиск наших выпускников Google провёл по профессиональной социальной сети linked.in.

Какие не очевидные выводы должен (или может?) сделать студент младших курсов?
Конечно, основный вывод в том, что нужно учиться и наш университет для этого подходит.
Второй вывод — не следует ограничиваться обязательной программой. Подготовки «по конспектам» совершенно недостаточно. Нужно читать книги, использовать интернет для самообразования, посещать дополнительные занятия по субботам и искать другие профессиональные мероприятия. В частности очень полезно участие в спортивных соревнованиях программистов. И дело тут не только в соревновательном аспекте. Контесты хороший повод попытаться решать задачи, а не учебные примеры на определённую тему. На соревновании Вы должны выбрать задачу, которую вероятно сможете решить и выбрать те из своих знаний и навыков, которые приведут Вас к цели. Это позволяет трезво оценить накопленные навыки и знания, а при необходимости внести корректировки в процесс своего обучения.
И третий вывод — сообщайте миру о себе и своих возможностях. Для этого хорошо подходит linked.in. Обязательно фиксируйте там все свои достижения — прохождение учебных курсов, освоение новых технологий, языков (и человеческих и машинных).

Это всё со стороны студента. А какая мотивация у преподавателя? Стыдно признаться, но единственный разумный ответ мне подсказывает неизвестный переводчик одиннадцатого сонета Шекспира

Ничто не вечно под луной. Но жизнь
Бессмертна эстафетой поколений.
Коль этим даром, друг мой, дорожишь,
Оставь свой след, отбросив яд сомнений.

Пусть красота живительной струёй
В преемнике, как Феникс, возродится,
А бездарь обойдёт вас стороной.
И злу чтоб не дано было свершиться.

Иначе человечеству конец
и жить ему лишь шесть десятилетий.
Хвала природе, ты – её венец,
За сохраненье рода ты в ответе.

Да не иссякнет мудрости печать,
Что ты сумел потомкам передать!

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах