|
Тройная последовательность
(Время: 1 сек. Память: 32 Мб Сложность: 57%)
На олимпиаде по математике Алексею встретилась интересная задача. Есть три последовательности из целых чисел {a0, a1, …,an}, {b0, b1, …,bn}, {c0, c1, …,cn}, которые определяются следующим образом:
- b0 = 4, c0 = 1;
- если an четно для n ≥ 0, то an+1 = an / 2 , bn+1 = 2×bn и cn+1 = cn;
- если an нечетно для n ≥ 0, то an+1 = an − bn / 2 − cn, bn+1 = bn и cn+1 = bn + cn.
Целое число a0 считается отличным, если an = 0 для некоторого n ≥ 1. Найдите
количество отличных целых чисел, меньших или равных K.
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число Q.
Во второй строке Q натуральных чисел K через пробел. (1 ≤ K ≤ 109; 1 ≤ Q ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите Q чисел – количество отличных целых чисел.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2
5 10 | 1 2 |
Пояснение к примеру
a0 = 3; b0 = 4; c0 = 1; => a1 = 0; b1 = 4; c1 = 5.
a0 = 10; b0 = 4; c0 = 1; => a1 = 5; b1 = 8; c1 = 1; => a2 = 0; b2 = 8; c2 = 9.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
