e-olymp 8595. Собаки и обезьяны

Задача

У Барыша есть $n$ собак и $m$ обезьян. Он хочет выстроить их в одну линию. Но он не хочет, чтобы в каком-либо месте стояло подряд две собаки или две обезьяны, потому что в таком случае они начинают драться. Сколько существует различных вариантов построения, таких чтобы ни обезьяны, ни собаки не дрались. Ответ выведите по модулю $10^{9}+7$. Имейте в виду, что собаки и обезьяны между собой различаются.

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

Два числа $n$ и $m$ $\left(1 \leq n, m \leq 10^{5}\right)$.

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

Выведите количество различных вариантов построения обезьян и собак по модулю $10^{9}+7$.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 2 8
2 3 2 12
3 1 8 0
4 100000 100000 530123477
5 99999 100000 768947656

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

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

В данной задаче три случая. Если разница между количеством собак и обезьян превышает один, то будет невозможно разместить их так, чтобы собаки с обезьянами чередовались. Размещение собак равно n!. Размещение обезьян равно m!. Если количество одинаково, то сначала может быть как собака, так и обезьяна. Поэтому ответом будет 2*n!*m! и выведем ответ по модулю $10^{9}+7$. В остальных случаях будет ответом n!*m! и выведем ответ по модулю $10^{9}+7$. Последний случай, значит, что разница между количеством собак и обезьян это $1$. Промежуточные вычисления будут иметь тип long long, так как в промежуточных вычислениях, число может быстро увеличиваться. И как только число будет превышать $10^{9}+7$. То сразу же будем искать остаток при делении числа на $10^{9}+7$.

Ссылки

Условие задачи на E-Olymp

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

e-olymp 8532. Печать квадратов и кубов

Задача

Заданы два целых числа $a$ и $b$. Выведите квадраты и кубы всех целых чисел от $a$ до $b$ включительно.

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

Два целых числа $a$ и $b$ [latex](0 \le a \le  b \le 10000)[/latex].

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

В первой строке выведите квадраты всех целых чисел от $a$ до $b$ включительно по возрастанию. Во второй строке выведите кубы всех целых чисел от $a$ до $b$ включительно по убыванию.

Тесты

 

Входные данные Выходные данные
5 10 25 36 49 64 81 100
1000 729 512 343 216 125
120 123 14400 14641 14884 15129
1860867 1815848 1771561 1728000
9995 10000 99900025 99920016 99940009 99960004 99980001 100000000
1000000000000 999700029999 999400119992 999100269973 998800479936 998500749875
0 3 0 1 4 9
27 8 1 0
25 27 625 676 729
19683 17576 15625

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

Решение

Ввожу $a$ и $b$, создаю цикл вывода по возрастанию квадратов чисел из промежутка, и с новой строки — кубы по убыванию.

Ссылки

Ideone

e-olymp

e-olymp 8362. Множители

Задача

Найти число от $1$ до $n$ включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выбрать максимальное из них.

Например, если $n = 7$, то ответом будет число $6$, как наибольшее число, имеющее в своем разложении $2$ простых множителя $2$ и $3$.

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

Одно целое число $n$ $(1 ≤ n ≤ 2$³¹$- 1)$.

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

Вывести одно искомое число.

Тесты

Ввод Вывод
1 1 1
2 10 8
3 100 96
4 363 256
5 2147483647 1610612736

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

Решение

Для решения данной задачи нам необходимо понять, что чем меньше простой множитель, тем больше таких множителей может содержать в себе искомое число, значит наше число состоит только из двоек или из двоек и одной тройки.

Создадим две переменные равные двум и трём и будем увеличивать их вдвое до тех пор, пока полученное число не превосходит заданное.

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

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

Ссылки

Задача множители на e-olymp

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

e-olymp 2061. Юные программисты

Задача 

Известно, что в школе не менее чем $k_{1}$учеников, но не более чем $k_{2}$ учеников. Также известно, что каждый мальчик дружит с $n$ девочками, а каждая девочка с $m$ мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Юные программисты, как Вы видите, до сих пор решают эту задачку. Помогите им.

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

В первой строке входного файла находится $4$ числа, разделённых пробелами: $k_{1}$, $k_{2}$, $n$ и $m$. Все входные данные натуральные числа, не превышающие $10000$, $k_{1}\leq k_{2}$.

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

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

Тесты

Входные данные Выходные данные
20 30 4 5 27 15 12
5 10000 54 44 98 44 54
1 10000 100 100 200 100 100
1 2 1 1 2 1 1
100 120 2 3 100 60 40
50 50 25 25 50 25 25
9900 10000 99 56 9920 3584 6336
9999 10000 9998 2 10000 2 9998
101 110 2 3 105 63 42

Решение

Объяснение 

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

e-olymp

ideone

e-olymp 1452. Кролики

Задача взята с сайта e-olymp.

Задача

Как-то наконец земляне нашли обитаемую планету, назвали ее ТТВ, и отправили вместе с кораблем туда одного кролика. Кролику понравился климат новой планеты и через месяц он произвел на свет еще одного кролика. Известно, что каждый месяц каждый кролик, присутствующий на планете, производил на свет еще одного кролика. На планете откуда-то взялся монстр, который в начале месяца съедал [latex] k [/latex] кроликов, если только их становилось строго больше [latex] k [/latex]. В задаче необходимо определить количество кроликов, которое будет на планете через [latex] n [/latex]месяцев после прибытия туда космического корабля с первым кроликом.

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

Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex]  (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.

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

Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].

Тесты

#

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

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

1

0

10

1

2

1

10

2

3

7

128

128

4

5

10

12

5

30

0

1073741824

Код

Решение

Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex]  k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.

Ссылки

Засчитанное решение на e-olymp.

Код в ideone.

e-olymp 891. Покупка цветов

Задача. Покупка цветов

На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по $a$ рублей за штуку и гладиолусы по $b$ рублей за штуку ($a < b$). У Васи есть $c$ рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже $c$ рублей. Помогите ему вычислить стоимость такого букета.

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

Три целых числа $a$, $b$, $c$ ($1 ≤ a < b ≤ 100, 0 ≤ c ≤ 1000$).

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

Выведите одно число — стоимость самого дорогого букета из максимального количества цветов.

Тесты

Ввод Вывод
1 5 7 0 0
2 3 5 10 9
3 2 3 11 11
4 48 64 306 304
5 17 20 100 100
6 13 15 260 260
7 29 53 999 986
8 17 28 16 0
7 75 100 1000 1000

Решение

Рассмотрим частный случай. Если можно купить по минимальной цене ромашки так, что у нас не будет остатка, то полученное количество цветов будет максимальным и увеличить их стоимость будет невозможно. Значит ответом будет количество денег в кошельке у Васи.

Далее, что бы найти решение для оставшихся вариантов, необходимо найти наибольшую сумму стоимостей максимального количества цветов не превышающую c. Максимальное количество цветов n будет равно количеству цветов с минимальной стоимостью которое можно купить за имеющиеся у Васи деньги. ( c / a).

Что бы оптимизировать код будем проверять условия в цикле с обоих концов (меняя местами количество ромашек и гладиолусов), таким образом мы выполним его за в 2 раза меньшее количество проходов и быстрее найдём максимум. А так же при равенстве искомого значения с его максимально возможным остановим проверку.

Код

Условие задачи

Решение

Код на ideone