Tag Archives: делимость числа

e-olymp 8352. Такси

by

8

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

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

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

Три натуральных числа, не превосходящих 100 — количество пассажиров в первой, второй и третьей маршрутках соответственно.

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

Выведите одно число — наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово IMPOSSIBLE (заглавными буквами).

Тесты

№ Ввод Вывод
1 1 2 3 1
2 6 7 4 IMPOSSIBLE
3 18 10 2 8
4 54 10 96 IMPOSSIBLE
5 27 27 27 0

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

Решение

Мы сможем рассадить пассажиров поровну в три маршрутки только тогда, когда их общее количество кратно трем. Если это условие не выполняется, выводим на экран слово IMPOSSIBLE.

Иначе вычисляем среднее арифметическое исходного количества пассажиров каждой маршрутки по формуле: $\frac{b_{1}+b_{2}+b_{3}}{3}$ и находим минимальное количество пересаживаемых пассажиров, суммируя только положительные отклонения от среднего арифметического.

Ссылки

Related Images:

e-olymp 8594. Между A и B

by

18

Задача

Заданы целые неотрицательные числа $a$ и $b$ [latex](a \le b)[/latex] и натуральное число $x$. Сколько существует чисел между $a$ и $b$ включительно, делящихся на $x$?

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

Три числа $a$, $b$ и $x$ [latex](0 \le a \le b \le 10^{18}, 1 \le x \le 10^{18}[/latex]).

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

Выведите ответ на задачу.

Тесты

Вход Выход
2 6 5 1
1 200 3000 0
83 180 10 10
775 12004 312 36
13 42 7 5

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

Решение

Объявим переменные a,  b,  x и k   типа  long long int, где   a,  b и x — соответствующие числа из условия, а  k — количество чисел на промежутке [latex][a, b][/latex].

Для начала, обоснуем эквивалентность деления и нахождения количества кратных чисел на промежутке [latex][0, n][/latex] . Действительно, деление — это действие, по которому можно узнать сколько раз делитель содержится в делимом. А так как числа, кратные $x$, на промежутке [latex][0, n][/latex] встречаются начиная с $x$ с периодичностью $x$, то количество кратных чисел на промежутке является количеством вместимых $x$ в $n$. Эквивалентность доказана.

Тогда, разность количеств кратных $x$ чисел на промежутках [latex][0, b][/latex] и [latex][0, a][/latex] будет количеством таких чисел на полуинтервале [latex](a, b][/latex], так что придётся отдельно проверять, является ли $a$ кратным $x$, и в таком случае увеличивать k на единицу.

Ссылки

e-olymp

ideone

 

Related Images:

e-olymp 8531. Делимость на числа

by

4

Задача

Задано натуральное число [latex]n.[/latex] Делится ли оно одновременно на [latex] a\ [/latex] и на [latex] b?[/latex]?

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

Три натуральных числа [latex] n, a, b,[/latex] не больших [latex] 10^{9}.[/latex]

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

Выведите «YES» если [latex] n\ [/latex] делится одновременно на [latex] a\ [/latex] и на [latex] b\ [/latex]. Выведите «NO» иначе.

Тесты

№ Ввод Вывод
1 12 4 6 YES
2 10 5 6 NO
3 1056 22 6 YES
4 98 103 5 NO

Решение

Проверим делимость [latex] n\ [/latex] на [latex] a\ [/latex] и [latex] b.[/latex] Число $n$ делится одновременно на $a$ и $b$ тогда, когда и остаток от деления $n$ на $a$ равен $0$ ( n % a == 0), и остаток от деления $n$ на $b$ равен $0$ ( n % b == 0).

Код с ветвлением

Код без использования ветвления

 

Ссылки

Related Images: