e-olymp 622. Единицы

Единицы

На уроках информатики вас, наверное, учили переводить числа из одних систем счисления в другие и выполнять другие подобные операции. Пришло время продемонстрировать эти знания. Найдите количество единиц в двоичной записи заданного числа.

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

Одно целое число [latex]n[/latex] [latex](0 ≤ n ≤ 2\cdot10^9)[/latex].

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

Вывести количество единиц в двоичной записи числа [latex]n[/latex].

Тесты

Входные данные Выходные данные
20 2
0 0
1 1
5 2
2000000000 13

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

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

Алгоритм заключается в последовательном делении заданного числа [latex]n[/latex] на [latex]2[/latex] и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц [latex]k[/latex] равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас [latex]k[/latex]. Если остаток равен единице то мы получим [latex]k+1[/latex] что нам и требуется.

Условие задачи на e-olimp
Код решения ideon

e-olimp 1610. Зайцы в клетках

Зайцы в клетках

Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:

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

В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется [latex]n[/latex] клеток и [latex]m[/latex] зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 10^9)[/latex].

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

Входные данные Выходные данные
3 50 17
5 5 1
1070 589 1
34 49 2

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

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

Пусть [latex]n[/latex] — количество клеток, и [latex]m[/latex] — количество зайцев.
Найдем отношение [latex]\frac{m}{n}[/latex]. Если это отношение больше либо равно единице то [latex]{m}\geq{n}[/latex] и мы имеем ответ. [latex]\frac{(m+n-1)}{n}[/latex] — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе [latex]{m}\leq{n}[/latex] и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.

Условие задачи на e-olimp
Код решения ideon

e-olimp 57. Бабочка-санитар

Задача

e-olimp 57. Бабочка-санитар

e-olimp 57. Бабочка-санитар

Школьники, идя из дому в школу или наоборот — со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.
Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], бабочка перелетала в точку с координатами [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex], расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.
Какую оптическую силу [latex]D[/latex] имели крылышки-линзы бабочки в этот момент? Continue reading