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

Подписчиков на 2002-08-01 - 3807 человек(а).
Главная Архив задач Конкурс Рассылки Форум Гостевая книга Контакты

Здравствуйте, уважаемые подписчики!

  Сегодня вышел уже пятый номер рассылки "Уроки программирования на Turbo Pascal"! Само собой, эта рассылка для начинающих, и, читая ее, вы вряд ли узнаете что-нибудь новое (хотя, кто знает). Но, если у вас есть знакомые, желающие научиться программировать на TP, без колебаний рекомендуйте им эту рассылку! Я уверен, они в ней не разочаруются.

  Спасибо всем, кто прислал свои пожелания по темам, освещаемым в разделе "Теория". В этом номере представлена информация по теории графов.
  Задача этого номера была предложена на Всеукраинской Олимпиаде-2002. Правда, уровень только второй ;).

ЗАДАЧИ

Забавный конфуз - 2 уровень

Условие:
Пусть A — массив, состоящий из N элементов A1,...,AN. Обозначим его максимальное и минимальное значение как max(A) и min(A) соответственно. Вычислим сумму элементов S, S=A1+A2+...+AN. Заменим каждый элемент массива на разницу S и этого элемента: Ai:=S-Ai, 1<=i<=N. Такое преобразование массива A назовем операцией Confuse.
Напишите программу CONFUSE, которая по массиву B, полученному в результате K–кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).

Техническое условие:
Первая строка входного файла CONFUSE.DAT содержит целые числа N и K, где N — количество элементов массива B (2<=N<=10000), а K — количество применений операции Confuse к начальному массиву A, 1<=K<=100. Вторая строка файла содержит N элементов массива B. Элементы массива B — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.
Единственная строка выходного файла CONFUSE.SOL должна содержать целое число, которое есть разностью max(A) и min(A).

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

Confuse.dat

Confuse.sol
4 2
45 52 47 46		 7

Авторское решение задачи:

{$N+,G+}
program Confuse;
var
  fr, fw: text;
  bmax, bmin, bi, n, k: longint;
  i: integer;
  answer: comp;

begin
  assign(fr, 'confuse.dat');
  reset(fr);
  assign(fw, 'confuse.sol');
  rewrite(fw);

  readln(fr, n, k);
  read(fr, bmin);
  bmax := bmin;
  for i:=2 to n do
  begin
    read(fr, bi);
    if (bi < bmin) then
      bmin := bi;
    if (bi > bmax) then
      bmax := bi;
  end;
  answer := bmax;
  answer := answer - bmin;
  writeln(fw, answer:0:0);
  close(fw);
  close(fr);
end.

ТЕОРИЯ

Задачи на графах

Что такое граф?
Часто в задачах встречается следующая конструкция - есть дома и дороги, их соединяющие; у каждой дороги есть длина. По другой терминологии такая конструкция называется графом, дома называются "вершинами", дороги - "ребрами" или "дугами", а длина дороги "весом ребра" или "весом дуги". Таким образом, фраза 'Найти минимальный вес пути между вершинами s и k в графе' может быть переведена так: 'Есть дома и дороги их соединяющие. Также заданы длины дорог. Найти кратчайшую длину пути от города s до города k, если двигаться можно только по дорогам'. Пропускная способность дуги (i,j) означает, например, сколько груза может быть перевезено по дороге (по дуге) (i,j) за единицу времени); а поток по дуге (i,j) - это сколько перевозится сейчас на самом деле).

Часто используют следующие обозначения: Г(x(i))- множество вершин, в которые есть дуга из вершины i; Д(x(i))- множество вершин, из которых есть дуга в вершину i.

Пусть в графе N вершин.

Длины дуг обычно заносятся в матрицу (назовем ее C) размера N на N, называемой матрицей смежности:

var С: array [1..N,1..N] of integer;

Элемент C[i,j] этой матрицы равен длине дуги (дороги), соединяющей вершины i и j, и равен (например) 0 или -1, если такой дуги нет. Если дорога двунаправленная (дуга неориентированная), то очевидно, что C[i,j]=C[j,i].

Задача о максимальном потоке.
Алгоритм расстановки пометок для задачи о максимальном (от s к t) потоке:

А.Расстановка пометок. Вершина может находиться в одном из трех состояний:
   - вершине приписана пометка, и вершина просмотрена (т.е. она имеет пометку и все смежные с ней вершины "обработаны"),
   - пометка приписана, но вершина не просмотрена (т.е. она имеет пометку, но не все смежные с ней вершины обработаны),
   - вершина не имеет пометки.
Пометка произвольной вершины x(i) состоит из двух частей и имеет один из двух видов: (+x(j),m) или (-x(j),m). Часть +x(j) пометки первого типа означает, что поток допускает увеличение вдоль дуги (x(j),x(i)). Часть -x(j) пометки другого типа означает, что поток может быть уменьшен вдоль дуги (x(i),x(j)). В обоих случаях m задает максимальную величину дополнительного потока, который может протекать от s к x(i) вдоль построенной увеличивающей цепи потока. Присвоение пометки вершине x(i) соответствует нахождению увеличивающей цепи потока от s к x(i). Сначала все вершины не имеют пометок.

 Шаг 1. Присвоить вершине s пометку (+s,m(s)=бесконечность). Вершине s присвоена пометка, и она просмотрена, все остальные вершины без пометок.

Шаг 2. Взять некоторую не просмотренную вершину с пометкой; пусть ее пометка будет (+-x(k),m(x(i))) (+- обозначает, что перед x(k) может стоять как плюс, так и минус).

(I) Каждой помеченной вершине x(j), принадлежащей Г(x(i)), для которой c(i,j)<q(i,j), присвоить пометку (-x(i),m(x(j))), где m(x(j))=min[m(x(i)),q(i,j)-c(i,j)].

(II) Каждой непомеченной вершине x(j), принадлежащей Д(x), для которой c(i,j)>0, присвоить пометку (-x(i),m(x(j))), где
m(x(j))=min[m(x(i)),c(j,i)].

(Теперь вершина x(i) и помечена, и просмотрена, а вершины x(j), пометки которым присвоены в (I) и (II), являются непросмотренными.) Обозначить каким-либо способом, что вершина x(i) просмотрена.

Шаг 3. Повторять шаг 2 до тех пор, пока либо вершина t будет помечена, и тогда перейти к шагу 4, либо t будет не помечена и никаких других пометок нельзя будет расставить; в этом случае алгоритм заканчивает работу с максимальным вектором потока c. Здесь следует отметить, что если X(0)-множество помеченных вершин, а X'(0) - множество не помеченных, то ( X(0) --> X'(0)) является минимальным разрезом.

Б. Увеличение потока.

Шаг 4. Положить x=t и перейти к шагу 5.

Шаг 5.

(I) Если пометка в вершине x имеет вид (+z,m(x)), то изменить поток вдоль дуги (z,x) c c(z,x) на c(z,x)+m(t).

(II) Если пометка в вершине x имеет вид (-x,z) c c(x,z) на c(x,z)-m(t).

Шаг 6. Если z=s, то стереть все пометки и вернуться к шагу 1, чтобы начать расставлять пометки, но используя уже улучшенный поток, найденный на шаге 5. Если z<>s, то взять x=z и вернуть к шагу 5.

Обозначения: Г(x(i))- множество вершин, в которые есть дуга из вершины i;
             Д(x(i))- множество вершин, из которых есть дуга в вершину i;
             c(i,j) - это пропускная способность дуги;
             q(i,j) - поток по дуге (i,j).

На сегодня все!

В рассылке использованы материалы сайта http://algolist.manual.ru.
Реклама в рассылке:

RLE    

  

Подпишитесь на наши рассылки:

Новости проекта "Олимпиада.com.ru" [Алексей Шамис]
Новости проекта "Olimpiada.com.ru". Новые темы на форуме. Информация о пополнениях в архиве задач. Оперативно и своевременно!

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

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

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

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

Copyright © 2001-2002 by Shamis Alex.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное