Задача
Витя живёт довольно далеко от школы, поэтому, чтобы не опаздывать на уроки, он ездит на автобусе. Витя — очень наблюдательный мальчик, он старается замечать все интересные совпадения, которые происходят в жизни. Однажды он заметил, что как только он садится в автобус, у которого номер в двоичном представлении второй цифрой справа имеет единичку, так его обязательно вызовут к доске отвечать заданный урок. А кто же любит ходить к доске?! Тем более, если накануне просидел за компьютером и не выучил уроки!!! Явно, что в таком случае грозит «двойка» …
Помогите Вите составить список автобусов, которые он считает «несчастливыми» автобусами.
Входные данные
В первой строке записано число [latex]N (0 ≤ N ≤ 100000)[/latex] — количество автобусов, далее указаны номера автобусов [latex]m_i (0 ≤ m_i ≤ 2^{31}-1)[/latex] по одному в строке.
Выходные данные
Выведите количество «несчастливых» автобусов.
Тесты
| Входные данные | Выходные данные |
|---|---|
| 2 0 3 |
1 |
| 3 1 2 4 |
1 |
| 4 2 1 3 5 |
2 |
| 5 1 2 3 7 4 |
3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <iostream> using namespace std; int main() { int n, number, count = 0; cin >> n; for (int i = 0;i < n; i++){ cin>>number; if ((number / 2) % 2 == 1) count++; } cout << count; return 0; } |
Решение
В двоичном коде число заканчивается на [latex]1[/latex] тогда и только тогда, когда остаток от деления на [latex]2[/latex] равен [latex]1[/latex] . Для определения предпоследнего символа , в каждом числе отбрасываем последний символ двоичного представления путем деления нацело на [latex]2[/latex] и проверяем нечетность. Подсчитываем все нужные варианты
2 thoughts on “e-olymp 247. Несчастливый автобус”