Сегодня был необычный день, кроме нашего очередного любимого контеста, нас ждала лекция доктора физико-математических наук Новосибирского университета Медных Александра Дмитриевича. Лектор решил рассказать про геометрию. Говорил про математику и как математики используют компьютер для больших вычислений.
Ну а контест выдался прекрасным. Красивые задачи с применением математики и теории чисел, что может лучше??? Перейдем собственно к задачам )
Задача А. Мне скучно жить. Ограничение по времени: 1 сек
Закончилось время каникул. Благодаря помощи хакера Лехи, Нура все же смогла поступить в университет своей мечты, который находится в Павлополисе. Как известно, на очной форме обучения университеты предоставляют студентам общежития, поэтому Нуре пришлось переехать в Павлополис. Теперь Леха остался совсем один в тихом городке Вичкополисе. От скуки он даже едва не впал в депрессию!
Чтобы хоть немного развеяться Леха придумал для себя задачу. Он выбирает два целых числа A и B, а затем считает наибольший общий делитель чисел «A факториал» и «B факториал». Более формально, хакер хочет посчитать НОД(A!, B!). Как известно, факториал числа x равен произведению всех положительных целых чисел, не превосходящих x. Таким образом, x! = 1·2·3·…·(x - 1)·x. Например, 4! = 1·2·3·4 = 24. Напомним, что НОД(x, y) определяется, как такое наибольшее целое число q, что делит x нацело и делит y нацело.
Леха научился решать такую задачку очень быстро. А сможете ли вы?
Входные данные
В первой и единственной строке входного файла дано два целых числа A и B (1 ≤ A, B ≤ 109, min(A, B) ≤ 12).
Выходные данные
Выведите одно число — наибольший общий делитель чисел A! и B!.
входные данные
4 3
выходные данные
6
Разбор:
Заметим, что НОД двух факториалов – это факториал меньшего из них. Потому что, меньший факториал числа содержится в факториале большего числа. А так как, факториал вычисляется с помощью произведения, то факториал большего из них делится на меньшее. В итоге, надо было посчитать факториал меньшего из чисел.
Тема: математика
Время работы: O(min(A,B))
Задача B. Дипломы и грамоты. Ограничение по времени: 1 сек
В олимпиаде участвовали n школьников, и теперь некоторым из них нужно раздать дипломы, некоторым грамоты, а оставшиеся школьники не получат ничего.
Школьник, получивший диплом или грамоту, является призером. Жюри утвердило, что грамот нужно раздать ровно в k раз больше, чем дипломов. Более того, количество призеров должно быть не больше половины количества школьников (то есть не больше половины n). При этом жюри допускает, что в олимпиаде может не быть призеров вообще.
Требуется определить, какое максимальное количество призеров может быть в олимпиаде с учетом описанных требований, и вывести, соответственно, количество школьников, получивших дипломы, количество школьников, получивших грамоты и количество школьников, которые ничего не получили.
Входные данные
В единственной строке даны два натуральных числа n и k (1 ≤ n, k ≤ 1012), где n — количество школьников, участвовавших в олимпиаде, а k — число, определяющее, во сколько раз количество грамот должно быть больше количества дипломов.
Выходные данные
В единственной строке через пробел выведите три числа: количество школьников, получивших дипломы, количество школьников, получивших грамоты и количество школьников, которые ничего не получили, с учетом того, что количество призеров максимально.
Жюри допускает, что в олимпиаде может не быть призеров вообще.
входные данные
18 2
выходные данные
3 6 9
входные данные
9 10
выходные данные
0 0 9
входные данные
1000000000000 5
выходные данные
83333333333 416666666665 500000000002
входные данные
1000000000000 499999999999
выходные данные
1 499999999999 500000000000
Разбор:
Пусть a — количество участников с дипломами, b — с грамотами. b всегда равно a·k. Тогда суммарное число призеров равно a + a·k = a·(k + 1). Это значение не должно превосходить n/2, поэтому максимальное значение a будет достигаться в точке (n/2) / (k + 1). Найдя сколько дипломников, можно вычислить сколько школьников получили грамоты как найденное а умножить на k. Ну и, чтобы вычислить количество школьников, которые ничего не получили, надо от всего количества школьников отнять количество призеров.
Тема: математика
Время работы: O(1)
Задача C. Золотой Век. Ограничение по времени: 1 сек
В Берляндии год считается несчастливым, если его номер n можно записать как n = xa + yb, где a и b — целые неотрицательные числа.
Например, если x = 2 и y = 3, тогда годы 4 и 17 будут несчастливыми (4 = 20 + 31, 17 = 23 + 32 = 24 + 30), а год 18 не будет, так как не существует представления числа 18 в таком виде.
Отрезок лет называется Золотым Веком, если в нем нет ни одного несчастливого года.
Напишите программу, которая найдет максимальную длину Золотого Века, который начинается не раньше года l и заканчивается не позднее года r. Если все годы в отрезке [l, r] несчастливые, то ответ — 0.
Входные данные
В первой строке записано четыре целых числа x, y, l и r (2 ≤ x, y ≤ 1018, 1 ≤ l ≤ r ≤ 1018).
Выходные данные
Выведите максимальную длину Золотого Века в промежутке [l, r].
Если все годы в отрезке [l, r] несчастливые, то выведите 0.
Примеры
входные данные
2 3 1 10
выходные данные
1
входные данные
3 5 10 22
выходные данные
8
входные данные
2 3 3 5
выходные данные
0
Разбор:
Заметим, что xa для x ≥ 2 имеет не более 60 различных степеней, что дают результат не больше 1018.
Сохраним все возможные суммы всех степеней x и y. Теперь ответ на запрос может быть получен за линейное время проверкой разности между двумя соседними несчастливыми годами в отсортированном порядке.
Тема: математика
Время работы: O(n * log(n))
Задача D. Антон и цифры. Ограничение по времени: 1 сек
Недавно Антон нашёл у себя дома коробку с цифрами. В коробке было k2 цифр 2, k3 цифр 3, k5 цифр 5 и k6 цифр 6.
Любимые числа Антона — 32 и 256. Поэтому он, конечно же, решил составить из цифр, находившихся в коробке, свои любимые числа. При этом он хочет, чтобы сумма составленных чисел была как можно больше. Помогите Антону найти эту сумму!
Каждую цифру можно использовать не более одного раза, то есть в составленных Антоном числах должно быть не больше k2 цифр 2, k3 цифр 3 и так далее. Неиспользованные цифры в сумме не учитываются.
Входные данные
В единственной строке входных данных находятся четыре целых числа k2, k3, k5, k6 — количество цифр 2, 3, 5 и 6 соответственно (0 ≤ k2, k3, k5, k6 ≤ 5·106).
Выходные данные
В единственной строке выходных данных выведите единственное число — максимальную сумму любимых чисел Антона, которые можно составить с помощью цифр из коробки.
входные данные
5 1 3 4
выходные данные
800
входные данные
1 1 1 1
выходные данные
256
Разбор:
Давайте будем действовать жадно. Сначала мы составим максимальное возможное количество чисел 256. Их количество будет равно n = min(k2, k5, k6). Из оставшихся цифр составим максимальное возможное количество чисел 32. Их количество будет равно m = min(k3, k2 — n) (мы используем (k2 - n) вместо k2, поскольку n двоек уже было потрачено на то, чтобы составить числа 256). Теперь нетрудно заметить, что ответ будет равен 32 * m + 256 * n.
Тема: математика
Время работы: O(1)
Задача E. A и B и командная тренировка. Ограничение по времени: 1 сек
A и B готовятся к олимпиадам по программированию.
Важная часть подготовки к соревнованиям по программированию — передача знаний опытных участников тем, кто только начинает заниматься олимпиадами. Поэтому на очередной командной тренировке A решил составить команды так, чтобы новички решали задачи вместе с опытными участниками.
A считает, что оптимальный состав команды из трех человек должен состоять из одного опытного участника и двух новичков. Таким образом, каждый опытный участник сможет поделиться опытом с большим количеством людей.
Однако, B считает, что оптимальным будет состав из двух опытных участников и одного новичка. Таким образом, каждый новичок сможет получить больше знаний и опыта.
В результате, A и B решили, что все команды на тренировке должны быть одного из двух вышеописанных типов. Кроме того, они оба считают, что общее количество команд должно быть как можно больше.
На тренировке присутствуют n опытных участников и m новичков. Сможете ли вы посчитать, какое максимальное количество команд может быть сформировано?
Входные данные
Первая строка содержит два целых числа n и m (0 ≤ n, m ≤ 5 * 105) — количество опытных участников и новичков, присутствующих на тренировке.
Выходные данные
Выведите максимальное количество команд одного из двух описанных в условии типов, которое может быть сформировано.
входные данные
2 6
выходные данные
2
входные данные
4 5
выходные данные
3
Разбор:
Будем выбирать жадно. Если опытных участников больше, чем новичков, то образовываем команду из двух опытных и одного новичка, обязательно проверив есть ли у нас 2 опытных участника. Если новичков больше, чем опытных, то команду образовываем из одного опытного и двух новичков, тоже проверив наличие двух новичков. Это все делаем, пока у нас есть и новички и опытные участники.
Тема: математика
Время работы: O(n)
Задача F. Найти Амира. Ограничение по времени: 1 сек
Несколько лет назад Саджад перешел из одной школы в другую. Теперь он хочет найти Амира — своего одноклассника и хорошего друга, но не знает, в какой школе он.
Всего есть n школ, они пронумерованы от 1 до n. Саджад может путешествовать между любой парой из них, чтобы это сделать, он должен купить билет. Билет между школами i и j стоит (i + j) mod (n + 1) (mod — это остаток от деления), и может быть использован сколько угодно раз. Помогите Саджаду найти минимальную стоимость, которую он должен заплатить, чтобы посетить все школы. Он может начать в любой школе и закончить в любой школе.
Входные данные
Единственная строка содержит одно целое число n (1 ≤ n ≤ 105) — количество школ.
Выходные данные
Выведите одно целое число: минимальную стоимость билетов, необходимую для того, чтобы посетить все школы.
входные данные
2
выходные данные
0
входные данные
10
выходные данные
4
Разбор:
Заметим что, если мы будем брать крайние невыбранные элементы, то это будет стоить сначала 0, потом 1, потом 0, и так далее. Отсюда можем вывести формулу, которая зависит от N – (N — 1) / 2.
Тема: математика
Время работы: O(1)
Задача G. Игра Васи и Пети. Ограничение по времени: 1 сек
Вася и Петя играют в одну простую игру. Вася загадал число x от 1 до n, а Петя пытается угадать это число.
Петя может задавать вопросы вида: «Делится ли загаданное число на число y?».
Игра происходит по следующим правилам: вначале Петя спрашивает все вопросы, которые его интересуют (в том числе, он может не задать ни одного вопроса), затем Вася отвечает на каждый из вопросов «да» или «нет». После получения всех ответов Петя должен назвать число, которое загадал Вася.
К сожалению, Петя не слишком хорошо разбирается в теории чисел. Помогите ему найти минимальное количество вопросов, которые он должен задать, чтобы гарантированно угадать число Васи, а также сами числа yi, про которые он должен задать вопросы.
Входные данные
В единственной строке записано число n (1 ≤ n ≤ 103).
Выходные данные
Выведите длину искомой последовательности вопросов k (0 ≤ k ≤ n), а затем k чисел — саму последовательность вопросов yi(1 ≤ yi ≤ n).
Если существует несколько корректных последовательностей вопросов минимальной длины, то разрешается вывести любую.
входные данные
4
выходные данные
3
2 4 3
входные данные
6
выходные данные
4
2 4 3 5
Разбор:
Пусть Петя не спросил число pk, где p — простое, а k ≥ 1. Тогда, Петя не сможет отличить число pk - 1 от числа pk.
Значит, нужно спросить все числа вида pk, где p — простое, а k ≥ 1. Несложно убедиться, что это позволит угадать и все остальные числа.
Тема: математика, теория чисел
Время работы: O(N*loglogN) в зависимости от теста на простоту.
По традиции фотки с четвертого дня!