e-olymp-203. Кубики-2

Задача

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

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

В первой строке – количество разложенных перед Витэком кубиков [latex]N[/latex] [latex](1 ≤ N ≤ 100)[/latex], в следующей строке последовательность из [latex]N[/latex] цифр на кубиках через пробел.

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

Наименьшее количество кубиков, которое нужно правее доставить Витэку.

Тесты

# Входные данные Выходные данные
1 3
1 2 3
2
2 5
1 2 3 4 4
3
3 2
1 2
1
4 2
1 1
0

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

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

Читаем поток данных переводя каждое прочитанное число в элемент массива. Для каждого элемента массива проверяем его равенство с последний и если да, то через два цикла(начиная с начала и с конца) проверяем равенство остальных элементов массива по двое и если да, то увеличиваем переменную, от которой будет зависеть ответ, если она в конце будет равна [latex]0[/latex], то выведем число равное номеру элемента массива равного последнему.

Ссылки

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

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

e-olymp-1317. Дни рождения

Задача

Известно, что в группе из [latex]23[/latex] или более человек вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает [latex]50 \% [/latex]. Этот факт может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в конкретный день – ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, факт не является парадоксом в строгом научном смысле – логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

Для заданного количества людей вычислить вероятность того, что двое из них родились в один день года. Год считать равным [latex]365[/latex] дням.

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

Каждая строка является отдельным тестом и содержит количество людей [latex]n[/latex] [latex](1 < n < 400)[/latex].

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

Для каждого значения [latex]n[/latex] в отдельной строке вывести вероятность того, что хотя бы у двух из [latex]n[/latex] людей дни рождения (число и месяц) совпадают. Искомую вероятность выводить в процентах и округлять до [latex]8[/latex] знаков после запятой как указано в примере.

Тесты

Входные данные Выходные данные
[latex]12[/latex] [latex]16.70247888\%[/latex]
[latex]28[/latex] [latex]65.44614723\%[/latex]
[latex]399[/latex] [latex]100.00000000\%[/latex]

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

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

Посчитаем вероятность того, что дни рождения не совпадут. Вероятность того, что у двух людей дни рождения не совпадут равна [latex](1 — \frac{1}{365})[/latex]. Взяв третьего человека, вероятность того, что его день рождения не совпадет с предыдущими равна [latex](1 — \frac{2}{365})[/latex] и так далее до последнего человека, у которого вероятность не совпадения дня рождения с остальными равна [latex](1 — \frac{n-1}{365})[/latex]. Перемножив все эти значения через цикл получим вероятность того, что у всех [latex]n[/latex] человек из группы дни рождения не совпадут[latex]( \frac{365!}{(365-n)! \cdot 365^n})[/latex]. Так как вероятность не может быть больше [latex]1[/latex], то от [latex]1[/latex] отнимем кол-во неблагоприятных исходов и получим нужное. Но по условию ответ необходимо вывести в процентах, поэтому умножим на [latex]100[/latex] полученное. И так как [latex]n[/latex] будет вводиться пока пользователю угодно , запишем вышесказанное в цикл [latex]while[/latex].

Ссылки

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

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

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. Вероятность

Задача

Однорукий бандит

Однорукий бандит

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

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

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

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