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

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

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.825 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.825 подписчиков
0 за неделю
←   Все выпуски   →

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


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

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

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

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

Здравствуйте!
  Что-то не доходят у меня руки до сайта. Форум создал уже, никак не хватает времени настроить. К концу недели торжественно обещаю совершить открытие.

  В этом номере впервые предлагаем задачу 4 уровня, спасибо Алексею Ильичеву;]. Что-то мы совсем про начинающих забыли...

  Ну, и как всегда, кое-что интересное в разделе "Теория".

Письма читателей:
  Письма в данный раздел отбираются по усмотрению автора рассылки, интересные для большого круга подписчиков. Хочу предупредить, что корреспонденция, оскорбляющая чьё-либо достоинство или содержащая нецензурные выражения публикации не подлежит.
From: Старков А.Ю. <starkov@privat-online.net>
To: sapisoft@yandex.ru
Date: Monday, March 11, 2002, 8:23:41 PM
Subject:

Доброе время суток!

Мне нравиться Ваша рассылка, таких рассылок должно быть больше. Особенно полезен Ваш материал для людей которые изучают этот самый язык - таких как я. Но вот пару месяцев назад в нашем институте начали читать паскаль под виндовз. И тут возникли трудности, то что это древность и на нем писать курсовой (вин приложение) я и сам понимаю что это маразм если есть делфи, но требуют исключительно BP 7.0 for Win. А поблуждав по сети я нигде немогу найти исходники для паскаля под
виндовз, если знаете подскажите очень нуждаюсь!!!

Зарание благодарен.

Best regards,
Старков mailto:starkov@privat-online.net
Алексей Шамис: Не знаю, попробуйте: исходники.ру - там много чего есть.
А в этом письме попробуйте разобраться, кто что кому хотел сказать...:)
From: HellMan <alexec@polarcom.ru>
To: sapisoft@yandex.ru
Date: Wednesday, March 13, 2002, 1:50:20 PM
Subject: : Re: Задача из #021 - #022

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

---------------------[ Потопали ночные ежики в тумане...]---------------------

От: HellMan <alexec@polarcom.ru>
Кому: Kirill <vk@zebratelecom.ru>
Дата: 12 марта 2002 г. | 16:21
Тема: Re: Задача из #021 - #022

> Два раза ку, Кирилл!

> Сегодня изучаем под мелкоскопом Ваши каракули от 12 марта 2002 г. | 1:07

>> Уважаемые Алексей и HellMan!
> Так, сейчас будем разбираться, что здесь кому предназначается ;)
> Что - мне, а что - моему тезке (меня тоже Алексей зовут).

>> Во-первых, спасибо за авторскую ссылку в #022 - прямо на подвиги тянет
>> в час ночи, адреналина в крови больше, нежели алкоголя... :)
> Это, видимо, не мне. Хотя я как-то писал про час ночи...

>> Во-вторых, решение задачи HellMan'a меня смутило.
> Какой вы сумнительный ;) Но все правильно. Найдете ошибки - мне, пожалуйста,
> тест, на котором прога заваливается.

>> Я, конечно, ламер несчастный, но, ребята, поясните, please:
>> Дельфи пишет:
>> [Error] sapisoft3.dpr(2): Invalid compiler directive: '$M'
> Значит, Delphi использует другие директивы компилятора. Среди них либо нет
> $M вообще, либо для нее другие ограничения. Просто рекомендую эти директивы
> снести и компилировать со стандартными (или вашими собственными)
> настройками. И только при необходимости менять.
> Привычка вставлять ключи компиляции выработалась из-за использования
> TurboPascal, где другие настройки компилятора могут не дать откомпилировать
> программу. Тут же гарантия, что использованы будут именно эти ключи.

>> [Error] sapisoft3.dpr(28): Element 0 inaccessible - use 'Length' or 'SetLength'
>> [Error] sapisoft3.dpr(37): Element 0 inaccessible - use 'Length' or 'SetLength'
>> [Error] sapisoft3.dpr(42): Element 0 inaccessible - use 'Length' or 'SetLength'
>> [Error] sapisoft3.dpr(43): Element 0 inaccessible - use 'Length' or 'SetLength'
> Опять Delphi не переваривает то, что на ура идет в TP.
> Юзайте length(string), как он и просит.

>> Object Pascal от Borland наглухо виснет, стоит только нажать Ctrl+F9
>> (правда курсор мигает). Что я делаю не так?
> Я тоже не в курсе. Писал под TurboPascal, где все прекрасно работало.
> Borland Pascal (только что проверил) тоже работает.
> Поэтому ответом будет многозначительное молчание.

>> {$M 16384,0,655360} - надо использовать 65536
> За правильность ручаюсь. Turbo Pascal сам вставляет эти две строки при
> нажатии Ctrl+O,O (держите Ctrl, нажимаете O, снова нажимаете O, отпускаете
> Ctrl). При этом даже не пытается возмущаться. Раз уж вы пользуетесь Delphi,
> то, как уже сказано выше, сносите директивы компилятора. Поможет.

>> И, наконец, в-третьих, компилятор+тестер в лице летучего голландца
>> ошибок в программе Алексея ошибок не нашел.
> Ура! Или это не в моей?.. Ах, досадно ;)

> --
> Искренне свой, HellMan [12.03.2002]

> В наушниках мертвая тишина...

> * Если оно зеленое и дергается - то это биология...

--------------------------[ А тут теряется их след ]--------------------------

--
Искренне свой, HellMan [13.03.2002]
Алексей Шамис: Что за мода пошла - тестировать паскалевские коды в win-оболочках? ;)
From: Korotkiy Sergey <ceasary@flexuser.ru>
To: sapisoft@yandex.ru
Date: Tuesday, March 12, 2002, 5:16:05 PM
Subject: проблеммка

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

Многие знают, что в матричном исчислениии есть такая штука: ДЕТЕРМИНАНТ или определитель матрицы никто не подскажет как написать программку для нахождения определителя N-ой Степени?

Заранее огромное спасибо
Ceasar.

ЗАДАЧИ

Дерево (4 уровень)
Условие:
Дерево из N вершин можно представить следующим образом: сначала все вершины нумеруются числами от 1 до N. Затем выкидывается лист с наименьшим номером и выписывается номер его предка. Такая операция повторяется до тех пор, пока не
останется одна вершина. Врезультате получается последовательность из (n-1) числа. Требуется написать программу, которая по последовательности восстанавливает само дерево.

Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 2 секунды на тест.

Входные данные:
Во входном файле на первой строке (N-1) (2<=N<=7500) число.

Выходные данные:
Выходной файл должен содержать N строк. В i-й строке должен быть список вершин, с которыми соеденина i-я вершина в порядке возрастания.

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

Input.txt

Output.txt
1 1 6 2 6 3 4 6
5 6
1
1
2
1 2

Решение: by Алексей Ильичёв <alex_z77@mail.ru>:

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

В нашем случае важно быстро находить лист с наименьшим номером (см. ограничение по времени), поэтому имеет смысл построить приоритетную очередь для листьев. Вывод ответа тоже оптимизирован, чтобы хватило времени.

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

var
  list : array[1..7500] of integer; {Здесь храним исходную последовательность}
  m : array[1..7500] of integer; {Степени вершин, уменьшенные на 1}
  tree : array[1..7500] of integer; {Номера предков для всех вершин}
  heap : array[0..7500] of integer; {Приоритетная очередь для листьев}
  n, i, j : integer;
  v : integer;
  written : boolean;

procedure add(x : integer); {Процедура добавления элемента в очередь}
var
  i, d : integer;
begin
  inc(heap[0]);
  i := heap[0];
  d := i div 2;
  while (d > 0) and (heap[d] > x) do begin
    heap[i] := heap[d];
    i := d;
    d := i div 2;
  end;
  heap[i] := x;
end;

function min(i, j : integer) : integer; {Функция, возвращающая номер минимального элемента из i-го и j-го, j>i!}
begin
  if (j > heap[0]) or (heap[i] < heap[j]) then min := i else min := j;
end;

function getfirst : integer; {Функция, возвращающая первый элемент очереди, и удалающая его из очереди}
var
  i, d : integer;
  x : integer;
begin
  getfirst := heap[1];
  x := heap[heap[0]];
  dec(heap[0]);
  i := 1;
  d := min(2, 3);
  while (d <= heap[0]) and (heap[d] < x) do begin
    heap[i] := heap[d];
    i := d;
    d := min(i*2, i*2+1);
  end;
  heap[i] := x;
end;

begin
  assign(input, 'input.txt');
  reset(input);
  while not seekeof do begin
    inc(n);
    read(list[n]);
    inc(m[list[n]]);
  end;
  inc(n);
  close(input);
  for i := 1 to n do if m[i] = 0 then add(i);
  for i := 1 to (n-1) do begin
    tree[getfirst] := list[i]; {Записать номер предка}
    dec(m[list[i]]); {Уменьшить степень предка}
    if m[list[i]] = 0 then add(list[i]); {Если получили лист, добавить его в очередь}
  end;
  for i := 1 to (n-1) do inc(m[list[i]]); {Опять считаем степени вершин, это нам понадобится для оптимизации вывода ответа}
  assign(output, 'output.txt');
  rewrite(output);
  for i := 1 to n do begin
    v := tree[i];
    if (v > 0) then written := false else written := true;
    j := 0;
    while m[i] > 0 do begin
      inc(j);
      if tree[j] = i then begin
      if (v < j) and (not written) then begin
        write(v, ' ');
        written := true;
      end;
      write(j, ' ');
      dec(m[i]);
    end;
  end;
  if not written then write(v);
  writeln;
  end;
close(output);
end.

Автора задачи вряд-ли удастся установить. Если нужны какие-либо комментарии - пишите.

ТЕОРИЯ

Обмен значений переменных

  Этот пример, наверное, придумали ещё до изобретения компьютеров;). Необходимо поменять  местами значения переменных без использования дополнительной памяти.

Задача. Даны две целые переменные a, b. Составить фрагмент программы, после исполнения которого значения переменных поменялись бы местами (новое значение a равно старому значению b и наоборот), не используя дополнительных переменных (и предполагая, что значениями целых переменных могут быть произвольные целые числа).

Решение. (Начальные значения a и b обозначим a0, b0.)
a := a + b; {a = a0 + b0, b = b0}
b := a - b; {a = a0 + b0, b = a0}
a := a - b; {a = b0, b = a0}

Чистая математика!

Если у вас есть интересная информация для данной рубрики - пишите: sapisoft@yandex.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 		Отписаться
Убрать рекламу
В избранное