Алгоритмы

2 280 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: успешные, неуспешные.
Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: НОД(a,b)=НОД(a % b,b). Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b).

Ввод
12 16
Вывод
4
Дан связный ориентированный невзвешенный граф. Требуется вывести номера вершин из которых исходят все его перекрестные ребра (нумерация с 1).
 
Входные данные:
Целое число n и m - число вершин и ребер в графе.
Следующие m строк содержат 2 числа a и b, показывающие, что из вершины a есть ребро в вершину b.
 
Выходные данные:
В первой строке должно находиться число n - количество перекрестных ребер, в следующей строке должны быть перечисленны вершины в порядке возрастания без повторений. Если таковых нет, тогда следует вывести -1.
 
Вам задан неориентированный связный граф с N вершинами и М ребрами (1 ? N ? 20000, 1 ? М ? 200 000). В графе отсутствуют петли и кратные ребра.
 
Найдите все точки сочленения в заданном графе.
 
Формат входного файла:
Граф задан во входном файле следующим образом: первая строка содержит числа N и М. Каждая из следующих М строк содержит описание ребра - два целых числа из диапазона от 1 до N - номера концов ребра.
 
Формат выходного файла:
На первой строке выведите число С - количество точек сочленения в заданном графе. На следующей строке выведите С целых чисел - номера вершин, которые являются точками сочленения, в возрастающем порядке. 

Громозека любит печеньки, на которых записаны числа. Громозека будет есть печеньку, если на ней написано комфортное для него число. Громозека считает число комфортным, если оно является точной степенью двойки.  В руках у Громозеки сейчас печенька, на которой написано число N. Выведите слово YES, если Громозека съест эту печеньку и слово NO в противном случае.

Операцией возведения в степень пользоваться нельзя!
 

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

Вводится натуральное число N (N < 109).
 

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

Выведите ответ на задачу.

 
Примеры
Входные данные Выходные данные
1 1 YES
2 4 YES
3 5 NO
 
В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.
 
Формат входных данных
В первой строке входных данных записано число N - количество вершин в графе (1 <= N <= 100). Далее с новой строки записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.
 
Формат выходных данных 
Выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.
Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая 
содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.
 
Входные данные
Вводится одно целое число N (\(0<=N<=30\)).
 
Выходные данные 
Выведите N строк треугольника Паскаля. Разделяйте числа в строке одним пробелом.
 

Примечание
Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint.
 
 
Примеры
Входные данные Выходные данные
1
8
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
 
ГАИ#18782
ГАИ
 
Вдоль шоссе в точках X1,X2,...,XN расположены посты ГАИ. 
В точке X произошло мелкое ДТП (дорожно-транспортное происшествие).
Требуется определить, какой из постов ГАИ расположен ближе всего
к этой точке, чтобы с него послать к месту происшествия наряд милиции.
 
Входные данные
Во входном файле записано сначала число N - количество пунктов ГАИ. (1<=N<=100)
Далее следуют координаты расположения постов ГАИ на прямом шоссе
(целые числа от -10000 до 10000). Далее идет координата точки,
в которой произошло ДТМ (целое число от -10000 до 10000).
 
Выходные данные
В выходной файл требуется вывести одно число - номер поста ГАИ,
с которого нужно послать наряд к месту ДТП. Если несколько постов
ГАИ находятся на одинаковом расстоянии от точки ДТП, выведите любой из них.
 
Пример входного файла
5
10 2 8 -7 3
7
 
Пример выходного файла
3
Количество операций
 
Дана программа сортировки (p141.pas). Требуется узнать, сколько раз
при сортировке конкретного массива с помощью этой программы
выполняется операция сравнения двух элементов массива (строка 25 программы).
 
Входные данные
Задано сначала число N (1≤N≤100), а затем N целых чисел, по модулю не превышающих 1000.
 
Выходные данные
Ваша программа должна печатать одно число - сколько
раз в процессе сортировки этого массива программой p141.pas выполнится
команда сравнения двух элементов массива.
 
Пример входного файла
5
3 1 2 4 2
 
Пример выходного файла
10

Текст программы p141.pas
const nmax=100;

var a:array[1..nmax] of integer;
    n:integer;
    i,j,g:integer;

    f1,f2:text;

begin
assign(f1,'input.txt');
reset(f1);
assign(f2,'output.txt');
rewrite(f2);
                                  {Чтение входных данных}
read(f1,n);
for i:=1 to n do read(f1,a[i]);
                                  {Сортировка массива}

for i:=1 to n do begin            {Подбираем число на i-ое место}

  g:=i;                           {Считаем, что самое маленькое число,
                                   которое нам встретилось, стоит на месте i}

  for j:=i+1 to n do              {Перебираем все числа с i+1 до конца массива}
    if a[j]<a[g] then g:=j;       {Если нашли число, которое меньше,
                                   чем то, что уже найдено, запоминаем его}

                                  {Меняем местами числа, стоящие на i-ом и
                                   на g-ом местах }
                                  {Если a[i]=x, a[g]=y, то после выполнения
                                   команды: }
  if i<>g then begin
    a[i]:=a[i]+a[g];                {a[i]=x+y, a[g]=y}
    a[g]:=a[i]-a[g];                {a[i]=x+y, a[g]=(x+y)-y=x}
    a[i]:=a[i]-a[g];                {a[i]=(x+y)-x=y}
                                  {То есть после этого a[i]=y, a[g]=x
                                   обмен значений произошел}
    end;

  end;

                                  {Выводим результат}
for i:=1 to n do
  write(f2,a[i],' ');
close(f1);
close(f2);
end.

18760#18760
Пользователь находился в каталоге Расписание. Сначала он поднялся на один уровень вверх, затем спустился на один уровень вниз, потом ещё раз спустился на один уровень вниз. В результате он оказался в каталоге C:\учёба\химия\ГИА Укажите полный путь каталога, с которым пользователь начинал работу.

1) C:\Расписание
2) C:\учёба\2013\Расписание
3) C:\учёба\химия\Расписание
4) C:\учёба\Расписание
18756#18756
Пользователь работал с каталогом Химия. Сначала он поднялся на один уровень вверх, затем спустился на один уровень вниз, потом ещё раз спустился на один уровень вниз. В результате он оказался в каталоге C:\Школа\Уроки\Информатика Запишите полный путь каталога, с которым пользователь начинал работу.

1) C:\Школа\Уроки\Химия
2) C:\Химия
3) C:\Школа\Уроки\Класс\Химия
4) C:\Школа\Химия
18749#18749

Пользователь находился в каталоге Расписание. Сначала он поднялся на один уровень вверх, затем спустился на один уровень вниз, потом ещё раз спустился на один уровень вниз и ещё раз спустился на один уровень вниз. В результате он оказался в каталоге C:\учёба\химия\ГИА Укажите полный путь каталога, с которым пользователь начинал работу.

1) C:\учёба\2013\Расписание
2) C:\учёба\Расписание
3) C:\учёба\химия\Расписание
4) C:\Расписание

18748#18748

Пользователь работал с каталогом C:\Компьютеры\Память. Сначала он спустился в каталог Винчестеры, после этого поднялся на один уровень вверх, затем ещё раз поднялся на один уровень вверх и далее спустился в каталог Процессоры. Укажите полный путь каталога, в котором оказался пользователь.

1) C:\Компьютеры\Процессоры
2) C:\Винчестеры\Процессоры
3) C:\Компьютеры\Память\Винчестеры
4) C:\Компьютеры\Память\Процессоры


18747#18747

Пользователь находился в каталоге Расписание. Сначала он поднялся на один уровень вверх, затем спустился на один уровень вниз, потом ещё раз спустился на один уровень вниз и ещё раз спустился на один уровень вниз. В результате он оказался в каталоге C:\учёба\информатика\ГИА Укажите полный путь каталога, с которым пользователь начинал работу. 

1) C:\учёба\2013\Расписание
2) C:\учёба\Расписание
3) C:\учёба\информатика\Расписание
4) C:\Расписание


18746#18746

Пользователь работал с каталогом Логика. Сначала он поднялся на один уровень вверх, затем поднялся ещё на один уровень вверх, потом спустился на один уровень вниз. В результате он оказался в каталоге C:\Школа\Уроки\Химия.
Запишите возможный полный путь каталога, с которым пользователь начинал работу.

1) C:\Школа\Уроки\Информатика\Логика
2) C:\Школа\Уроки\Логика
3) C:\Школа\Логика
4) C:\Школа\Информатика\Логика


Сортировка
 
Во входном файле задано сначала число N (1<=N<=100),  а затем N целых
чисел, по модулю не превышающих 1000.
 
Выведите N чисел в порядке неубывания.
 
Пример входного файла
5
3 1 2 4 2
 
Пример выходного файла
1 2 2 3 4
Троллейбусы одного маршрута проходят через остановку каждые k (1<=k<=500) минут. Известны времена прихода пассажиров на эту остановку. Если пассажир приходит на остановку в момент прихода троллейбуса, то он успевает уехать на нем.
 
Напишите программу, которая бы определяла, во сколько должен пройти первый троллейбус (это время от 0 до k-1), чтобы:
1) Суммарное время ожидания троллейбуса для всех пассажиров было минимально.
2) Максимальное из времен ожидания троллейбуса было минимально.
 
Входные данные
В строке записано сначала число k, затем - число N (0<=N<=100000). Затем идет N чисел, задающих времена прихода пассажиров 
на остановку. Каждое из этих чисел - целое от 0 до 100000.
 
Выходные данные
Запишите два числа, являющиеся ответами на первый и второй вопросы задачи соответственно. 
Если решений несколько, выведите любое из них.

Примеры
Входные данные Выходные данные
1
100 5
0 210 99 551 99
10
51
 
 
Задача Иосифа Флавия
 
Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. 
В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили 
выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. 
Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места 
в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.
 
В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только 
один человек. (Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)
 
Задача: определить номер уцелевшего.
 
Входные данные: числа N и k вводятся из строки. 
Ограничения: 1<=N<=500, 1<=k<=100.
 
Выходные данные: Программа должна выдавать номер уцелевшего человека.
 
Пример входного файла:
10 3
 
Пример выходного файла:
4
Поделиться
Класснуть