e-olymp 513. Проблема Николая

Задача

Николаю нужно доставить подарки для [latex]n[/latex] [latex](n ≤ 10^{18})[/latex] детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю [latex]m[/latex] [latex](m ≤ 2009)[/latex].

Входные данные

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex].

Выходные данные

Вывести искомое количество способов.

Тесты

Входные данные Выходные данные
[latex]500[/latex] [latex]2001[/latex] [latex]0[/latex]
[latex]4[/latex] [latex]5[/latex] [latex]4[/latex]
[latex]4[/latex] [latex]7[/latex] [latex]3[/latex]
[latex]15[/latex] [latex]213[/latex] [latex]147[/latex]
[latex]10[/latex] [latex]3[/latex] [latex]0[/latex]

Код программы

Решение задачи

Если [latex]m[/latex] является членом произведения [latex]n![/latex], то остаток от деления на [latex]m[/latex] равен [latex]0[/latex].В остальных случаях ищем [latex]n![/latex] с вычислением остатка от деления после каждого перемножения.

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.

e-olymp-7410.Маршрутне таксі

Задача

У годину пік на зупинку одночасно під’їхали три маршрутних таксі, які слідують по одному маршруту, в які тут же набилися пасажири. Водії виявили, що кількість людей у ​​різних маршрутках різна, і вирішили пересадити частину пасажирів так, щоб у кожній маршрутці було порівну пасажирів. Потрібно визначити, яку найменшу кількість пасажирів доведеться при цьому пересадити.

Вхідні дані

Три натуральних числа, що не перевищують [latex]100[/latex] — кількості пасажирів у першій, другій і третій маршрутках відповідно.

Вихідні дані

Виведіть одне число — найменшу кількість пасажирів, яку потрібно пересадити. Якщо це неможливо, виведіть слово [latex]IMPOSSIBLE[/latex] (великими літерами).

Тести

Вхідні дані Вихідні дані
[latex]1[/latex] [latex]1[/latex] [latex]4[/latex] [latex]2[/latex]
[latex]1[/latex] [latex]2[/latex] [latex]4[/latex] [latex]IMPOSSIBLE[/latex]
[latex]1[/latex] [latex]3[/latex] [latex]5[/latex] [latex]2[/latex]
[latex]9[/latex] [latex]3[/latex] [latex]9[/latex] [latex]4[/latex]

Код програми

Рішення завдання

Спочатку відріжемо усі варіанти при яких розподілити пасажирів порівну не вийде так, що коли іх загальна кількість не ділиться націло на [latex]3[/latex] виводимо [latex]IMPOSSIBLE[/latex]. Коли розподілити пасажирів можна, розглядаємо [latex]4[/latex] випадки : коли у різних маршрутках кількість людей різна та коли у будь-яких двох маршрутках кількість однакова. Коли кількість різна, від максимальної кількості людей у трьох маршрутках віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей(у кінці ми маємо отримати це число, як кількість пасажирів у всіх маршрутних таксі), коли у двох маршрутках кількість однакова , то від кількості людей(у маршрутці, де іх більше або менше) віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей. Якщо відповідь менше [latex]0[/latex] то помножуюмо на [latex]-1[/latex].

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

e-olymp.472.Вероятность

Задача

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

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

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

Чтобы оценить среднюю частоту выигрышей, Вася решил найти такую величину: количество выигрышных вариантов заполнения полоски разделить на количество всех вариантов заполнения полоски. Количество всех вариантов заполнения полоски Вася нашёл самостоятельно (получилось $n^3$), а вот для нахождения количества выигрышных вариантов он обратился к своему знакомому, лучше разбирающемуся в математике и программировании, т.е. к Вам.

Входные данные

В первой строке входных данных находится число ($1 \leq n \leq 10$)— количество видов фишек.

Выходные данные

Выведите одно число — количество выигрышных способов заполнить полоску из трёх клеток такими фишками.

Тесты

Входные данные Выходные данные
[latex]2[/latex] [latex]6[/latex]
[latex]3[/latex] [latex]15[/latex]
[latex]5[/latex] [latex]45[/latex]
[latex]7[/latex] [latex]91[/latex]
[latex]9[/latex] [latex]153[/latex]

Код программы

Решение задачи

При проигрышных вариантах на выбранной полоске из трех позиций на первое место мы можем поставить [latex]n[/latex] вариантов фишек, а на вторую позицию [latex]n[/latex] — [latex]1[/latex],так как мы можем поставить все варианты кроме того вида, что использовали ранее, аналогично с третьей позицией. Теперь вычтем из кол-ва всех вариантов заполнения [latex]n^3[/latex] кол-во проигрышных [latex]n\cdot(n-1)^2[/latex] и получим кол-во выигрышных способов заполнить полоску. Все варианты могут быть выигрышными только в том случае, если у нас 1 вариант фишек.

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.