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

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

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

Подписчиков на 2002-03-28 - 2892 человек(а).
Главная Программы Задачи Рассылки Гостевая книга Контакты

Здравствуйте, уважаемые подписчики!
  Очень рад, что идея форума на сайте оказалась вам по душе. Кстати, теперь некоторые дискуссии из рассылки можно перенести на форум. Например, ответ на свой вопрос в 23# Korotkiy Sergey запросто сможет найти в теме [ПОМОГИТЕ!!!!!]. 

Письма читателей:
  Письма в данный раздел отбираются по усмотрению автора рассылки, интересные для большого круга подписчиков. Хочу предупредить, что корреспонденция, оскорбляющая чьё-либо достоинство или содержащая нецензурные выражения публикации не подлежит.
From: Z.M. <zhilinmike@hotmail.com>
To: sapisoft@yandex.ru
Date: Tuesday, March 19, 2002, 9:56:46 PM
Subject:

Здравствуйте.

Я очень хорошо изучаю вашу рассылку. Она просто класс!!! Но порой данные решения такие тупые. Вот последняя задача - последовательность. Решение перебором на мой взгляд очень сложное и неоправданное. Просто динамика решает её очень хорошо.
Вот что я сотворил за полчаса после прочтения письма. Как говорится проще надо-проще!!!!!

Mike.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
uses crt,dos;

var dat,max,sol:array[1..200]of longint;
  n:integer;

procedure inputdata; {input data}
var i:integer;
begin
  clrscr;
  assign(input,'input.txt');
  reset(input);
  readln(n);
  for i:=1 to n do readln(dat[i]);
  close(input);
end;

procedure find;
var i,j,m:integer;
begin
  max[1]:=1;
  for i:=2 to n do begin
    m:=0;
    for j:=1 to i-1 do if (dat[i]>=dat[j])and(max[j]>m)then m:=max[j];
    max[i]:=m+1;
  end;
end;

procedure outresult;
var i,m,mm:integer;
begin
  m:=0;
  for i:=1 to n do if max[i]>m then m:=max[i];
  assign(output,'output.txt');
  rewrite(output);
  writeln(m);
  mm:=m;
  for i:=n downto 1 do if max[i]=m then begin sol[m]:= dat[i];dec(m) end;
  for i:=1 to mm do writeln(sol[i]);
  close(output);
end;

begin
  inputdata;
  find;
  outresult;
end.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Алексей Шамис: Да, это конечно все хорошо, но почему ваше решение не проходит по тесту, данному в условии?;)
From: Igor L.Zubrytsky <igorz@butes.west.energy.gov.ua>
To: sapisoft@yandex.ru
Date: Monday, March 18, 2002, 8:55:30 AM
Subject: Ошибка в теории (немного математики от 18.3.2002)

Если две прямые перпендикулярны, то K1*K2= -1 , а не 1.

Пример: y=x, y=-x. k1*k2=1*(-1)=-1 .
Алексей Шамис: В предыдущем номере действительно была допущенна ошибка (или, если позволите, опечатка) в разделе "теория". Но странно, что отреагировал на это только один человек...8)
From: Serhiy Serbin <serhiys@adarvo.com>
To: sapisoft@yandex.ru
Date: Tuesday, March 19, 2002, 9:40:55 AM
Subject: задача

Коль пошел разговор об уравнении прямой, то вспомнил очень простую задачу из какойто то там олимпиады. Задача действительно очень простая, правда не совсем понятно почему, но решили ее тогда далеко не все.

Задана последовательность точек на плоскости, парами координат (x,y). Колличество точек N >= 3. Начинаем последовательно просматривать тройки точек от 1 до N-2. Будем считать, что был осушевствлен левый поворот, если луч исходящий из точки (i+1) в точку (i+2) был повернут против часовой стрелки по отношению, к лучу из i в (i+1). И соотвественно правым поворотом, если по часовой стрелке. Задание: сколько левых повортов в последовательности?

К сожалению или к радости, именно подобная формулировка была в задании, что сразу несет кучу вопросов. Ну для начала, можно уверенно всегда выдавать ответ ноль и это всегда будет правильным решением, но что бы привесте задачу к тому
виду, который по видимому подразумевали авторы, я от себя добавлю два уточнения.

Если луч (i+1 -> i+2) продолжает луч (i - > i+1) (поворот на ноль градусов) - будем считать ни левым ни правым. И самое главное, всегда во внимание будем принимать меньшый угол, который образуется между лучами.

Best regards,
Serhiy Serbin
From: Yuri Y. Roumega <ryy@mail.ru>
To: "Aleksey Shamis" <sapisoft@yandex.ru>
Date: Wednesday, March 20, 2002, 1:28:29 AM
Subject: По материалам выпуска #24 рассылки "Олимпиадные задачи с решениями на TP"

Здравствуйте, Aleksey,

Я часто и с интересом читаю Вашу рассылку, но обидно, что наравне с интересной информацией в ней иногда бывают весьма сомнительные, а то и неправильные утверждения.

В выпуске #24 Алексей Ильичёв пишет, что при обмене значений 2 переменных c помощью XOR алгоритм будет работать некорректно, если A=B. Это не так. В самом деле, рассмотрим значения переменных на каждом шаге:

A:=X; B:=X; {Присвоили первичное значение: A=X; B=X, т.е. A=B}
A:=A xor B; {A=X xor X=0; B=X}
B:=A xor B; {A=0; B=0 xor B=0 xor X=X}
A:=A xor B; {A=0 xor B=0 xor X=X; B=X}

Действительно, после 1-го шага A обнулится, но это не означает, что в итоге (после 3-го шага) A будет равно 0 - вопреки словам Алексея.

Второе замечание касается ур-ния прямой в 2D.

Было сказано, что любая прямая на плоскости задается уравнением Y=K*X+B . На самом деле не все прямые можно задать таким ур-нием. Рассмотрите прямую, параллельную оси ординат. Тогда у всех точек X=const, а Y меняется от -oo до +oo. Естественно, нельзя подобрать K и B такие, чтобы ур-ние Y=K*X+B описывало линию.

Для задания произвольной прямой на плоскости следует использовать ур-ние A*X+B*Y+C=0. К примеру, для прямой, проходящей
через точки (x1,y1) и (x2,y2) A, B и С будут вычисляться так:

A:=y1-y2;
B:=x2-x1; {это не ошибка!}
C:=(x1*y2)-(x2*y1);

Тогда, если есть 2 прямые A1*X+B1*Y+C1=0 и A2*X+B2*Y+C2=0, то условие параллельности: A1*B2=A2*B1 условие перпендикулярности: A1*A2=-B1*B2.

C уважением,
Yuri.
From: Hilary <lars@ezmail.ru>
To: sapisoft@yandex.ru
Date: Monday, March 18, 2002, 5:11:49 PM
Subject: Проблемка...

Добрый день!

Возникла небольшая проблема (хотя, может это только для меня?)

Задача: вычислить на Паскале число е с точностью до 8-9 знака.

Но: дело в том что при "чистом" использовании второго замечательного предела(это который (1+1/n)^n)) или формулы разложения в ряд Тейлора точность достигается в 7 знаке, а дальше начинается чертовщина, в виде появления цифры 3 вместо 2. Была бы благодарна, если бы хоть кто-нибудь пояснил мне причину сих происков судьбы, а так же не отказалась бы от идей по поводу достижения цели (8-9 знаков после запятой...)

Hilary.
mailto:lars@ezmail.ru

ЗАДАЧИ

Игра в города (4 уровень)
Условие:
Всем известны правила игры "в города": первый игрок называет произвольный город, следующий - город, название которого начинается на ту же букву, на которую заканчивается название предыдущего города, и т.д. Аналогичным образом можно
играть не в названия городов, а, например, в названия животных.

Задан список допустимых для описанной игры слов, слова в нём могут повторяться. Напишите программу, определяющую, в каком порядке в процессе игры должны быть названы слова из списка, чтобы каждое слово было использовано ровно столько раз,
сколько оно в нём встречается.

Технические требования:
Входные данные:
Во входном файле на первой строке записано число N - количество слов в списке (1<=N<=1000), а в последующих N строках - сами слова. Каждое из них является последовательностью не более, чем 10 строчных английских букв.

Выходные данные:
Выведите в выходной файл слова в исходном порядке, либо сообщение "NO", если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.

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

Input.txt

Output.txt
4
b
ab
bb
bb		 ab
bb
bb
b

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

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

Если построить граф, в котором буквы английского алфавита являются вершинами, а данные нам слова - рёбрами, то задача сведётся к построению Эйлерова пути в ориентированном графе.

Как изменится условие существования Эйлерова пути для ориентированного графа? Нетрудно понять, что для существования в ориентированном графе Эйлерова пути необходимо и достаточно, чтобы для каждой вершины кол-во входящих рёбер равнялось кол-ву выходящих, или для одной вершины кол-во входящих рёбер было больше на 1, а для другой кол-во выходящих было больше на 1.

При этом каждое ребро должно быть достижимым, то есть нет вершины, к которой подходит ребро и к которой нет пути из стартовой вершины.

Собственно алгоритм построения пути тот же самый, что и для неориентированного графа, зы стартовую вершину принимается вершина, для которой кол-во выходящих рёбер на 1 больше.

var
  n, i, j : integer;
  wrd : array[1..1000] of string[10]; {Тут храним слова}
  rin, rout, {Кол-во входящих и выходящих рёбер}
  hash : array[1..26] of integer; {указатель на элемент массива рёбер,
  с которого начинаются рёбра, выходящие из данной вершины}
  s, f : array[0..1000] of integer; {список рёбер - номера начальных и конечных вершин}
  sv, fv, {начальная и конечная вершины}
  v : integer;
  avail : array[1..26] of boolean; {существует ли путь из стартовой вершины в данную}
  way, ret : array[0..1000] of integer; {очередь рёбер}
  deleted : array[1..1000] of boolean; {отмечаем уже использованные слова}
  found : boolean;

procedure swap(i, j : integer);
var
  st : string[10];
  w : integer;
begin
  w := s[i];
  s[i] := s[j];
  s[j] := w;
  w := f[i];
  f[i] := f[j];
  f[j] := w;
  st := wrd[i];
  wrd[i] := wrd[j];
  wrd[j] := st;
end;

procedure sort(l, r : integer);
var
  x, i, j : integer;
begin
  i := l;
  j := r;
  x := s[(l + r) div 2];
  repeat
    while s[i] < x do inc(i);
    while s[j] > x do dec(j);
    if i <= j then begin
      swap(i, j);
      inc(i);
      dec(j);
    end;
  until i > j;
  if i < r then sort(i, r);
  if j > l then sort(l, j);
end;

procedure check(v : integer);
var
  i : integer;
begin
  avail[v] := true;
  i := hash[v];
  while (s[i] = v) do begin
    if not avail[f[i]] then check(f[i]);
    inc(i);
  end;
end;

procedure movefrom(v : integer);
var
  i : integer;
  found : boolean;
begin
  ret[0] := 0;
  repeat
    found := false;
    i := hash[v];
    while (s[i] = v) and (deleted[i]) do inc(i);
    if s[i] = v then begin
      found := true;
      deleted[i] := true;
      inc(ret[0]);
      ret[ret[0]] := i;
      v := f[i];
    end;
  until not found;
end;

begin
  assign(input, 'input.txt');
  reset(input);
  readln(n);
  for i := 1 to n do begin
    readln(wrd[i]);
    s[i] := ord(wrd[i, 1]) - ord('a') + 1;
    f[i] := ord(wrd[i, length(wrd[i])]) - ord('a') + 1;
    inc(rout[s[i]]);
    inc(rin[f[i]]);
  end; {читаем данные, считаем кол-во подходящих рёбер для каждой вершины}
  close(input);
  sort(1, n); {сортируем рёбра по начальной вершине}
  for i := 1 to 26 do
  if (rout[i] - rin[i] = 1) and (sv = 0) then sv := i
  else if (rin[i] - rout[i] = 1) and (fv = 0) then fv := i
  else if (rout[i] <> rin[i]) then begin
    assign(output, 'output.txt');
    rewrite(output);
    writeln('NO');
    close(output);
    halt;
  end; {Проверяем первое условие существования пути, записываем
  стартовую и конечную вершины}
  for i := 1 to n do if hash[s[i]] = 0 then hash[s[i]] := i; {формируем
  массив указателей на элементы списка рёбер для каждой вершины}
  if sv = 0 then for i := 1 to 26 do if rout[i] > 0 then sv := i; {если
  стартовую вершину найти не удалось, берём произвольную}
  check(sv); {обходом в глубину закрашиваем компоненту связности,
  к которой относится первая вершина}
  for i := 1 to 26 do if (not avail[i]) and (rin[i] > 0) then begin
    assign(output, 'output.txt');
    rewrite(output);
    writeln('NO');
    close(output);
    halt;
  end; {если не все рёбра достижимы, значит пути нет}
  v := sv;
  repeat
    found := false;
    i := hash[v];
    while (s[i] = v) and deleted[i] do inc(i);
    if s[i] = v then begin
      found := true;
      inc(way[0]);
      way[way[0]] := i;
      deleted[i] := true;
      v := f[i];
    end;
  until not found; {идём от стартовой вершины, пока не упрёмся в конечную}
  v := sv;
  i := 0;
  while i <= way[0] do begin
    if rout[v] > 0 then begin
      movefrom(v);
      for j := way[0] downto i + 1 do way[j + ret[0]] := way[j];
      inc(way[0], ret[0]);
      move(ret[1], way[i+1], ret[0] shl 1);
    end;
    inc(i);
    v := f[way[i]];
  end; {добавляем к нашему пути все возможные циклы}
  assign(output, 'output.txt');
  rewrite(output);
  for i := 1 to way[0] do writeln(wrd[way[i]]); {выводим ответ}
  close(output);
end.

Если нужна дополнительная информация, такая например как теорема Эйлера с доказательством, или алгоритм построения Эйлерова пути - пишите.

Кстати. Программы гораздо лучше читаются, если они написаны с отступами в нужных местах ;-)

ТЕОРИЯ

Немного математики...[2]

  В продолжение затронутой темы. Думаю всем еще с 8 класса известна формула Герона (для вычисления площади треугольника):

  S = sqrt(p*(p-a)*(p-b)*(p-c)), где p - полупериметр треугольника со сторонами a, b и с.
 
  Но часто требуется найти площадь треугольника по заданным координатам его вершин. В этом случае может пригодиться следующая формула:

  S = abs(((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0))/2).

  Если у вас есть интересная информация для данной рубрики - пишите: sapisoft@yandex.ru.

ТЕМЫ ФОРУМА:

7. Anton [Системы линейных уравнений] 25-Мар (18:15)

6. Михаил [Правило Варнсдорфа] 20-Мар (14:30)

5. Сергей [ПОМОГИТЕ!!!!!] 19-Мар (20:31)
     Berdan [re: ПОМОГИТЕ!!!!! (+)] 24-Мар (17:26)

4. Тоня [Помогите пожалуйста решить задачу!!!!] 19-Мар (08:38)

3. Алексей Ильичёв [...] 17-Мар (00:26)

2. Петров Денис [Помогите решить задачку] 15-Мар (15:56)
     Алексей Ильичёв [re: Помогите решить задачку] 17-Мар (00:30)

1. Webmaster [Дизайн на сайте.] 14-Мар (16:01)
     Максим [re: Дизайн на сайте.] 22-Мар (12:48)

Реклама в рассылке:

RLE    

  

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