Задача
Витя живёт довольно далеко от школы, поэтому, чтобы не опаздывать на уроки, он ездит на автобусе. Витя — очень наблюдательный мальчик, он старается замечать все интересные совпадения, которые происходят в жизни. Однажды он заметил, что как только он садится в автобус, у которого номер в двоичном представлении второй цифрой справа имеет единичку, так его обязательно вызовут к доске отвечать заданный урок. А кто же любит ходить к доске?! Тем более, если накануне просидел за компьютером и не выучил уроки!!! Явно, что в таком случае грозит «двойка» …
Помогите Вите составить список автобусов, которые он считает «несчастливыми» автобусами.
Входные данные
В первой строке записано число [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 13 14 15 16 17 18 19 20 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n, number, count = 0; n = in.nextInt(); for (int i = 0;i < n; i++){ number = in.nextInt(); if ((number / 2) % 2 == 1) count++; } System.out.print(count); in.close(); return; } } |
Решение
В двоичном коде число заканчивается на [latex]1[/latex] тогда и только тогда, когда остаток от деления на [latex]2[/latex] равен [latex]1[/latex] . Для определения предпоследнего символа , в каждом числе отбрасываем последний символ двоичного представления путем деления нацело на [latex]2[/latex] и проверяем нечетность. Подсчитываем все нужные варианты