Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи с решениями на Turbo Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.826 RSS
←   Февраль 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
28.02.2002
00:18:54
23:38:21


За последние 60 дней ни разу не выходила


Открыта: 02-12-2001

Автор
Aslof

Статистика

3.826 подписчиков
0 за неделю
←   Все выпуски   →

Олимпиадные задачи с решениями на Turbo Pascal


Служба Рассылок Subscribe.Ru
Олимпиадные задачи c решениями на Turbo Pascal

Олимпиадные задачи с решениями на Turbo Pascal

Рассылка проекта Sapisoft.By.Ru [#013]

Подписчиков на 13.02.2002 - 2565 человек.
Главная Программы Задачи Рассылки Гостевая книга Контакты

Здравствуйте!
  На нашем сайте несколько раз в неделю появляются новые задачи. Многие из них не попадают в рассылку. Поэтому заходите почаще на sapisoft.by.ru и оставляйте сообщения в гостевой книге;). И ещё вопрос к знающим людям. Где можно открыть хороший форум для сайта? Пишите на sapisoft@yandex.ru.

Последовательность (2 уровень)

Условие:
Дана последовательность целых чисел. Известно, что все числа в ней встречаются четное количество раз, кроме одного, которое встречается нечетное число раз. Требуется написать программу, которая определяет это число.

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

Формат входных данных:
Входной файл INPUT.TXT содержит заданную последовательность. Каждое из чисел последовательности больше -2147483649 и меньше 2147483648. В каждой строке файла записано по одному числу. Общее количество чисел в файле не превышает 500001.

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

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

Input.txt

Output.txt
-1
2
-1		 2

Решение:

---------- cut ----------
Рассмотрим следующую операцию сложения по модулю 2: 0+0=0, 1+0=1, 0+1=1 и 1+1=0. Многозначные числа будем складывать поразрядно после двоичного разложения каждого из слагаемых. Так определенная операция сложения обладает следующими свойствами: a+0=a, a+a=0, a+b=b+a, (a+b)+c=a+(b+c). Этих свойств достаточно, чтобы показать, что такая сумма чисел, удовлетворяющих условиям задачи, как раз и будет искомым числом. Действительно, числа, которые встречаются четное количество раз, дают в результате сложения 0 (после перегруппировки слагаемых), а, так как только одно из них встречается нечетное число раз, то оно и останется после всех сложений.

В математике и программировании описанное сложение еще называют исключающим «или», а в Турбо Паскале это сложение реализована как операция «XOR» над целыми числами. Следуя авторам, подсказка была заложена в названии задачи. Приведенные соображения и реализованы в программе:
---------- cut ----------

var
  x, y : longint;
  f, g : text;
begin
  assign(f,'input.txt');
  reset(f);
  assign(g,'output.txt');
  rewrite(g);
  x:=0;
  while not eof(f) do
  begin
    readln(f,y);
    x:=x xor y;
  end;
  writeln(g,x);
  close(g)
end.
Реклама в рассылке:

RLE Banner Network    

  

Рассылки проекта Sapisoft:
Новости проекта Sapisoft [Шамис Алексей]
Информация о выходе новых версий программ и прочих обновлениях на сайте.

 Уроки программирования на Turbo Pascal [Галин Павел]
Хотите стать Великим Программистом? Начните свой путь к вершине славы с изучения языка Turbo Pascal. Он как нельзя лучше подходит для начинающих программистов и в то же время используется для разработки сложных "профессиональных" программ.

 Олимпиадные задачи с решениями на Turbo Pascal [Шамис Алексей]
В рассылке публикуются решения интересных олимпиадных задач различного уровня. Периодичность - 2-3 раза в неделю. Каждый выпуск содержит решение 2-3 задач с подробным анализом описанием алгоритма решения.

 Задача в неделю. Олимпиадные задачи по информатике [Алексеев Александр]
Каждый понедельник в рассылке публикуется задача, которую необходимо решить и в следующий понедельник прислать программу на тестирование. Решения проверяются и в пятницу публикуется разбор и итоги тестирования.

Всегда рады видеть Вас на нашем сайте. Жду ваших предложений и замечаний, Шамис Алексей

Copyright © 2001-2002 by Shamis Alex.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное