Олимпиада проводится при поддержке Московского физико-технического института, Компьютерной компании НИКС, Компании Yandex
Информационная поддержка:
журнал "Мир ПК"
IV Открытая олимпиада школьников по программированию, 2009/10 учебный год
Задача A. Подмножество
| Имя входного файла: | a.in |
| Имя выходного файла: | a.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Из множества всех натуральных чисел от 1 до N требуется выделить такое подмножество, чтобы в нем не было бы никаких двух чисел, отличающихся ровно в два раза (то есть если некоторое число X входит в это подмножество, то число 2X заведомо в него не входит).
Напишите программу, которая по введенному числу N определяет, какое наибольшее количество чисел от 1 до N может быть включено в такое подмножество.
Например, для N=8 ответ 5, подмножество может быть таким: 1, 3, 4, 5, 7.
Формат входных данных
Вводится одно натуральное число N (1 ≤ N ≤ 109).
Формат выходных данных
Выведите искомое максимальное количество чисел от 1 до N, которые могут быть включены в подмножество так, чтобы в этом подмножестве не оказалось бы чисел, отличающихся ровно в два раза.
Примеры
| a.in | a.out |
8 |
5 |
50 |
33 |