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

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

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.827 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
29
30
31


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


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

Автор
Aslof

Статистика

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

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


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

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

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

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

Здравствуйте!
  Рассылка продолжает развиваться, и я, в меру своих сил и возможностей, стараюсь сделать её как можно более удобной и интересной для вас, уважаемые подписчики!

  Итак, позвольте представить вам новый раздел рассылки - "Теория". В нём будет публиковаться интересная / полезная информация, касающаяся решения олимпиадных задач и вообще программирования в Turbo Pascal. Кто-то может быть не найдёт в нём для себя ничего нового, но большинству подписчиков, я думаю, будет чему поучиться.

  Теперь по поводу задачи "Следующее слово" из предыдущего номера рассылки. Спасибо Kirill'у <vk@zebratelecom.ru> за указание на ошибку в решении. Ниже можете прочитать правильное решение задачи. Ну, и как обычно;), HellMan со своим вариантом решения данной задачи.

Письма читателей:
  Письма в данный раздел отбираются по усмотрению автора рассылки, интересные для большого круга подписчиков. Хочу предупредить, что корреспонденция, оскорбляющая чьё-либо достоинство или содержащая нецензурные выражения публикации не подлежит.
From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Sunday, March 10, 2002, 4:09:51 PM
Subject: По поводу вопроса по задаче из #13

>Турбо паскалем интересовался со школы, но данное решение задачи показалось мне сомнительным.

Думаю, что автора задачи найти будет трудно, т.к. эта задача предлагалась на всероссийских сборах, причём достаточно давно. Напомню условие:

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

Ответом на задачу будет являться XOR-сумма всех чисел. Это нетрудно вывести исходя из следующих свойств операции XOR:

(A xor B = B xor A), (A xor A = 0) и (A xor 0 = A)

Свойства эти по моему мнению вполне очевидны. Если есть последовательность чисел X1, X2, X3, ..., Xn, то (X1 xor X2 xor X3 xor ... xor Xn = 0), если все числа встречаются чётное число раз, если же одно число встречается нечётное число раз, то получаем (0 xor A = A). Что же касается до присланных input.txt и output.txt, то просто напросто входные данные в этом примере не корректны.
From: HellMan <alexec@newmail.ru>
To: sapisoft@yandex.ru
Date: Sunday, March 10, 2002, 12:59:10 AM
Subject: Олимпиадные задачи с решениями на Turbo Pascal || #21

Два раза ку, Алексей!

Во-первых, по поводу задачи "Следующее слово". Я долго въезжал в условие. Особенно долго пытался понять, что же такое

> непосредственно следующее за ним по алфавиту слово в соответствии с
> описанным правилом

Тем более что описания правила не заметил. Оно подразумевается? Гораздо понятнее было бы сказать, что требуется следующее за данным в лексико-графическом порядке слово. Это, кажется, общепринятый термин.

Еще мне не совсем ясно, зачем возиться со строками посредством insert, delete, copy, pos? Гораздо удобнее, IMHO, работать с ними как с массивом символов.

Не буду утверждать, что мое решение лучше, но мне оно роднее и понятнее ;)

Напоследок хочу сказать тем, кто придирался к моей программе, посвященной проверке общеизвестного факта относительно простых чисел: люди, если вам надо, напишите так, как вы хотите! Не маленькие, наверное, чтобы просить заменить одно число на другое и вставить в конце if!

{ это я, видимо, не выспался }

Например, у Фёдора Меньшикова есть прекрасная программа, которая удовлетворяет всем вашим требованиям. Если хорошо попросите, он обязательно поделится ;)

Ну, вот, все сказал. Спасибо за внимание. Освобождаю трибуну.

Искренне свой, HellMan [10.03.2002]
Алексей Шамис: Решение читайте ниже, а на счёт условия хочу сказать, что формулировал его не я. Оно было взято с областной олимпиады в том виде, в котором было там представлено.
From: Fyodor Menshikov <mfv@mail.ru>
To: "Aleksey Shamis" <sapisoft@yandex.ru>
Date: Monday, March 11, 2002, 9:35:39 AM
Subject: [#13]

> Последовательно заXORивая набор разных чисел мы по моему
> получаем какую-то лабуду, а не требуемое решение.
> Если я что-то не так сделал прошу указать на ошибку.
> С пламенным приветом, Денис.

Пожалуйста:

Лучше нужно условие задачи читать. Там сказано, что ищется число,
встречающееся НЕЧЁТНОЕ число раз. Так что ввод

5
3
4
1
-2
3

где, по-видимому, ищется чётное число раз встречающееся число 3, некорректен.

Обоснование задачи элементарное:

X xor X=0,
X xor Y=Y xor X,
(X xor Y) xor Z=X xor (Y xor Z)
Так что все пары чисел взаимно уничтожатся, а число, встречающееся нечётное число раз, останется.

С уважением,
Фёдор Меньшиков.

ЗАДАЧИ

Следующее слово (3 уровень)
Условие:
Задаётся некоторое слово, длина которого не превышает 80 символов, например GOTO. Из всех его букв составляются все возможные другие слова, может быть бессмысленные, например, GOOT, GOTO, GTOO, ..., TOOG. Каждая буква входит в образованное слово ровно столько же раз, сколько раз она встречается в исходном слове.
Требуется написать программу, которая по заданному слову строит непосредственно следующее за ним по алфавиту слово в соответствии с описанным правилом.

Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени: 5 секунд на один тест.
Входной файл INPUT.TXT содержит одно слово, состоящее не более чем из 80 заглавных английских букв. Выходной файл OUTPUT.TXТ содержит одно слово, непосредственно следующее в алфавитном порядке за заданным, или фразу "no words", написанную малыми английскими буквами, если нужного слова найти не удаётся.

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

Input.txt

Output.txt
APAQ APQA
Z no words

Решение: by Aleksey Shamis [sapisoft@yandex.ru]:

Конечно, не стоит искать все варианты перестановок заданного слова, а потом искать среди них нужный. Вместо этого предлагаю следующий алгоритм. Просматривая заданное слово с конца, ищем первую пару символов, стоящую не в порядке убявания. Затем сортируем полученный ряд символов (от найденной пары до конца слова) по возростанию, и, поставив на первое место символ, идущий следующим по порядку за тем что был в отрезке первым, получаем слово которое было необходимо найти.
Выше изложенные мысли реализованы в программе:

var
  i,j:integer;
  s,t,p,q:string;
begin
  assign(input,'input.txt');reset(input);
  assign(output,'output.txt');rewrite(output);
  readln(s);
  i:=length(s);
  while (s[i]<=s[i-1]) and (i<>1) do inc(i,-1);
  t:=copy(s,i-1,length(s)-i+2);delete(s,i-1,length(s)-i+2);
  q:=copy(t,1,1);if i=1 then q:='no words';
  for i:=1 to length(t)-1 do
  begin
    for j:=1 to length(t)-1 do
    begin
      if t[j]>t[j+1] then
      begin
        p:=copy(t,j,1);
        delete(t,j,1);
        insert(p,t,j+1);
      end;
    end;
  end;
  i:=pos(q,t);
  while t[i]=t[i+1] do inc(i);
  s:=s+t[i+1];delete(t,i+1,1);s:=s+t;
  if q='no words' then s:=q;
  write(s);
end.

Решение: by HellMan <alexec@newmail.ru>

{$A-,B-,D+,E-,F-,G-,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X-,Y+}
{$M 16384,0,655360}

program nextword;

var
  w: string;
  i, j, k: byte;

label
  FINISH;

procedure swap(var a, b: char);
begin
  if a = b then
  exit;
  byte(a) := byte(a) xor byte(b);
  byte(b) := byte(a) xor byte(b);
  byte(a) := byte(a) xor byte(b);
end;

begin
  assign(input, 'input.txt');
  reset(input);
  readln(w);
  close(input);

  i := byte(w[0]) - 1;
  while (w[i] >= w[i + 1]) and (i > 0) do { ищем букву, меньшую стоящей справа }
  dec(i);

  if i = 0 then begin
    w := 'no words';
    goto FINISH;
  end;

  j := byte(w[0]); { ищем букву, большую найденной }
  while w[i] >= w[j] do
  dec(j);

  swap(w[i], w[j]);
  for k := i + 1 to (i + 1 + byte(w[0])) div 2 do { сортируем хвост }
  swap(w[k], w[byte(w[0]) + i + 1 - k]); { на самом деле просто инвертируем порядок }

  FINISH:
  assign(output, 'output.txt');
  rewrite(output);
  writeln(w);
  close(output);
end.

ТЕОРИЯ

Работа с файлами

  Сегодня мы расскажем вам, как можно при работе с файлами сэкономить несколько строк кода и сделать отладку программы намного легче. Спасибо Boris Bukh <brbukh@yahoo.com> за предоставленную информацию.

Есть более простой способ работы с файлами на олимпиадах, чем прямолинейное открытие/закрытие файла. Вот код

program Solution;
begin

Assign(input,'input.txt');Reset(input);
Assign(output,'output.txt');Rewrite(output);

ReadLn(Data); { нам не надо указывать из какого файла читать т.к. input читается по умолчанию}

...

Answer:=решение(Data);

...

WriteLn(Answer); { ответ идет в output }

{ Нам не нужно закрывать файлы, поскольку они объявлены в System и закроются сами }

end;

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

Примечание: переменные input и output описывать в разделе var не нужно! В данном случае компилятор автоматически асоциирует их с файлами ввода-вывода.
Реклама в рассылке:

RLE Banner Network    

  

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

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

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

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

Всегда рады видеть вас на нашем сайте!
Aleksey Shamis - sapisoft@yandex.ru
Sapisoft Project - http://sapisoft.by.ru
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное