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


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


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

Автор
Aslof

Статистика

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

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


Служба Рассылок Subscribe.Ru

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

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

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

Здравствуйте, уважаемые подписчики!
  Вообще-то, я хотел выпустить 26 номер рассылки вчера, но решил сделать это все-таки второго апреля, потому как "могли не поверить" ;).   А вообще сегодня обычный номер - немного писем, задача и, как обычно, теория.

Письма читателей:
  Письма в данный раздел отбираются по усмотрению автора рассылки, интересные для большого круга подписчиков. Корреспонденция, оскорбляющая чьё-либо достоинство или содержащая нецензурные выражения, публикации не подлежит.
From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 28, 2002, 11:43:46 PM
Subject: "Хорошее" решение задачи, предложенной Serhiy Serbin в #25

Ответ на:

From: Serhiy Serbin <serhiys@adarvo.com>
To: sapisoft@yandex.ru
Date: Tuesday, March 19, 2002, 9:40:55 AM
Subject: задача

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

. . . . . . . . . . . . .

Зачем же уравнение прямой? Гораздо проще посмотреть знак векторного произведения. Формула для нахождения векторного произведения через координаты векторов очень простая: x2*y1-x1*y2.

Д.З.: посмотреть на примере, какой знак принимает это произведение при левом повороте ;-)
From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 28, 2002, 11:16:56 PM
Subject: Ответ на ложное обвинение Yuri Y. Roumega, опубликованное в #25

Оригинал был:

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. Это не так.

. . . . . . . . . . . . .

Рекомендуется всем, кто не понял перечитать моё послание ещё разок ;-)

Имеется в виду именно процедура обмена и именно её вызов от одной и той же переменной. Процедура не будет разбираться, куда показывают указатели, переданные ей.

Procedure swap(Var a, b : integer);
begin
a := a xor b;
b := a xor b;
a := a xor b;
end;

Если в параметрах вызова указана одна и та же переменная, то после выполнения оператора a := a xor b обнулится не только A, но и B. Можете проверить на опыте. Я бы не стал писать об этом, если бы сам несколько раз на этом не погорел...
From: Kirill <vk@zebratelecom.ru>
To: sapisoft@yandex.ru, alex_z77@mail.ru
Date: Thursday, March 28, 2002, 11:36:01 PM
Subject: Задача из #025 ("города")

Уважаемые Алексей и Алексей {Что ж Вас всех так заименовали...}!

В лучших традициях жанра пишу тест, на котором программа "Игра в города" успешно не хочет работать:

4
qp
iu
pq
qi

{Надо: qp -> pq -> qi -> iu ; Есть: qp -> iu -> qi ->iu}

Enter после последнего "слова" учтен (в данном тесте это qi).

--
Kirill        mailto:vk@zebratelecom.ru
              Тетя Ася: 153871696
From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Saturday, March 30, 2002, 10:56:34 AM
Subject:

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

Комментарий к решению задачи "Игра в города", опубликованному в #25.

Грешен, каюсь. Мои исходники порой не то, чтобы на другую платформу, но и даже на другой компилятор не переносятся. В том месте, где к пути прибавляется найденный цикл, используется процедура move, которая, как известно, копирует участок памяти. Так вот при её использовании я нагло воспользовался тем, что в Borland Pascal-е размер переменной типа Integer 2 байта, и написал формулу, по которой вычисляется длина копируемого участка в явном виде:

ret[0] shl 1 (что эквивалентно ret[0]*2)

Поэтому у тех, кто пытался компилировать эту программу на Дельфи, где размер переменной типа Integer 4 байта, она выдавала непонятные и неверные ответы.

Конечно же, грамотнее было бы написать:

ret[0] * sizeof(ret[0])

и тогда проблем с переносом на Дельфи не возникло бы.
From: Иван Сидоров <vano@sidorov.net>
To: sapisoft@yandex.ru
Date: Tuesday, April 02, 2002, 2:58:47 PM
Subject: Решение задачи Serhiy Serbin (выпуск от 28 марта)

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

Предлагаю вам свое решение на задачу, опубликованную в выпуске за 28 марта.

Решение:

var
  i,n,count: integer;
  a:array [1..100,1..2] of integer;
  k1,k2,ugol: real;
begin
  write('Введите количество точек:'); readln(n);
  for i:=1 to n do begin
    write('A',i,'(x)='); read(a[i,1]);
    write('A',i,'(y)='); readln(a[i,2]);
  end;
  for i:=1 to n-2 do begin
    if a[i+1,1]<>a[i,1] then k1:=(a[i+1,2]-a[i,2])/(a[i+1,1]-a[i,1]) else k1:=100000000;
    if a[i+2,1]<>a[i+1,1] then k2:=(a[i+2,2]-a[i+1,2])/(a[i+2,1]-a[i+1,1]) else k2:=100000000;
    ugol:=(k1-k2);
    if ugol>0 then begin
      count:=count+1;
      write('Луч из т.(',i+1,') в т.(',i+2,') совершил левый поворот по отношению к лучу из т.(',i,') в т.(',i+1,')');
    end;
  end;
  writeln('Всего левых поворотов:',count);
end.

Алгоритм: У каждой прямой вычисляется коэффициент k (y=kx+b) по формуле k=(y2-y1)/(x2-x1) (если прямая перпендикулярна, то ей присваивается очень большое число k=100000000; посоветуйте, пожалуйста, другой вариант, потому что этот не совсем правилен). Затем беру коэффициент след. прямой, и смотрю на разность k1-k2 - если больше нуля, то луч совершает левый поворот.

--
С уважением,
Сидоров Иван mailto:vano@sidorov.net

ЗАДАЧИ

Равные элементы (3 уровень)

Условие:
Задан целочисленный массив N*M (N - количество строк, M - столбцов, N*M<=30000). Каждая строка массива упорядочена по возрастанию. Требуется написать программу, которая находит число, встречающееся во всех строках.

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

Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке числа N, M, разделенные пробелами. В каждой из следующих N строк записано через пробел по M чисел.

Формат выходных данных:
В выходной файл OUTPUT.TXT записывается найденное число или "NO", если такого числа не существует.

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

Input.txt

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

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

var
  n, m, k, l, o, l1, i, j : integer;
  a : array [1..30000] of integer;
  b : array [1..2001] of integer;
begin
  assign(input,'input.txt'); reset(input);
  readln(n,m); k:=0;
  for i:=1 to n do
  for j:=1 to m do
  begin
    k:=k+1; read(a[k])
  end;
  for i:=1 to m do b[i]:=a[i];
  l:=m; k:=m;
  for i:=2 to n do
  begin
    l1:=0;
    for j:=1 to m do
    begin
      k:=k+1;
      b[l+1]:=a[k];
      o:=1;
      while b[o]<>a[k] do o:=o+1;
      if o<=l then begin l1:=l1+1; b[l1]:=a[k] end
    end;
    l:=l1
  end;
  assign(output,'output.txt'); rewrite(output);
  if l>0 then write(b[1])
  else write('NO');
  close(output)
end.

ТЕОРИЯ

Арифметические функции

  Эти функции полезно использовать для выполнения арифметических операций.

  Примечание: Значения, возвращаемые процедурами операций с плавающей запятой модуля System, при компиляции в режиме числовой обработки (директива {$N+}), имеют не вещественный тип (real), а расширенный (extended).

Функция Описание
Abs Возвращает абсолютное значение аргумента.
Аrctan Возвращает арктангенс аргумента.
Cоs Возвращает косинус аргумента.
Eхp Возвращает экспоненту аргумента.
Frас Возвращает дробную часть аргумента.
Int Возвращает целую часть аргумента.
Ln Возвращает натуральный логарифм аргумента.
Pi Возвращает значение числа Pi
Sin Возвращает синус аргумента.
Sqr Возвращает аргумент в квадрате.
Sqrt Возвращает квадратный корень аргумента.

  Использованы материалы сайта: http://g6prog.narod.ru

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

ТЕМЫ ФОРУМА:

7. Алексей Ильичёв Зачем этот форум? 01-Апр (16:24)
     Алексей Шамис re: Зачем этот форум? 01-Апр (23:51) new!

6. Anton Системы линейных уравнений 25-Мар (18:15)
     Алексей Ильичёв re: Системы линейных уравнений 01-Апр (16:21)

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

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

3. Тоня Помогите пожалуйста решить задачу!!!! 19-Мар (08:38)
     Петрович re: Помогите пожалуйста решить задачу!!!! 30-Мар (00:59)
       Тоня re: Помогите пожалуйста решить задачу!!!! 30-Мар (09:45)
     Mad Wild re: Помогите пожалуйста решить задачу!!!! 01-Апр (00:17)

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 раза в неделю.

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

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