Дистанционная подготовка к Всероссийской олимпиаде по информатике

ДВГУПС, преподаватель программы IT-школа Samsung,
Пономарчук Юлия Викторовна
E-mail: yulia.ponomarchuk@gmail.com

а искомое число равно k. Тогда код, осуществляющий поиск, можно

записать:

j := -1;
for i := 1 to n do
if a[i] = k then
j := i;

Если элемент, равный k, не найден, j=-1. В противном случае, j имеет значение индекса (номера) последнего вхождения k.

Сложность алгоритма – О(N)

Линейный поиск в неупорядоченных массивах

i:=i+1;

«Барьерный» метод
поиска первого вхождения элемента

поиска.
Выбираем ее середину.
Если искомый элемент меньше, чем средний,

то поиск осуществляется в левой части, иначе – в правой.
Сложность алгоритма – O(log N)


while (lbegin
m := (l+r) div 2;
if (a[m] else r :=m;
end;
if (a[r] = k) then write(r)
else write("-1");

уравнений и значений монотонных функций (убывающих или возрастающих).

Пример: вычислить кубический

корень с заданной точностью,
т.е. найти


r := x;
l := 1;
while (abs(l-r)>eps) do begin
m := (l+r) div 2;
if (m*m*melse r := m;
end;

олимпиады еще одну, Очень Легкую Задачу.
Ответственный секретарь Оргкомитета напечатал

ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий.
В его распоряжении имеется два ксерокса, один из которых копирует лист за x секунд, а другой – за y. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии).
Помогите выяснить, какое минимальное время в секундах для этого потребуется.
1 ≤ N ≤ 2*108, 1 ≤ x,y ≤ 10

и затем рассматриваем решение для N-1 страницы
Пусть l –

минимальное время, r – максимальное. Минимум – 0 секунд, максимум – (N-1)*x секунд (если страницы делаются полностью на одном ксероксе).
Считаем текущее среднее значение (l+r)/2 и смотрим, сколько полных страниц можно напечатать за это время, используя оба ксерокса.
Если количество страниц меньше N-1, то меняем нижнюю границу, иначе – верхнюю.

l, r, now : integer;
speed : double;
begin

read(n, i, j);
if (i < j) then begin
x := i;
y := j;
end else begin
x := j;
y := i;
end;
l := 0;
r := (n-1)*y;
while (l <> r) do begin
now := (l+r) div 2;
j := now div x + now div y;
if (j < n-1) then l := now+1
else r := now;
end;
write(r+x);
end.

людей, которые сядут в автобус
Если общее количество рабочих больше вместимости

автобуса – то объем автобуса
Если число рабочих меньше вместимости автобуса – то количество рабочих
Когда считываются данные, следует определить время прихода последнего человека (когда все люди будут на остановках) – максимум в бинарном поиске
Минимум равен нулю
Если автобус должен задержаться, он должен задержаться перед первой остановкой
Рассмотрим задержку x= (min+max)/ 2

до момента x на первую остановку
Для второй остановки задержка

автобуса: x+a[1]
a[1] – время следования от первой остановки до второй
Для третьей остановки задержка автобуса: x+a[1]+a[2] и т.д.
Если количество севших в автобус на всех остановках больше либо равна его вместимости, то надо заменить x на (min+x)/2
Если остались места в автобусе, то x=(x+max)/2
Условие выхода:
Если при некоторой задержке x автобус заполнен, а при задержке (x-1) автобус не полон, то ответ x

придти на определенную остановку до определенного момента
Максимум: количество

людей на остановке
Минимум: равен нулю
Выбираем среднего человека – если его время прихода меньше
x=(x+max)/2 – задержка автобуса
Если он не успеет придти, то x=(min+x)/2
Условие выхода: если человек успевает придти на остановку, а следующий за ним – нет, то ответом будет номер человека.
Отдельно следует обрабатывать случай, если на автобус сядут все люди с остановки

массива (т.е. если массив отсортирован по неубыванию, то k-я порядковая

статистика – это элемент, стоящий на k-ой позиции)

Схема алгоритма:
a – исходный массив (неотсортированный)
k – номер искомой порядковой статистики
l, r – текущая левая и правая границы области
Если l=r, то область поиска ограничена одним элементом, т.е. k-я порядковая статистика равна a[r]
На каждом шаге выбираем число s = (l+r)/2
Расположим элементы массива из интервала [l, r] так, чтобы сначала шли все элементы, меньшие a[s], а затем все остальные
Первый элемент второй группы обозначим за j
Если k≤j, то продолжаем поиск в левой части массива (с неизменным значением l и r=j)
Иначе продолжаем поиск в правой части массива (с неизменным значением r и l=j)

: integer);
var s, m, i, j, tmp : integer;
begin
i :=

l; j := r;
if (l = r) then
search := a[r]
else begin
s := (l + r) div 2;
m := a[s];
while (i < j) do begin
while (a[i] < m) do inc(i);
while (a[j] > m) do dec (j);
if (i < j) then begin
tmp := a[i];
a[i] := a[j];
a[j] := tmp;
inc(i); dec(j);
end;
end;
if (k < j) then search(a, k, l, j)
else search(a, k, i, r);
end;
end;