Задача. Опять двойка!

[droxeda]

Помогите пожалуйста, вопрос жизни и смерти

Задача 1. Опять двойка!
Ограничение по времени: 1 секунда на тест
Во входном файле задано N целых чисел, каждое из которых находится в диапазоне [1..231-
1]. Подсчитайте количество чисел, встречающихся в этом файле, которые можно представить в
виде 2k, где k — целое число.
Входные данные
В первой строке входного файла записано одно целое число N (0 < N ≤ 106).
Во второй строке — N целых чисел, разделенных пробелами.
Выходные данные
В выходной файл нужно записать одно целое число — количество чисел, удовлетворяющих
условию задачи.
Пример
input.txt

10
2 4 16 100000 5 3 8 2048 16 16
output.txt

7

[Poma][a]

Во входном файле задано N целых чисел, каждое из которых находится в диапазоне [1..231-
1].

Тоесть в диапазоне [1..230] или [1..2311] ?
И в любом случае число в тесте (100000) не удовлетворяет условию задачи

[Mad_Cat]

1..2^31 -1 имхо

if A mod 2 = 0 then inc(count);

[ep1a]

Сообщение от Poma][a

Тоесть в диапазоне [1..230] или [1..2311] ?
И в любом случае число в тесте (100000) не удовлетворяет условию задачи

как я понял - там (2^31)-1

Автору топика: можно завести массив из 31 элемента, где A[n]=2^(n-1). ну а потом сверять очередное число с каждым элементом этого массива. ответ ясен?

[Poma][a]

1..2^31 -1 имхо

Спасибо.

if A mod 2 = 0 then inc(count);

А что говорит пример? Что если 2 числа, то проверяем только одно из них..

где A[n]=2^(n-1)

Тогда уж a[n]=2*(n-1)

Но это ОЧЕНЬ неэффективно, и боюсь не уложит в 1 секунду..

Нужно отбрасывать повторяющиеся элементы..
Мой вариант, не проверял :

begin
    ReadLn (n);

    // специально что-то забыл

    for i := 1 to n do begin
       Read (t);
       j := 1;
       while (j <= count) and (a[j] <> t) do
           Inc (j);
       if j > count then begin
          Inc (count);
          a[count] := t
       end;
 
    // что-то специально забыл

    for i := 1 to count do
         if not Odd (a[i]) then
            Inc (res);

    WriteLn (res)
end.

[Аватар]

Зачем вообще массив - читаем очередное число и проверяем делится ли на 2 нацело. Подозреваю, что Odd медленее mod 2

[Poma][a]

Аватар, гляньте пример ТС, там стоит два числа 16, НО щетчик увеличивается на этих 2-ух числах только 1 раз!

[Mad_Cat]

только еще вопрос там 2*K или 2^k

А что говорит пример? Что если 2 числа, то проверяем только одно из них..

имелось в виду какбе

while not eof(f) do begin
read(a);
if A mod 2 = 0 then inc(count);
end;

там стоит два числа 16

там стоит 3 числа 16
значит все таки 2^k
и как раз 7 чисел)

2 4 16 100000 5 3 8 2048 16 16

[Аватар]

количество чисел, удовлетворяющих условию задачи

Слова разных не вижу

[Poma][a]

Подозреваю, что Odd медленее mod 2

тыц

Слова разных не вижу

Тоже не вижу, тогда как же объяснить ответ в примере?

UPD

там стоит 3 числа 16
значит все таки 2^k
и как раз 7 чисел)

Точняк.. Однако со зрением у меня проблемы
Плюсую (ан нет.. не разрешает )