Отправляет 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
29
30
31


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


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

Автор
Aslof

Статистика

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

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


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

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

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

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

Здравствуйте!
  Женщин поздравляем с Праздником Весны! Всем желаем Счастья и Большой Любви! Вот такие стихи ;).
  Все хорошо отдохнули? Надеюсь, что да, потому что я опять лезу к вам со своими задачами ;). Обещанный формум на сайте заработает в ближайшее время. А пока предлагаем для разбора следующую задачку.

Следующее слово (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]:

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

const
  input='input.txt';
  output='output.txt';
var
  i,j:integer;
  f:text;
  s,t,p,q:string;
begin
  assign(f,input);
  reset(f);
  read(f,s);
  close(f);
  i:=length(s);
  while (s[i]<=s[i-1]) and (i<>1) do i:=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;
  s:=s+t[pos(q,t)+1];delete(t,pos(q,t)+1,1);s:=s+t;
  if q='no words' then s:=q;
  assign(f,output);
  rewrite(f);
  write(f,s);
  close(f);
end.
Почта:

From: Василевич Денис Анатольевич <denis_vasilevich@mail.kz>
To: sapisoft@yandex.ru
Date: Saturday, March 02, 2002, 7:27:02 AM
Subject: Олимпиадные задачи с решениями на Turbo Pascal [#13]

Турбо паскалем интересовался со школы, но данное решение задачи показалось мне сомнительным. Сам тоже порой старался алгоритмы изобретать не используя массивы. Но тут принцип действия мне не понятен. Последовательно заXORивая набор разных чисел мы по моему получаем какую-то лабуду, а не требуемое решение. Даже не поленился запустил Дельфи, попросил изобразить консольное приложение (чтобы было что-то вроде обычного трубопаскакаля) и затолкал туды блоком текст кода без малейших изменений. Как я ожидал результат был более чем странным. Входной и выходной файл прилепил к письму, да и проект на Дельфях тоже. Если я что-то не так сделал прошу указать на ошибку.

С пламенным приветом, Денис.

INPUT.TXT
5
3
4
1
-2
3

OUTPUT.TXT
-2

program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;

var
x, y : longint;
f, g : text;
begin
// Insert user code here
assign(f,'d:\input.txt');
reset(f);
assign(g,'d:\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.

Шамис Алексей: Мнда... Верстаем 21-ый номер, а комментарии по 13-ому приходят:). Я уж и не помню, чьё это решение было... Автор! Откликнитесь, плз, помогите решить проблему!

From: Fyodor Menshikov <mfv@mail.ru>
To: "Aleksey Shamis" <sapisoft@yandex.ru>
Date: Saturday, March 02, 2002, 5:56:20 PM
Subject: Задачи на TP от 02.03.2002

Здравствуйте, Алексей!

Относительно решения (by Алексей Ильичёв alex_z77@mail.ru).

> Преимущество этого алгоритма в том, что кол-во операций линейно
> зависит от длины номера, в отличии от приведённого переборного
> решения.

В условии задачи ясно сказано, что номер семизначный. Значит, рекурсивный алгоритм будет выполнять не более 3^7=2187 действий, но выполняет гораздо меньше.

Поэтому никаких преимуществ у одного корректного (работающего за требуемое время) алгоритма над другим корректным алгоритмом в смысле сложности быть не может.

Однако у решений олимпиадных задач могут быть два преимущества: лёгкость получения (время, чтобы до него додуматься) и лёгкость набора.

Если из динамического решения убрать комментарии и директивы, оно будет на целых 9 байт меньше рекурсивного.

Относительно доказательства (by HellMan [alexec@newmail.ru]).

> Интересно, сколько ошибок читатели найдут в этой программе? ;)

Целых две.
1. В задаче говорилось не о 1000, а о 500000, так что для полного доказательства корректности решения требуется перебрать до 500000.
2. Для 500000 будет выводиться слишком много информации в файл, просмотреть его весь никому не захочется. Идеальным доказательством была бы программа, просто выдающая ответ "да" или "нет" относительно выполнения требования.

Кстати, факт, что между N+1 и 2N есть простое число был доказан Чебышевым (как я понимаю, 19-й век) для любого натурального N.
Потрясти доказательством или даже ссылкой не могу. Да оно и не нужно - в задаче это нужно всего лишь для N<=500000.

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

From: Natalie Klimova <postklim@mailru.com>
To: sapisoft@yandex.ru
Date: Wednesday, March 06, 2002, 8:07:34 PM
Subject: Задача на Турбопаскале (требуется решение)

Добрый день! Сыну в 8 классе задали нижеизложенную  задачу. Помогите, пожалуйста!
ЗАДАЧА.
Дано некое число, записанное в определённой системе счисления ( двоичная, восьмиричная, десятичная, шестнадцатиричная)
Число и система счисления, в котором оно записано, вводятся с клавиатуры.
Составить программу по переводу записи этого числа в любую заданную( из вышеперечисленных) систему счисления.

Спасибо.

Шамис Алексей: Если в ближайшие дни будет время, то постараюсь выслать вам свой вариант решения задачи. Но на всякий случай ко всем аналогичная просьба (уж очень много работы:(.

From: Jupiter <Z_Q_jupiter@hotmail.com>
To: "Pascal" <sapisoft@yandex.ru>
Date: Thursday, March 07, 2002, 4:17:01 PM
Subject: Коммент к алгоритму перебора HellMan'a

Приветствую всех, а особенно HelMan'а!

Не думаю, что Федор Меньшиков сможет быстро убедиться в прасильности утверждения, поскольку работает программа непомерно долго. На прербор положительных значений типа Longint уйдет немало времени (я не дождался:), даже если исключить из программы вывод.
Алгоритм можно оптимизировать. Зачем проверять делимость числа на 6, если оно не делится на 2 и на 3? Незачем. Можно просто составить массив из первых 5000 простых чисел, а поскольку кавдрат 5000-го простого числа больше, чем влезает в Longint, то любое составное число типа Longint будет делиться на число из массива. Так зачем перебирать до фига чисел, когда быстрее сгенерировать массив и перебирать только из массива?
А еще стоило бы добавить автопроверяльщик, который сам проверяет утверждение для кахдой пары чисел. Не просматривать же, в самом деле, 40 миллионов пар чисел, чтобы убедиться в утверждении.

Jupiter
jupiter@au.ru

From: Jupiter <Z_Q_jupiter@hotmail.com>
To: "Pascal" <sapisoft@yandex.ru>
Date: Thursday, March 07, 2002, 4:18:42 PM
Subject: К чему все споры?

Приветствую!

На всех олимпиадах господствует девиз: "Главное не решить задачу, главное - чтоб она прошла все тесты!".
Факт про наличие простого числа между (N + 1) и (2 * N) является общеизвестным, но никто вас не заставит писать в программе его доказательство.
Поэтому можно считать все такие факты заранее доказанными, по крайней мере на олимпиадах по ПРОГРАММИРОВАНИЮ!!!
Рассылка, кажется, про олимпиадные задачи...

Jupiter
jupiter@au.ru
Реклама в рассылке:

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 		Отписаться
Убрать рекламу
В избранное