Меню сайта

Категории раздела
Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) [36]
Решение олимпиадных задач по программированию
Готовимся к олимпиаде по математике [3]
Решение олимпиадных задач по математике

Мини-чат

Наш опрос
Уважаемый посетитель сайта, к какой категории вы себя относите?
Всего ответов: 5525

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Главная

Регистрация

Вход
Вы вошли как Гость | Группа "Гости" | RSS


Личный сайт учителя математики и информатики

Фоновой Натальи Леонидовны



Пятница, 29.03.2024, 03:06
Главная » Файлы » Внеурочная деятельность » Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru)

Последовательность
14.02.2012, 08:49

Условие:
Последовательность 1001011001101001... строится так: сначала пишется 1, затем повторяется такое действие: уже написанную часть приписывают справа с заменой элемента 0 на 1 и наоборот, т.е. 1->10->1001->10010110->...
Требуется написать программу, вычисляющую n-ый член этой последовательности по заданному n<=2147483647.

Технические условия:
Ограничение по времени тестирования: по 1 секунде на один тест.

Формат входных данных:
Входной файл INPUT.TXT содержит n.

Формат выходных данных:
В выходной файл OUTPUT.TXT вывести найденную цифру.

Примеры входных и выходных файлов:
Input.txt
6

Output.txt
1

Решение:
---------- cut ----------
Эта задача предлагалась на олимпиадах школьников различных регионов России еще в конце 80 годов уже прошлого века. Ее решение осуществляется методом возврата. Пусть на искомом месте стоит 0. Определим, откуда и из чего получилось это значение при указанных в условии задачи построениях. Это продолжаем до тех пор, пока не возвратимся к началу построения (вначале пишется 1). Если найденное нами значение совпадает с 1, значит на искомом месте действительно стоит 0, а иначе там 1.
---------- cut ----------

var
n, p : longint;
t : byte;
f, g : text;
begin
assign(f,'input.txt'); reset(f);
read(f,n);
if n>1073741824 then p:=1073741824 else
if n>536870912 then p:= 536870912
else
begin p:=1; while p<n do p:=p*2; p:=p div 2 end;
t:=0;
while n>1 do
begin
t:=1-t;
n:=n-p;
while p>=n do p:=p div 2
end;
assign(g,'output.txt'); rewrite(g);
write(g,1-t);
close(g)
end.
Категория: Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) | Добавил: admin
Просмотров: 1601 | Загрузок: 0 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск

Кнопка сайта

Одна кнопка

время жизни сайта

Сайт участвует
конкурс сайтов 

Новости образовани

Фраза дня

Web-мастеру

OperaFirefoxGoogle ChromeDownload Master
QIPSkypeµTorrentTeamViewer
Dr.Web CureITAvira AntiVirTotal CommanderCDBurnerXP
PicasaIrfanViewCheMaxDAEMON Tools
AIMPKMPlayerBSplayerK-Lite Codec Pack

Установить себе такой Блок
Скрипты и HTML для uCOz

Раскрутка сайта
Graffiti Decorations(R) Studio (TM) Site Promoter

Copyright MyCorp © 2024
/td>