Andrew (14 ноября 2012 - 15:42) писал:

Сделано

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.

Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n.

Пример: НОК(16, 20) = 80.

var a,b :longint;
function NOD(x,y:longint):longint; //Функция поиска НОДа двух чисел
  begin
   if x<>0 then NOD:=NOD(y mod x,x)
	else NOD:=y;
  end;
function NOK(x,y:longint):longint; //Функция поиска НОКа двух чисел
  begin
   NOK:=( x div NOD(x,y) ) * y;
  end;
begin
  readln(a, b );
  writeln( 'НОД этих чисел = ', NOD(a,b ) );
  writeln( 'НОК этих чисел = ', NOK(a,b ) );
end.

На вершине лесенки, состоящей из n ступенек, лежит мячик. Он начинает прыгать вниз, к основанию лесенки. Мячик может прыгнуть на след. ступеньку, на ступеньку через одну или через две. Т.е. если мячик лежит на 10 ступеньке, то он может прыгнуть на 9, 8 или 7 ступеньки. Определите число всевозможных маршрутов мячика.

Входные данные

Число n - кол.во ступенек (0<=n<=70)

Выходные данные

Одно число - ответ на задачу

Решение

var f:array [1..70] of int64; i,n:longint;
begin
readln(n); //считываем число ступенек
f[1]:=1; //если у нас 1 ступенька, то кол-во способов 1, т.к. есть один способ сигануть с вершины лесенки до основания, если всего одна ступенька (проверьте сами)
f[2]:=2; //если у нас 2 ступеньки, то кол-во способов 2, т.к. есть два способа сигануть с вершины лесенки до основания, если всего две ступеньки (проверьте сами)
f[3]:=4; //если у нас 3 ступеньки, то кол-во способов 4, т.к. есть четыре способа сигануть с вершины лесенки до основания, если всего три ступеньки (проверьте сами)
for i:=4 to n do
  f[i]:=f[i-2]+f[i-1]+f[i-3]; //А дальше динамика. В массив ответов заносим сумму вариантов "сигания" с i-1, i-2, i-3 ступенек.
writeln(f[n]); //ответ на задачу
end.

Дана числовая последовательность, вывести длину максимальной возрастающей подпоследовательности.

Входные данные

В первой строке вводится n (1<=n<=1000) - длина последовательности. Далее идет сама последовательность длиной n чисел (все числа по модуля не превосходят 10000).

Выходные данные

Одно число - ответ на задачу.

Решение

var a,f:array [1..10000]of longint;
	n,i,max,j:longint;
begin
readln(n); //читаем кол-во чисел
for i:=1 to n do
  read(a[i]); //считываем последовательность
for i:=1 to n do
  f[i]:=1; //забиваем массив ответов 1
for i:=1 to n do
  for j:=1 to i-1 do
   if (a[i]>a[j]) and (f[j]+1>f[i]) then f[i]:=f[j]+1; //ищем длину возрастающей последовательности на каждом шаге последовательности
for i:=1 to n do
  if f[i]>max then max:=f[i]; //находим максимальную подпоследовательность в массиве ответов
writeln(max);
end.

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

Задача

Дан граф (n вершин и m ребер). Далее идут описания ребер, т.е. две вершины, из которой в какую есть путь (ребро). Найти все компоненты сильной связности (их количество).

Словесный алгоритм

• Сортируем вершины топологически.
  
• Инвертируем граф (т.е. меняем направления ребер, например если было ребро из 2 в 3 вершину, то делаем из 3 во 2)
  
• Пробегаемся по отсортированному массиву и если находим не помеченную вершину, то увеличиваем счетчик кол-во к.с.с. и пускаем dfs2 от этой вершины

Реализация


Топологическая сортировка

 
procedure dfs(v:longint);
var i:longint;
begin
  used[v]:=true;//помечаем вершину
  for i:=1 to n do //перебираем все вершины
    if not(used[i]) and (g[v,i]=1) then dfs(i); //если вершина не помеченна и есть путь из нашей вершину в нее, то запускаем глубину от этой вершины
  cnt:=cnt+1;//кол-во вершин тоположке
  dag[cnt]:=v; //кидаем нашу вершину в топологически отсортированный массив
end;

Меняем направление ребер

 
for i:=1 to n do
    for j:=1 to n do
      if (g[i,j]=1) then g1[j,i]:=1; //здесь думаю все понятно

Ищем кол-во к.с.с

 
scc:=0;
  for i:=cnt downto 1 do
    if not(used[dag[i]]) //если вершина не помеченна
      then
        begin
          scc:=scc+1; //на 1 увеличиваем кол-во к.с.с.
          dfs2(dag[i]); //пускаем dfs2 от нашей вершины
        end;
  writeln(scc);

Сам dfs2

 
procedure dfs2(v:longint);
var i:longint;
begin
  used[v]:=true; //помечаем вершину
  for i:=1 to n do//перебираем все вершины
    if not(used[i]) and (g1[v,i]=1) then dfs2(i);//если вершина не помеченна и есть путь из нашей вершину в нее, то запускаем глубину от этой вершины
end;

Не забудьте обнулить массив меток used перед поиском к.с.с.

Результаты наших команд в отборочном туре командного чемпионата г.Минска 23.09.2012:

2 место: Витебск #11_1 ( Петрашко Татьяна, Лапенков Александр, Марчукевич Евгений ) 8 решенных задач, время 237 минут(ы)

7 место: Витебск #1 ( Медяников Илья, Яковлев Илья, Кускова Барбара ) 8 решенных задач, время 433 минут(ы)

10 место: Три области ( Петрушенко Ирина, Шах Егор, Русак Максим) 8 решенных задач, время 526 минут(ы)

11 место: Витебск #2 ( Пискевич Януш, Краснов Александр, Кодосов Никита ) 8 решенных задач, время 749 минут(ы)

19 место: Витебск #3 (Бородавко Евгений, Петуховский Артур, Ульянов Петр) 7 решенных задач, время 854 минут(ы)

27 место: Витебск #4 (Довгаль Алексей, Краснобаев Андрей ) 5 решенных задач, время 592 минут(ы)

28 место: Витебск #5 (Вычев Андрей, Родик Алексей ) 4 решенные задачи, время 273 минут(ы)

Кому интересно самим посмотреть результаты, прикрепляю рейтинг

 LVP (15 января 2012 - 16:55) писал:

Я человек 20 удалил, но они опять зарегались.

 Я. Илья (15 января 2012 - 12:14) писал:

Они были зарегистрированы, потом удалены за спам

Дерево отрезков — это структура данных, которая позволяет эффективно (т.е. скорость алгоритма (O(log n)) реализовать операции следующего вида:

• Нахождение суммы на отрезке [L;R]
  
• Нахождение минимума и максимума на отрезке [L;R]
  
• Изменение элементов (увеличение и уменьшение) на отрезке [L;R]

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



Важной особенностью деревьев отрезков является то, что они потребляют линейный объём памяти: стандартному дереву отрезков требуется порядка 4n элементов памяти для работы над массивом размера n.

Например в задаче n<=100000. Значит нам надо сделать массив [0..400000].

Структура дерева

Подсчитаем и запомним сумму элементов всего массива, т.е. отрезка a[0..n-1] Также посчитаем сумму на двух половинках этого массива: a[0..n/2] и a[n/2..n-1]. Каждую из этих двух половинок в свою очередь разобьем пополам, посчитаем и сохраним сумму на них, потом снова разобьем пополам, и так далее, пока текущий отрезок не достигнет длины 1. Иными словами, мы стартуем с отрезка [0..n-1] и каждый раз делим текущий отрезок надвое (если он ещё не стал отрезком единичной длины), вызывая затем эту же процедуру от обеих половинок; для каждого такого отрезка мы храним сумму чисел на нём.

Можно говорить, что эти отрезки, на которых мы считали сумму, образуют дерево: корень этого дерева — отрезок [0..n-1], а каждая вершина имеет ровно двух сыновей (кроме вершин-листьев, у которых отрезок имеет длину 1).

Задача


Реализуйте структуру данных, хранящую информацию об N (1 ≤ N ≤ 100000) целых числах A₁, ..., A_N. Структура должна поддерживать следующие операции.



1) INIT(N) Инициализация числом N. При этом каждому числу A_i присваивается значение 0.

2) MODIFY(pos,value) Значение A_pos увеличивается на value, если value ≥ 0, и уменьшается на |value|, если value < 0.

3) FINDSUM(l,r) Вывод в выходной файл суммы a[l]..a[r].



Input

Входной файл содержит не более 100000 операций. Каждая операция описывается в отдельной строке. Описание операции начинается с целого числа от 1 до 3 --- ее номера в списке выше. Далее следуют параметры операции в порядке их перечисления в скобках. Числа в каждой строке разделены пробелами.

Все операции корректны. Это значит, что:

• операция INIT является самой первой операцией во входном файле и больше нигде в нем не встречается;
  
• для операции MODIFY выполняются ограничения 1 ≤ pos ≤ N и -10000 ≤ value ≤ 10000;
  
• для операции FINDSUM выполняются ограничения 1 ≤ l ≤ r ≤ N.

Output




Выполните операции в порядке их перечисления в входном файле. Если для выполнения операции нужно вывести некоторую информацию в выходной файл, то выведите эту информацию. Вывод для каждой операции оформите в отдельной строке.

Ввод

1 5
2 4 3
2 2 2
3 2 3
2 5 -2
3 2 4
2 5 6
2 4 2
3 3 3
2 1 -8
2 5 -3
2 4 -7
2 5 -4
3 4 4
3 1 2

Вывод

2
5
0
2
6

Решение

Совершенно очевидно, что надо применять дерево отрезков для решения этой задачи. Каждый из запросов задается первым числом в строке входного файла. Т.е. если нам ввели 1, то надо выполнить запрос INIT, если ввели 2, то надо выполнить запрос MODIFY, если 3, то запрос FINDSUM. Итак рассмотрим каждый из запросов в отдельности.

Запрос INIT(N)

Здесь нам надо обнулить всё дерево, т.е. построить его. Для этого сделаем вот что:

Прочитаем число n. Далее подберем такой показатель степени (банально мы подбираем число), чтобы при возведении 2 в эту степень полученное число было больше нашего n. Это и будет размером нашего массива для хранения дерева сумм. Ну и обнуляем все a[i].

Запрос MODIFY(pos,value)

Этот запрос получает на вход индекс pos и значение value, и перестраивает дерево отрезков таким образом, чтобы оно соответствовало новому значению a[pos]=value .
Тогда понятно, что запрос обновления можно реализовать как рекурсивную функцию: ей передается текущая вершина дерева отрезков, и эта функция выполняет рекурсивный вызов от одного из двух своих сыновей (от того, который содержит позицию pos в своем отрезке), а после этого — пересчитывает значение суммы в текущей вершине точно таким же образом, как мы это делали при построении дерева отрезков (т.е. как сумма значений по обоим сыновьям текущей вершины).

Запрос FINDSUM(l,r)

Реализация

Построение

 
procedure init;
begin
  readln(n);
  pr:=1;
  while pr<n do
    pr:=pr*2;
end;
 

Обновление

 
procedure modify(p,v:longint);
begin
  a[p]:=a[p]+v;
  if p<>1 then modify(p div 2,v);
end;
 

Нахождение суммы

 
procedure findsum(v,l,r:longint);
begin
  if (lv>r) or (rv<l)
    then exit
      else
        if (l>=lv) and (rv>=r)
          then s:=s+a[v]
            else
              begin
                findsum(2*v,l,(l+r)div 2);
                findsum(2*v+1,(l+r)div 2+1,r);
              end;
end;

В основном коде делаем вот что

 
читаем b
      if b=1 then init;
      if b=2
        then
          begin
            readln(p,v);
            p:=pr+p-1;
            modify(p,v);
          end;
      if b=3
        then
          begin
            readln(lv,rv);
            lv:=pr+lv-1;
            rv:=pr+rv-1;
            findsum(1,pr,2*pr-1);
            writeln(s);
            s:=0;
          end;
    end;

"Всплытие" и "затапливание" элементов кучи на паскале.

Допустим у нас n элементов и m запрос на изменение этих элементов. Запросы содержат два числа: pos и value, т.е. надо увеличить a[pos] на value. Но т.к. мы изменяем значение элемента, то вероятнее всего мы можем нарушить основное свойство кучи, т.е у нас может поток должен быть больше предка. Поэтому мы подымаем измененный элемент по кучи вверх, пока его предок не будет больше его или пока мы не доставим измененный элемент в вершину кучи.

Есть два способа сделать всплытие: через цикл while и рекурсией. Рассмотрим оба

 
procedure shift_up(pos:longint);
begin
  while (pos<>1) and (a[pos div 2] < a[pos]) do //пока не дошли до предка и потомок больше предка
    begin
      x:=a[pos div 2]; //меняем их местами
      a[pos div 2]:=a[pos];
      a[pos]:=x;
      pos:=pos div 2; //теперь мы в предке вершины pos
    end;
end;

 
procedure shift_up(pos:longint);
var x:longint;
begin
  if pos=1 then exit; //если мы в самом вверху, то вылетаем
  if a[pos div 2] < a[pos] //если потомок больше предка
    then //то меняем их местами
      begin 
        x:=a[pos div 2];
        a[pos div 2]:=a[pos];
        a[pos]:=x;
        shift_up(pos div 2); //подымаем предка наверх
      end;
end;

Рассмотрим затапливание элемента

У нас есть то же самое, что я описал выше, только теперь надо уменьшить a[pos] на value. Тогда опять нарушится условие кучи, т.к. предок получится меньше одного или двух своих потомков. Поэтому нам надо опускать наш a[pos] до тех пор, пока мы не придем в последний элемент или наш предок не станет больше потомка.

Опять же два способа: рекурсия и цикл while

 
procedure shift_down(pos:longint);
var pos2,x:longint;
begin
  while (2*pos<=n) do //пока мы не пришли в последний элемент
    begin
      pos2:=pos; 
      if (a[2*pos]>a[pos2]) //если левый потомок больше предка
        then pos2:=2*pos; //номеру предка присваем номер потомка
      if (2*pos+1<=n) and (a[2*pos+1]>a[pos2]) //если правый потомок есть и он больше предка
        then pos2:=2*pos+1; //номеру предка присваем номер потомка
      if (pos=pos2) then break; //если предок это потомок тогда вылетаем
      x:=a[pos]; //меняем местами предка и потомка
      a[pos]:=a[pos2];
      a[pos2]:=x;
      pos:=pos2; //номеру потомка присваем номер предка
    end;
end;

 
procedure shift_down(pos:longint);
var pos2:longint;
begin
  pos2:=pos; 
  if pos*2>n  then exit; //если пришли в последний элемент то вылетаем
  if a[pos*2]>a[pos2] //если левый потомок больше предка
    then pos2:=pos*2; //номеру предка присваем номер потомка
  if (pos*2+1<=n) and (a[pos*2+1]>a[pos2]) //если правый потомок есть и он больше предка 
    then pos2:=pos*2+1; //номеру предка присваем номер потомка
  if pos=pos2 then exit; //если предок это потомок тогда вылетаем
  x:=a[pos]; //меняем местами предка и потомка
  a[pos]:=a[pos2];
  a[pos2]:=x;
  shift_down(pos2);//топим потомка
end;

Словесный алгоритм

1)Устанавливаем левую и правую границу l и r(с какого по какой элемент мы хотим отсортировать) .

2)Находим средний элемент между правой и левой границей x (относительно этого элемента мы будем сортировать наш массив) .


3) Пока индикатор i > индикатора j то:

а) Теперь (если сортируем по возрастанию) то ищем слева , от среднего элемента x , элемент который >=x

б) А справа элемент который <=x

в) И если индикаторы i и j не пересеклись то меняем местами элементы a[ i ] и a[ j ] и увеличиваем(или уменьшаем) индикаторы i и j

4) Если индикатор j < правой границы r то запускаем сортировку от этих границ.

5) И если индикатор j > левой границы l то запускаем сортировку от этих границ.


Теперь сам код:

var a:array [1..1000000] of longint;
    i,n:longint;
procedure qSort(l,r:longint);
  var i,j,z,x:longint;
begin
   i:=l;
   j:=r;
   x:=a[(i+j)div 2];{находим  средний элемент}
   repeat
	while a[i]<x do i:=i+1;{ищем слева элемент который >=x }
	while a[j]>x do j:=j-1;{а справа элемент который <=x }
	if i<=j then begin
                        z:=a[i];
                        a[i]:=a[j];
                        a[j]:=z;
                        i:=i+1;
                        j:=j-1;
                      end; {меняем местами элементы a[i] и a[j] и изменяем индикаторы i и j}
   until (i>j);
   if i<r then qSort(i,r);
   if j>l then qSort(l,j);
end;
begin        
readln(n);
for i:=1 to n do
  read(a[i]);
qSort(1,n); {задаём границы сортировки}
for i:=1 to n do
  write(a[i],' ');
end.

Алгоритм Флойда, применяется для

*поиска кратчайших расстояний расстояний между всеми парами вершин графа (одновременно можно построить и сами кратчайшие пути от каждой вершины до каждой)

*построения матрицы достижимости графа

*построения множества истоков и множества стоков (исток - вершина, в которую нет входящих дуг) (сток - вершина, из которой нет исходящих дуг)

Алгоритм Флойда

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке входного файла INPUT.TXT записано единственное число N (1 <= N <= 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы - всегда нули.

Выходные данные

В выходной файл OUTPUT.TXT выведите N строк по N чисел - матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.

Пример

INPUT.TXT

4

0 5 9 100

100 0 2 8

100 100 0 7

4 100 100 0

OUTPUT.TXT

0 5 7 13

12 0 2 8

11 16 0 7

4 9 11 0

var g:array [1..100,1..100] of longint; n,j,i,k:longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x
		else min:=y;
end;        
begin
//Считываем граф
readln(n);
for i:=1 to n do
  for j:=1 to n do read(g[i,j]);
//Вот это - алгоритм Флойда, т.е простейший для реализации способ нахождения кратчайших расстояний от каждой вершины к каждой
for k:=1 to n do
	for i:=1 to n do
        for j:=1 to n do
   		G[i,j]:=min(G[i,j],G[i,k]+G[k,j]);
//Вывод полученного графа
for i:=1 to n do
  begin  
    for j:=1 to n do
      write(g[i,j],' ');
    writeln;
   end;  
end.