e-olymp 2817. Двоичные числа

Задача

Для заданного положительного целого числа $n$, распечатать позиции всех $1$ в двоичном его представлении. Позиция младшего бита имеет номер $0$.
Позиции $1$ в двоичном представлении числа $13$ — это $0$, $2$, $3$.
Напишите программу, которая для каждого набора данных:

  • читает натуральное число $n$,
  • вычисляет позиции $1$ в двоичном представлении $n$,
  • выводит результат.

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

В первой строке входного файла содержится одно натуральное число $d$, указывающее количество наборов входных данных, $1 \leq d \leq 10$. Входные данные заданы ниже.

Каждый набор данных состоит ровно из одной строки, содержащей ровно одно целое число $n$, $0 \leq n \leq 10^6$.

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

Вывод должен состоять ровно из $d$ строк — по одной строке для каждого набора входных данных.

Строка $i$, $1 \leq i \leq d$, должна содержать возрастающую последовательность целых чисел, разделенных одним пробелом — позиции $1$ в двоичном представлении $i$-го числа, полученного во входных данных.

Тесты

 

Входные данные
Выходные данные
$3$
$17$
$7$
$5$
$0$ $4$
$0$ $1$ $2$
$0$ $2$
$4$
$1945$
$1337$
$1000000$
$999999$
$0$ $3$ $4$ $7$ $8$ $9$ $10$
$0$ $3$ $4$ $5$ $8$ $10$
$6$ $9$ $14$ $16$ $17$ $18$ $19$
$0$ $1$ $2$ $3$ $4$ $5$ $9$ $14$ $16$ $17$ $18$ $19$
$10$
$0$
$1$
$2$
$3$
$4$
$5$
$6$
$7$
$8$
$9$
$0$
$1$
$0$ $1$
$2$
$0$ $2$
$1$ $2$
$0$ $1$ $2$
$3$
$0$ $3$

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

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

Для решения этой задачи нужно понять, что остаток от деления $n$ на $2$ это последняя цифра в двоичном коде числа $n$, а деление целочисленной переменной $n$ на $2$ это отбрасывание последней цифры в двоичном коде. Цикл с счетчиком $i$ до момента, как $n$ не станет равняться $0$, очевиден, как и внешний цикл от $0$ до $d$, который реализовывает $d$ итераций ввода числа $n$. Стоит отметить, что тесты на e-olymp (все, кроме первого) чувствительны к пробелам в конце строки, из-за чего появляется необходимость каким-то образом его избежать.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

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-olymp 542. Поставка содовой воды

Задача

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

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

Три целых неотрицательных числа [latex]e[/latex], [latex]f[/latex], [latex]c[/latex], где [latex]e[/latex] ([latex]e < 1000[/latex]) — количество пустых бутылок, имеющихся у Тима в начале дня, [latex]f[/latex] ([latex]f < 1000[/latex]) — количество пустых бутылок, найденных в течение дня, и [latex]c[/latex] ([latex]1 < c < 2000[/latex]) — количество пустых бутылок, необходимых для покупки новой бутылки.

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

Сколько бутылок содовой воды смог выпить Тим, когда его замучила жажда?

Тесты

Входные данные Выходные данные
[latex]9[/latex] [latex]0[/latex] [latex]3[/latex] [latex]4[/latex]
[latex]5[/latex] [latex]5[/latex] [latex]2[/latex] [latex]9[/latex]
[latex]0[/latex] [latex]8[/latex] [latex]4[/latex] [latex]2[/latex]
[latex]22[/latex] [latex]0[/latex] [latex]4[/latex] [latex]7[/latex]

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

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

Можно считать, что изначально у Тима имеется [latex]e+f[/latex] пустых бутылок. Допустим, у него есть хотя бы [latex]c[/latex] бутылок, необходимых для покупки новой, Тим идет и меняет их на одну полную бутылку. Затем выпивает её, после чего общее количество пустых у него уменьшается на [latex]c-1[/latex]. То есть за [latex]e+f[/latex] пустых бутылок он сможет выпить [latex]\frac{e+f}{c-1}[/latex] бутылок содовой воды. Нам также следует добавить к [latex]c-1[/latex] маленькую константу [latex]a = 0.0001[/latex] для корректировки значения, чтобы в случае когда количество бутылок кратно [latex]c-1[/latex], Тиму нельзя было взять новую бутылку с недостающим количеством пустых бутылок для этого, следовательно, он должен выпить на одну бутылку меньше. В результате выводим целое число бутылок содовой воды, которые Тим смог выпить, когда его замучила жажда.

Ссылки

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

A288

Задача A288

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

Даны целые числа [latex]a_{1}[/latex], …, [latex]a_{n}[/latex], каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются (+, –, +, –,  или –, +, –, +, … ), то ответом должна служить сама исходная последовательность. Иначе получить все отрицательные члены последовательности, сохранив порядок их следования.

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

Тесты

 

Входные данные Выходные данные
5 5 3 1 2 7 8 100000
-9 -5 -1 -3 -7 -4198 -852 -9 -5 -1 -3 -7 -4198 -852
5 -3 1 81 3 -7 1 -5 6 -3 -7 -5
-1 2 -8 995 -3 777 -42 -1 2 -8 995 -3 777 -42

Решение

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

A297

Условие

Даны целые числа [latex]a_1, \ldots , a_{100}[/latex]. Получить новую последовательность из 100 целых чисел, заменяя [latex]a_i[/latex] нулями, если [latex]|a_i|[/latex] не равно [latex]\text{max} (a_1, \ldots , a_{100})[/latex], и заменяя [latex]a_i[/latex] единицей в противном случае ([latex]i = 1, \ldots , 100[/latex]).

Ниже приведено решение для общего случая, когда количество чисел произвольно.

Тестирование

Входные данные Выходные данные
1 0 1
2 1 0 -1 1 0 1
3 -1 0 -1 0 1 0
4 -1 -1 -1 0 0 0
5 4 4 4 4 1 1 1 1
6 10 5 -1 -10 -20 0 1 2 3 1 0 0 1 0 0 0 0 0

Код

Решение

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

Так как последовательность состоит из целых чисел и ее длина неизвестна, воспользуемся классом vector типа int:

Затем отдельно считаем первый элемент последовательности и возьмем его в качестве максимума, после чего поместим в вектор:

Заполним вектор оставшимися числами, попутно обновляя переменную max , если встретим число, большее хранимого максимума:

Теперь обработаем последовательность согласно условию задачи, то есть заменим каждое число либо нулем, если его абсолютное значение не равно максимуму, либо единицей в противном случае:

Наконец, выведем ответ на задачу — полученную последовательность из нулей и единиц:

Ссылки

Код программы на Ideone.com;

Условие задачи в сборнике задач по программированию (С. А. Абрамов).

A287

Задача A287

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

Даны целые числа [latex] a_{1}\dots a_{n} [/latex]. Все члены последовательности с четными номерами, предшествующие первому по порядку члену со значением [latex] max(a_{1}\dots a_{n}) [/latex], домножить на  [latex] max(a_{1}\dots a_{n}) [/latex].

Тестирование

Входные данные Выходные данные
1. 1 2 3 4 3 2 1 1 8 3 4 3 2 1
2. 1 2 3 4 4 2 5 5 3 3 2 1 1 10 3 20 4 10 5 5 3 3 2 1
3. 11 4 6 7 9 11 4 6 7 9
4. 9 8 10 1 2 4 5 4 6 13 9 104 10 13 2 52 5 52 6 13
5. -10 -4 -6 -7 -3 0 -1 -20 -10 0 -6 0 -3 0 -1 -20

Реализация

Алгоритм решения

Считываем все целые числа до конца входного потока и записываем их в вектор [latex] a [/latex]. Затем:

  1. Сравниваем между собой каждый элемент вектора, и если находится большее значение, то запоминается номер данного элемента.
  2. Далее проходим все члены последовательности, предшествующие первому по порядку члену с максимальным значением.
  3. Умножаем все элементы с четными номерами на  [latex] max(a_{1}\dots a_{n}) [/latex].

Ссылки

Код на ideaone.