max := a[1] + a[2]; jmax := 1;

if (max<a[2]+a[3]) then

begin

max := a[2] + a[3];

jmax := 2;

end;

s := a[1] + a[2] + a[3] + a[4];

j1 := 1; j2 := 3;

for i:=4 to N-1 do

begin

sum2 := a[i] + a[i+1];

if (sum2+max>s) then

begin

j1 := jmax;

j2 := i;

s := sum2 + max;

end;

sum2max := a[i-1] + a[i];

if (sum2max>max) then

begin

max := sum2max;

jmax := i-1;

end;

end;

writeln(s);

end;

begin

inp;

proceed;

end.

NET

Задача. В офисе фирмы Megasoft установлены N компьютеров, пронумерованных от 1 до N, некоторые из них соединены между собой. Сообщение между соединенными компьютерами проходит за 1 секунду. Компьютер, получивший сообщение, сразу же отправляет его всем компьютерам, с ним соединенным. С какого компьютера главный программист Гилл Бейтс должен отправить сообщение, чтобы все компьютеры получили его как можно раньше?

Технические условия. Вы вводите с клавиатуры количество компьютеров (3?N?200), количество соединений K, а затем - K пар чисел, обозначающих соединение (первое число - источник, второе - приемник). Все числа разделены пробелами. Вы выводите на экран наименьший номер компьютера, с которого посылается сообщение. Если все компьютеры не могут получить сообщение, вывести 0.

Пример:

Ввод:

4 3 1 2 3 4 2 3

Вывод:

1

Математичекая формулировка. Задан орграф G(V,U) множеством своих вершин V и ребер U. Пусть W Н V - множество тех вершин, из которых доступны все остальные. А функция L(v), vОW - задает расстояние до наиболее удаленной от v вершины (под расстоянием между двумя вершинами подразумевается количество вершин/ребер в наикратчайшем соединяющем их пути). Тогда необходимо определить наименьший номер вершины v* такой, что L(v*) = min(L(v)), vОW, если W№Ж (в противном случае решением является 0, как указано в условии).

Описание алгоритма. Для решения оптимально подходит поиск в ширину для каждой вершины (так как вершины перебираются в порядке удаленности и последняя просмотренная вершина является одной из наиболее удаленных) с сохранением источника перехода: для каждой просматриваемой вершины запоминаем вершину, из которой мы в нее пришли. Последнее позволяет определить расстояние от любой вершины до данной после окончания поиска в ширину.

Суть задачи в том, чтобы сделать все операции по возможности быстрее. Для этого следует граф хранить в виде списков инцидентности и заканчивать поиск в ширину как только будут просмотрены все вершины (а не тогда, когда очередь станет пустой).

Итак, производим поиск для каждой вершины. Если из данной вершины доступны все остальные, вычисляем расстояние до последней из просмотренных вершин. Если это расстояние меньше (строго меньше), чем текущий минимум - данная вершина становится кандидатом на вывод. Если после поиска для всех вершин найдена хоть одна вершина из W, выводим номер последнего кандидата. Иначе - 0.

Код программы на языке Паскаль:

{ NetOI-2003: Tour2: NET}

program net;

var

N, L, vL, mx, H, T, unmarked, u, v, w: byte;

K, i, fl_size: word;

incd: array [1..200,0..200] of byte;

idle, que, last: array [1..200] of byte;

procedure readnbuild;

begin

read(N,K);

for i:=1 to N do incd[i,0] := 0;

for i:=1 to K do

begin

read(u,v);

inc(incd[u,0]);

incd[u,incd[u,0]] := v;

end;

end;

procedure proceed;

begin

L := 255; fl_size := N*sizeof(byte);

for v:=1 to N do

begin

fillchar(idle,fl_size,1); idle[v] := 0; unmarked := N-1;

H := 1; T := 1; que[1] := v;

repeat

u := que[H]; inc(H);

for i:=1 to incd[u,0] do

begin

w := incd[u,i];

if (idle[w]=1) then

begin

idle[w] := 0; dec(unmarked);

inc(T); que[T] := w;

last[w] := u;

end;

end;

until ((H>T) or (unmarked=0));

if (unmarked=0) then

begin

mx := 0; u := que[T];

while (u<>v) do

begin

inc(mx);

u := last[u];

end;

if (mx<L) then

begin

L := mx;

vL := v;

if (L=1) then

break;

end;

end;

end;

if (L=255) then vL := 0;

writeln(vL);

end;

begin

readnbuild;

proceed;

end.

DIGITS

Задача. Дано натуральное число K. Найти наименьшее число кратное К, все цифры которого одинаковы (пользуемся, естественно, десятиричной системой счисления).

Технические условия. Вы вводите с клавиатуры число K (2?K?1000). Вы выводите на экран цифру и количество этих цифр в искомом числе. Если решения не существует, вывести 0 0.

Пример:

Ввод:

37

Вывод:

1 3

Описание алгоритма. Оговоримся сразу, что для чисел, кратных 10, 16, 25 - решение не существует. Обозначим искомое число как qL_m, где qО1..9, L_m = Sum(D_i,i=0..m), D_i=10ⁱ. Тогда

(qL_m) mod K = (q(L_m mod K)) mod K

L_m mod K = (L_m-1 + D_m) mod K = (L_m-1 mod K + D_m mod K) mod K,

D_m mod K = (10D_m-1) mod K

Итак,

D_m mod K = (10D_m-1) mod K,

L_m mod K = (L_m-1 mod K + D_m mod K) mod K.

Полученные рекуррентные формулы позволяют решить задачу простым перебором значений m, q в порядке возрастания.

Комментарий. Перебор продолжается пока не будут найдены искомые параметры q, m. Как показала прогонка программы для всех возможных значений K, решение находится за допустимое время.

Код программы на языке Паскаль:

{ NetOI-2003: Tour2: DIGITS}

program digits;

var

K: word;

D, L, q, m: word;

b: boolean;

begin

read(K);

if ((K mod 10=0) or (K mod 16=0) or (K mod 25=0)) then

begin

q := 0; m := 0;

end

else

begin

D := 1; L := 1; m := 0;

b := true;

while (b) do

begin

m := m + 1;

for q:=1 to 9 do

if ((q*L) mod K=0) then

begin

b := false;

break;

end;

D := (10*D) mod K; L := (L+D) mod K;

end;

end;

writeln(q,' ',m);

end.

WAY

Задача. На декартовой плоскости заданы 2 точки своими целочисленными координатами. Фишка за 1 ход может переместиться в любую из 8 ближайших целочисленных точек. Сколько существует различных путей с минимальным количеством ходов фишки между двумя заданными точками?

Технические условия. Вы вводите с клавиатуры через пробел X1, Y1, X2, Y2 - координаты начальной и конечной точки (целые числа, не превосходящие 100 по абсолютной величине). Вы выводите на экран искомое количество путей.

Пример:

Ввод:

1 1 1 3

Вывод:

3

Описание алгоритма. Для начала заметим, что задача инвариантна относительно замен {X1,Y1} ? {X2,Y2}, {X1,X2} ? {Y1,Y2}. Поэтому, не умаляя общности, будем считать, что X1?X2, Y1?Y2, X2-X1 = a?b = Y2-Y1.

[Везде далее под путем будет понимать путь, соединяющий начальное и конечное положения фишки]

Далее, выясним, какова длина минимального пути. Очевидно, она не может быть меньше величины a, т.к. любой допустимый ход изменяет координаты фишки с шагом, не превышающим 1. Cуществует путь длины a: делаем (a-b)-шагов по горизонтали вправо и b-шагов по диагонали вправо-вверх. Вывод: длина минимального пути равна a. Т.о. задача сводится к отысканию количества различных путей длины a.

В силу предыдущих рассуждений можно делать только такие ходы: по диагонали вправо-вверх/вниз, по горизонтали вправо, т.к. каждый ход должен продвигать фишку на 1 по горизонтали в направлении цели (всего ходов - a, расстояние до цели по горизонтальной оси - a). Обозначим количество ходов в некотором минимальном пути по указанным направлениям символами p, q, r. Уравнения для проекций:

p+q+r = a

p-q = b

0?p,q,r?a.

Решение с параметром q:

p = b+q

r = a-b-2q

0?q?[(a-b)/2].

При любых конкретных значениях p,q,r количество путей с такими количествами ходов по соотв. направлениям определяется как количество перестановок из a элементов с повторениями p,q,r:

G_p,q,r = a!/(p!q!r!)

и решением задачи будет число:

N_a,b = Sum(G_b+q,q,a-b-2q, q=0..[(a-b)/2]).

В последней формуле легко выразить последующее слагаемое через предыдущее:

G_i+1,j+1,k-2 = k(k+1)/((i+1)(j+1))G_i,j,k.

Первое слагаемое:

G_b,0,a-b = a!/(b!0!(a-b)!) = a!/(b!(a-b)!) = C_a^b.

Комментарий. Очевидно, при заданных ограничениях на входные данные результат может превысить и 2³², и предел для типа comp в Pascal. Поэтому подсчет необходимо вести в длинных числах.

Текст программы не приводиться, он выноситься на самостоятельное написание.

NetOI-2004 Tour 3

MChess

Однажды юноша, который интересуется олимпиадными задачами по программированию, пошел на прогулку в лес. Гуляя по лесу, он встретил Злого Мишку, лесного зверя, который терпеть не может тех, кто ходит по его лесу. Мишка хотел принести парня в жертву, но, узнав что юноша - программист, решил сыграть с ним в игру "Лесные шахматы".

Игра имеет такие правила: на доске размером 3хN в первой горизонтали доски находится N черных пешек Злого Мишки, в третьей горизонтали находится N белых пешек мальчика, соответственно вторая горизонталь пустая. Злой Мишка и юноша ходят по очереди, начинает юноша. На каждом шаге игрок выбирает пешку, которой либо делает ход, либо сбивает пешку противника.

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

Пешка бьет фигуры по диагонали на одну клетку. В "лесных шахматах" сбивать фигуры обязательно: т.е. если можно сбить фигуру, это следует делать при этом ходе! Проигрывает тот, кто не сможет сделать очередной ход.

Ваша задача помочь юноше указать все возможные первые ходы, которые на 100% приведут его к победе, если его дальнейшая стратегия будет оптимальной.

Технические условия. Программа считывает с клавиатуры одно число N (1<=N<=1000).

Программа выводит на экран сначала число K - количество первых ходов юноши, ведущих к победе на 100% в случае оптимальной стратегии. Если таковых нет, тогда нужно вывести 0. Далее идут K чисел в порядке возрастания, которые показывают, какой по номеру белой пешкой должен ходить юноша.

Белые пешки нумеруются от 1 до N слева направо. Все числа выводятся через пробел.

Примеры.

Ввод> 3

Вывод> 1 2

Ввод> 2

Вывод> 2 1 2

Алгоритм: Строим последовательность A_i, i=0…(N_1) по следующим правилам: A₀=0; A₁=1; A₂=1. A_i+1 равно минимальному неотрицательному числу, которое не встречается во множестве (xor - «исключающее или» для двоичного представления чисел, например, 101 xor 110 = 11, т.е. 5 xor 6 = 3, или 1111 xor 1 = 1110, т.е. 15 xor 1 = 14). Выигрышными на доске 3хN будут те и только те ходы, которые «разбивают» позицию на две: 3xj и 3x(N_j_3), для которых , либо хода, которые оставляют позицию 3x(N_2), если A_{N_2}=0.

Код программы на языке Паскаль:

Program Mchess

const

dim=1007;

var

a,b:array[0..dim] of longint;

procedure Gen;

var

i,j:longint;

begin

a[0]:=0;

a[1]:=1;

a[2]:=1;

a[3]:=2;

for i:=4 to dim do

begin

fillchar(b,sizeof(b),0);

b[a[i-2]]:=1;

for j:=2 to i div 2+1 do

b[a[i-j-1] xor a[j-2]]:=1;

a[i]:=0;

while b[a[i]]=1 do inc(a[i]);

end;

end;

var

n,i,c:longint;

begin

read(n);

Gen;

{ for i:=1 to n do

if not a[i] then

writeln(i:3,'-',a[i]);}

if n=1 then begin writeln('1 1');halt; end;

if n=2 then begin writeln('2 1 2');halt; end;

if n=3 then begin writeln('1 2');halt; end;

fillchar(b,sizeof(b),0);

c:=0;

if a[n-2]=0 then

begin

b[1]:=1;

b[n]:=1;

inc(c,2);

end;

for i:=2 to n-1 do

begin

b[i]:=0;

if (a[n-i-1] xor a[i-2])=0 then b[i]:=1;

if b[i]=1 then inc(c);

end;

write(c,' ');

for i:=1 to n do

if b[i]=1 then write(i,' ');

writeln;

end.

Casino

Команда телевизионных игроков в "Что? Где? Когда?" села за стол для игры. Вопросы лежат каждый в своем секторе, все секторы заполнены. Секторы имеют произвольные номера. Если номера одинаковы, то цвета секторов разные. Волчок, стрелка которого вначале указывала на сектор с неким номером, раскрутили. Капитан команды запомнил не только номер этого сектора, но и всю последовательность номеров секторов, которые проходила стрелка в процессе вращения. Наиболее интересным оказалось то, что волчок, совершив целое количество оборотов, остановился, а стрелка оказалась напротив того же сектора, что вначале.

Какое минимальное количество вопросов может быть предложено для игры?

Технические условия. Программа читает с клавиатуры число N (2<=N<=30000) - количество номеров, которые запомнил капитан, а далее - N натуральных чисел, не больших 32000 - номера секторов, на которые указывала стрелка в процессе вращения. Первое число всегда совпадает с последним. Все числа разделены пробелами. Вы выводите на экран единственное число - минимально возможное количество конвертов с вопросами для игры.

Примеры.

Ввод> 13 5 3 1 3 5 2 5 3 1 3 5 2 5

Вывод> 6

Ввод> 4 1 1 1 1

Вывод> 1

Ввод> 4 1 2 3 1

Вывод> 3

Алгоритм: Для каждого делителя числа N-1, в порядке возрастания (начиная с единицы) непосредственно проверяем, может ли для игры быть предложено ровно такое количество вопросов. Первое подходящее число и будет ответом (как минимум одно число из множества делителей N-1 подходит - это само N-1).

Алгоритм 2 (быстрее) Изменение ответа по мере считывания, понятнее будет посмотреть в самом исходнике.

Код программы на языке Паскаль:

program casino;

var n,i,j: integer;

a: array[0..30000] of integer;

function is(m: integer): boolean;

var i: integer;

begin

is:=true;

for i:=m to n-1 do if a[i]<>a[i mod m] then begin

is:=false;

break;

end;

end;

begin

read(n);

dec(n);

for i:=0 to n do read(a[i]);

for i:=1 to n do if (n mod i=0) then if is(i) then break;

write(i);

end.

Casino2

В интеллектуальном казино "Что? Где? Когда?" разыгрывается N (1<= N<= 50) писем с вопросами для игроков. В начале игры письма раскладываются на круглом столе, разделенном на N секторов, по одному письму на сектор. Игра состоит из нескольких раундов, количество которых не превышает N. В начале каждого раунда определяется вопрос, который будет разыгран, по такому правилу. Запускается волчок, стоящий в центре стола; он останавливается в некотором секторе (мы считаем, что волчок никогда не останавливается на границе секторов). Если в этом секторе лежит вопрос, то он будет разыгран. В противном случае волчок вращают против часовой стрелке до первого сектора, в котором лежит письмо, и вопрос берут из этого письма. Письмо с вопросом, который разыгран, забирают со стола. Игра закончена. Вам известно, какие письма остались на столе. Выясните, сколько возможных последовательностей остановок волчка приводят к такой конфигурации в конце игры.

Технические условия. Вы вводите с клавиатуры число N, а далее - последовательность из N чисел 0 (письмо отсутствует) и 1 (письмо в секторе есть). Секторы пронумерованы против часовой стрелки. Вы выводите на экран единственное число - ответ на задачу.

Примеры.

Ввод> 3 0 1 0

Вывод> 3

Ввод> 6 1 0 1 0 0 0

Вывод> 64

Алгоритм: Пусть m связных последовательностей нулей имеют длины A₁, A₂,…, A_m (например, для случая входных данных 6 1 0 1 0 0 0, m=2, A₁=1, A₂=3, для 3 0 1 0: m=1, A₁=2). Ответом тогда будет число

Не стоит забывать о длинной арифметике и о случае, когда все секторы пустые (ответом тогда будет N^N).

Вся сложность данной программы заключается в написании длинной арифметики. Данная тема в некоторой мере была нами уже рассмотрена в I части, посоветую ещё обратиться к дополнительной литературе (Том Кнут, «Art of Computer Programming» том 2). Поэтому текст программы выносится на самостоятельное рассмотрение.

CRANE

На станции Глупов-Товарный используются подъемные краны специальной конструкции "Мостовой-Глуповский". Крюк такого крана подвешен к нескольким блокам, которые ездят по рельсу, размещенному горизонтально (на некоторой высоте). Благодаря этому, крюк можно перемещать в любую точку части плоскости, ограниченной многоугольником специального вида: верхняя сторона многоугольника совпадает с рельсом крана, оба внутренние угла многоугольника при этой стороне острые, остальные вершины многоугольника размещены произвольно, но так, что многоугольник оказывается выпуклым. Кроме этого, станция имеет в распоряжении устройство, которое позволяет комбинировать действие двух кранов такого типа: пространство достижимости крюка скомбинированного механизма точно такой, если бы рельс второго крана подвесили (с сохранением горизонтальности) на крюк первого.

Задание. Напишите програму, которая будет выполнять следующие два действия:

1. По заданными областям достижимости двух кранов находит область достижимости их комбинации.

2. По заданной области достижимости одного крана и необходимой области достижимости, выяснить, какой нужно взять второй кран, чтобы комбинация первого и второго кранов в точности совпадала с нужной областью достижимости (либо выясняла, что это невозможно).

Технические условия. Введите с клавиатуры сначала 1 или 2 (в зависимости от того, какую задачу требуется решить), затем идут две области. Если решается задача "1", то это области достижимости первого и второго кранов, если "2", то вначале нужную область достижимости, а затем область достижимости первого крана. Все области достижимости задаются в таком формате: вначале число N (3<=N<=1000) - количество вершин в многоугольнике, а далее N групп по 2 числа x_i и y_i - координаты вершин этой области в порядке возрастания x - координаты. Система координат всегда выбирается так, что первая вершина имеет координаты (0; 0), ось y направлена сверху вниз. Все входные координаты - целые числа, не превышающие по модулю 10⁶. Если решается задача "2" и подобрать второй кран невозможно, то вывести на экран единственное число 0. Иначе вывести построенную область достижимости (в том же формате, что для входных данных).

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

Примеры.

Ввод>

2 5 0 0 10 40 20 50 30 40 40 0 3 0 0 10 10 20 0

Вывод> 3 0 0 10 40 20 0

Ввод> 2 3 0 0 10 10 20 0 3 0 0 10 10 40 0

Вывод> 0

Ввод> 1 3 0 0 10 10 20 0 3 0 0 10 10 40 0

Вывод> 4 0 0 20 20 50 10 60 0

Алгоритм: Рассмотрим множество векторов, соединяющих соседние вершины каждого из многоугольников - выходящих из вершины с меньшим номером к вершине с большим для первого и: если выполняется первая подзадача, то таких же; если вторая - то выходящих из вершины с большим номером к вершине с меньшим, для второго многоугольника. Теперь сложим все попарно коллинеарные (в том числе и противоположно направленные) векторы, т.е. вместо наборов таких векторов «запишем» их сумму. Если при этом получились векторы с неположительной x-координатой, построить нужный многоугольник не удастся. Иначе упорядочим по возрастанию все получившееся векторы относительно угла, который они образуют с положительным направлением оси ординат. Восстановленный по этим векторам, как по последовательным сторонам многоугольник, и будет искомым.

Код программы на языке Паскаль:

Program crane;

const

con=1000;

type typ=longint;

koor=record

x,y:typ;

end;

var a,b:array[1..con] of koor;

c:array[1..2000] of koor;

jj,x,li,lj,ni,nj,pi,pj,k,i,j,v,n,m:longint;

v1,v2,v3,v4,v5,v6:typ;

a1,a2,p1,p0,p:koor;

flag,ans:boolean;

procedure read_data;

begin

read(v);

read(m);for i:=1 to m do read(b[i].x,b[i].y);

read(n);for i:=1 to n do read(a[i].x,a[i].y);

end;

procedure algor;

function vect(p1,p2:koor):typ;

var ff:extended;

begin

ff:=(p1.x+0.0)*(p2.y+0.0)-(p1.y+0.0)*(p2.x+0.0);

if abs(ff)<0.5 then vect:=0 else

if ff>0 then vect:=1 else if ff<0 then vect:=-1;

end;

function cry(a1,a2,a3,b1,b2,b3:koor):boolean;

begin

a1.x:=a1.x-a2.x;a1.y:=a1.y-a2.y;

a3.x:=a3.x-a2.x;a3.y:=a3.y-a2.y;

b1.x:=b1.x-b2.x;b1.y:=b1.y-b2.y;

b3.x:=b3.x-b2.x;b3.y:=b3.y-b2.y;

v1:=vect(a1,b1);v2:=vect(a1,b3);v3:=vect(a1,a3);

v4:=vect(a3,b1);v5:=vect(a3,b3);v6:=vect(a3,a1);

if (((v1>=0) and (v2>=0) and (v3>=0)) or ((v1<=0) and (v2<=0) and (v3<=0))) and

(((v4>=0) and (v5>=0) and (v6>=0)) or ((v4<=0) and (v5<=0) and (v6<=0))) then

cry:=true

else

cry:=false;

end;

procedure case2;

begin

ans:=true;

inc(k);j:=1;pj:=n;nj:=2;

for i:=2 to m do

begin

ni:=i+1;if ni>m then ni:=1;

while (j<=n) and not(cry(b[i-1],b[i],b[ni],a[pj],a[j],a[nj])) do begin inc(j); pj:=j-1; nj:=j+1; if nj>n then nj:=1; end;

if j>n then begin ans:=false; exit; end;

p.x:=b[i].x-a[j].x;p.y:=b[i].y-a[j].y;

if (p.x<>c[k].x) or (p.y<>c[k].y) then

begin

inc(k);

c[k]:=p;

end;

end;

end;

procedure case1;

function may:boolean;

begin

ni:=i+1;if ni>m then ni:=1;

nj:=j+1;if nj>m then nj:=1;

li:=i-1;if li<1 then li:=m;

lj:=j-1;if lj<1 then lj:=m;

p0.x:=a[x].x+b[i].x;p0.y:=a[x].y+b[i].y;

p1.x:=a[x+1].x+b[j].x-p0.x;p1.y:=a[x+1].y+b[j].y-p0.y;

a1.x:=a[x].x+b[li].x-p0.x;a1.y:=a[x].y+b[li].y-p0.y;

a2.x:=a[x].x+b[ni].x-p0.x;a2.y:=a[x].y+b[ni].y-p0.y;

v1:=vect(p1,a1);v2:=vect(p1,a2);

if not((v1<=0) and (v2<=0)) then begin may:=false; exit; end;

may:=true;

p0.x:=a[x+1].x+b[j].x;p0.y:=a[x+1].y+b[j].y;

p1.x:=a[x].x+b[i].x-p0.x;p1.y:=a[x].y+b[i].y-p0.y;

a1.x:=a[x+1].x+b[lj].x-p0.x;a1.y:=a[x+1].y+b[lj].y-p0.y;

a2.x:=a[x+1].x+b[nj].x-p0.x;a2.y:=a[x+1].y+b[nj].y-p0.y;

v1:=vect(p1,a1);v2:=vect(p1,a2);

if not((v1>=0) and (v2>=0)) then begin may:=false; exit; end;

may:=true;

end;

begin

inc(k);

i:=1;

for X:=1 to n-1 do

begin

flag:=false;

while not flag do

begin

for j:=i to m do

if may then

begin

if flag then dec(k);

flag:=true;

inc(k);

c[k].x:=a[x+1].x+b[j].x;

c[k].y:=a[x+1].y+b[j].y;

jj:=j;

end else if flag then break;

if flag then i:=jj;

if not flag then

begin

inc(i);

inc(k);

c[k].x:=a[x].x+b[i].x;

c[k].y:=a[x].y+b[i].y;

end;

end;

end;

inc(i);

while i<=m do

begin

inc(k);

c[k].x:=a[n].x+b[i].x;

c[k].y:=a[n].y+b[i].y;

inc(i);

end;

ans:=true;

end;

begin

case v of

1:case1;

2:

begin

case2;

if not ans then exit;

ans:=false;

for i:=1 to k do

if c[i].y<0 then begin ans:=false; exit; end else

if c[i].y>0 then ans:=true;

end;

end;

end;

procedure write_data;

begin

if ans then

begin

write(k);

for i:=1 to k do write(' ',c[i].x,' ',c[i].y);

writeln;

end else writeln(0);

end;

begin

read_data;

algor;

write_data;

end.

Hard

В компании Megasoft сотрудники начали жаловаться на недостаток места на жестких дисках. Каждый сотрудник может иметь в своем распоряжении только один диск. Владелец компании Гилл Бейтс предложил решение проблемы: некоторые сотрудники поменяются ЖД с другими, а остальным приобрести новые ЖД. Он составил список имеющихся ЖД и потребностей сотрудников. Гилл Бейтс программирует только на Basic, а этот язык не используется на NetOI. Hапишите за него программу для нахождения минимального количества ЖД, которые необходимо приобрести, чтобы удовлетворит потребности всех сотрудников.

Технические условия. Программа вводит с клавиатуры количество сотрудников N, (1<=N<=10000), а дале - N пар чисел в одну строку: первое число - емкость имеющегося ЖД, второе - потребность сотрудника. Все числа натуральные, не большие 1000, разделенные пробелами. Программа выводит на экран единственное число - ответ задачи.

Пример.

Ввод> 4 2 4 4 1 5 4 7 8

Вывод> 1

Алгоритм: Упорядочим и емкости имеющихся винчестеров, и “необходимые” емкости по убыванию. Возьмем наибольшую “необходимую” емкость, не превосходящую наибольшую из “имеющихся”. Теперь возьмем наибольшую из меньших уже взятой необходимой емкости, которая не превосходит второй по величине имеющейся. Далее наибольшую из меньших только что взятой емкость, которая не превосходит третью по величине имеющуюся и т.д., вплоть до того момента, когда мы уже не сможем взять такую “необходимую” емкость, которая не превосходила бы очередную “имеющуюся”. Ответом будет количество таких “имеющихся” емкостей, которые не получили в соответствие некоторую “необходимую”.

Код программы на языке Паскаль:

program hard;

type list = array[1..10000] of integer;

var n,i,j: integer;

a,b: list;

begin

read(n);

for i:=1 to n do read(a[i],b[i]);

sort(a); {процедура сортировки массива}

sort(b);

j:=n; i:=n;

while (i>0) and (j>0) do

begin

while (j>0) and (a[i]<b[j]) do dec(j);

dec(j);

if j>=0 then dec(i);

end;

write(i);

end.

BEAR

Задача. Маленький медвежонок идет по дороге, вдоль которой на расстоянии М одно от другого растут деревья. Останавливаясь под каждым деревом, медвежонок забывает, откуда пришел, и, двигаясь через некоторое время дальше, случайно выбирает то или иное направление движения. На каком расстоянии от "стартового" дерева может быть медвежонок после К этапов?

Технические условия. Программа считывает с клавиатуры числа M и К через пробел (1 ? М, К ? 10000). Программа выводит на экран в одной строке через пробелы расстояния, на которых может находиться медвежонок (от меньшего до большего).

Пример

Ввод 2 6

Вывод 0 4 8 12

Решение. Рассмотрим случай M=1.

Заметим, что всевозможные пройденные мишкой расстояния имеют одинаковую чётность, равную чётности числа К (так как при каждом переходе чётность меняется). Кроме того, медвежонок всегда может попасть в точку с координатой 0 (при чётном K) или с координатой 1 (при нечётном), ему также доступна точка с координатой K. Несложно заметить, что мишка может попасть во все точки между 0 и K, координаты которых равны К по чётности (несколько раз ходим взад-вперёд, затем а раз прямо, a ? K).

Исходя из вышесказанного, ответом будут все целые числа от 0 до K, равные К по чётности (т.е., сравнимые с K по модулю 2).

В случае M>1, умножаем все числа в ответе на M.

Сложность алгоритма: O(K).

Код программы на языке Паскаль:

{ NetOI-2005: Tour1: BEAR}

Program BEAR;

var

m,k,i,t:longint;

begin

read(m,k);

t:= (k mod 2)-2;

for i:=1 to (k div 2) +1 do

begin

t:=t+2;

write(t*m,' ');

end;

end.

Piece

Задача. Имеется окружность радиуса R с координатами центра (x;y) и прямая, заданная координатами двух своих точек. Какой длины отрезок прямой лежит внутри окружности?

Технические условия. Программа читает с клавиатуры строку из 7-ми чисел: радиус окружности, координаты x и y центра и координаты 2-х точек прямой. Все числа целые, по абсолютной величине не превосходят 10000. Результат вывести на экран, не округляя. Если окружность и прямая не пересекаются, вывести -1, если касаются - вывести 0.

Пример

Ввод 5 0 0 4 1 4 2

Вывод 6.0000000000000000E+0000

Решение. Сначала двигаем плоскость на вектор (-x;-y), чтобы точка (x;y) перешла в точку (0;0) в новой системе координат.

Далее, находим расстояние от центра окружности до прямой. Неплохой способ - подсчет высоты в треугольнике OAB с помощью формулы H = 2•S_?OAB/AB, где 2S_?OAB подчитывается как модуль псевдоскалярного произведения векторов и ((a;b)(c;d) = ad-bc). Зная расстояние, легко перейти к длине секущей:

Если H > R - пересечения нет

H = R - касание

H < R - пересечение, длина секущей: L² = 2(R² - H²) (теорема Пифагора)

Не забываем делать “допуск” для условия касания, вместо H = R пишем:

abs(H-R) ? 0.00001

Сложность алгоритма: O(1).

Код программы на языке Паскаль:

{ NetOI-2005: Tour1: PIECE}

Program PIECE;

var

r,o1,o2,x1,y1,x2,y2,d,ps,l:real;

begin

read(r,o1,o2,x1,y1,x2,y2);

x1:=x1-o1;

x2:=x2-o1;

y1:=y1-o2;

y2:=y2-o2;

l:=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

ps:=abs(x1*y2-x2*y1);

if ps=0 then d:=0 else d:=ps/l;

if d>r+0.00001 then writeln(-1) else

if abs(d-r)<0.00001 then writeln(0) else

writeln(2*sqrt(r*r-d*d));

end.

Blamblam

Задача. Главнокомандующий армии блямблямчиков, проводя заседание Генерального штаба, приказал блямблямскому офицеру по особым поручениям расстелить на столе секретную карту боевых действий, причём так, чтобы она полностью лежала на поверхности стола. Сумеет ли офицер выполнить это поручение, если размеры стола AxB, а карта нарисована на прямоугольном листке бумаги размерами XxY?

Технические условия. Программа читает с клавиатуры натуральное число N (1 ? N ? 10) - количество попыток положить карту на стол, а далее N групп по 4 натуральных числа (каждая группа - числа X, Y, A, B). Все числа в одной строке, разделены пробелами и не превышают 100. Программа выводит на экран последовательность из N нулей и единиц - нуль, если попытка не удалась, единица - если карта поместилась на столе.

Пример

Ввод 2 1 10 9 9 99 99 2 2

Вывод 10

Решение. Для каждой попытки проведём следующие рассуждения:

Пусть мы упорядочили координаты, и теперь A ? B, X ? Y. Если X > A, поручение, и это несложно понять, выполнить не удастся. Если же X ? A и Y ? B, поручение, очевидно, выполнить можно. Таким образом, осталось рассмотреть единственный случай: X ? A, Y > B. Для этого «положим» прямоугольник AxB на его большую сторону (т.е., представим, что сторона длиной B этого прямоугольника расположена в пространстве горизонтально). Теперь «положим» и прямоугольник XxY на его большую сторону так, чтобы, скажем, левые нижние концы обоих прямоугольников совпадали. На такой картинке получается, что карта «помещается» на стол по высоте, но выходил за его пределы по длине. Если теперь поворачивать прямоугольник XxY против часовой стрелки, так чтобы он «упирался» в левый нижний угол AxB, то рано или поздно настанет момент, когда первый начнёт «помещаться» во втором по ширине (т.к. в крайнем положении, когда XxY повернётся на 90^о относительно своего начального положения, он будет помещаться по ширине: X ? A ? B). Всё что нужно - определить, будет ли ещё в этот момент XxY помещаться и по высоте.

Иначе говоря, обозначив, допустим, угол между большими сторонами прямоугольников через б, а затем, решив уравнение Xsinб + Ycosб = B и подставив получившееся значение б в неравенство Xcosб + Ysinб ? A, в зависимости от его истинности, даём ответ.

Всё это можно реализовать, скажем, двоичным поиском. А можно просто заменой переменных:

, , .

Сложность алгоритма: O(N) (решение с помощью замены переменных).

Код программы на языке Паскаль:

{ NetOI-2005: Tour1: BLAMBLAM}

Program BLAMBLAM;

var

f:boolean;

h,l,a,b:real;

i,n:integer;

function arcsin(x:real):real;

begin

if x=1 then arcsin:=pi/2 else begin

arcsin:=arctan(x/(sqrt(1-x*x)));

end;

end;

function ins(h,l,a,b:real):boolean;

var d,alpha,beta,dl:real;

begin

if (b<h+0.0001) then ins:=(a<l+0.0001)else

begin

d:=sqrt(a*a+b*b);

alpha:=arcsin(h/d);

beta:=arcsin(b/d);

dl:=-d*cos(alpha+beta*2);

if dl-l<0.0001 then ins:=true

else ins:=false;

end;

end;

begin

read(n);

for i:=1 to n do begin

read(a,b,h,l);

f:=ins(h,l,a,b) or

ins(h,l,b,a);

if f then write(1)else write(0);

end;

end.

Вот еще одно решение:

Program BLAMBLAM2;

var a,ans,b,i,n,x,y:integer;

begin

read(n);

for i:=1 to n do

begin

read(x,y,a,b);

if x>y then

begin

ans:=x;

x:=y;

y:=ans;

end;

if a>b then

begin

ans:=a;

a:=b;

b:=ans;

end;

if y<=b then

if x<=a then ans:=1 else ans:=0

else

if (x>=a) or (sqrt(x*x+y*y-b*b)+2*cos(arctan(x/y) + arctan(sqrt(x*x+y*y-b*b)/b))*x-a>1e-6) then ans:=0 else ans:=1;

write(ans);

end;

end.

Newpatience

Задача. Многие в свободное время увлекаются разложением пасьянсов. Предлагаем вам еще один, правда, карты для него нужно изготовить самостоятельно. Итак, на N карточках нанесите натуральные числа по одному числу на каждой стороне карточки так, что каждое из чисел наносилось ровно 2 раза. Карточки разложите на столе в ряд. Все готово. Можно начинать. В процессе игры карточки можно переворачивать другой стороной. Пасьянс сходится тогда, когда, перевернув некоторые карточки, вы получите возможность видеть все N чисел одновременно. Сойдётся ли пасьянс, а если да, то какое наименьшее количество карточек необходимо для этого перевернуть?

Технические условия. Программа читает с клавиатуры число N (N < 10000), а далее 2 группы по N чисел - сначала числа на одной из сторон каждой из N карточек (игрок их видит в начале игры), а затем числа, нанесенные на эти же карточки, но на противоположную сторону. Все числа вводятся одной строкой через пробелы. Вы выводите на экран одно число: -1, если пасьянс не "сошёлся", либо минимальное количество перевернутых другой стороной карточек, если игра завершилась успехом.

Пример

Ввод 5 3 2 5 3 2 5 4 1 1 4

Вывод 2

Решение. Назовем циклом последовательность из a карточек такой, что у любых двух последовательных (а также у 1-ой и а-ой) карточек есть общее число. Решим задачу для цикла: найдем общее число карточек 1 и 2, повернём карточку 1 этим числом вверх.

Для всех 1 < x ? a повернем карточку x вниз тем числом, которое сверху у карточки х-1. В итоге получаем сошедшийся пасьянс. Количество ходов при этом (t) определяется однозначно. Можно заметить, что при этом существует еще всего один способ собрать пасьянс: повернуть все карточки наоборот. Количество ходов при этом: a-t. Поэтому нужно выбрать минимум из этих двух чисел. Это и будет минимальное число ходов, чтобы собрать цикл. Теперь разбиваем весь исходный набор на циклы (последовательность карточек в цикле не обязательно совпадает с последовательностью карточек на столе), и считаем для каждого цикла минимальное количество ходов, необходимое, чтобы его собрать. Сумма всех этик чисел и будет ответом. Заодно мы, кстати, доказали, что любой пасьянс сходится.

Сложность алгоритма: O(N).

{ NetOI-2005: Tour1 NEWPATIENCE}

Program NEWPATIENCE;

const nmax=10000;{10000}

mw=65536; {65536}

var

k:array[1..nmax,1..2]of integer;

po:array[1..mw,1..2]of integer;

was:array[1..nmax]of boolean;

i,n,sum:longint;

function look(p:integer):integer;

var t,w,w1,n,h,kol:longint;

rudik:boolean;

begin

was[p]:=true;

n:=0;

kol:=1;

if k[p,1]=k[p,2] then look:=0 else begin

w:=po[k[p,2],1]+po[k[p,2],2]-p;

w1:=p;

while not was[w] do begin

rudik:=true;

was[w]:=true;

inc(kol);

if k[w1,2]<>k[w,1] then begin

inc(n);

h:=k[w,1];

k[w,1]:=k[w,2];

k[w,2]:=h;

rudik:=false;

end;

w1:=w;

w:=po[k[w,2],1]+po[k[w,2],2]-w;

end;

end;

if n<kol-n then look:=n else

look:=kol-n;

end;

begin

read(n);

fillchar(po,sizeof(po),0);

fillchar(was,sizeof(was),false);

sum:=0;

for i:=1 to n do begin

read(k[i,1]);

if po[k[i,1],1]=0 then po[k[i,1],1]:=i else

po[k[i,1],2]:=i;

end;

for i:=1 to n do begin

read(k[i,1]);

if po[k[i,1],1]=0 then po[k[i,1],1]:=i else

po[k[i,1],2]:=i;

end;

for i:=1 to n do begin

read(k[i,2]);

if po[k[i,2],1]=0 then po[k[i,2],1]:=i else

po[k[i,2],2]:=i;

end;

i:=1;

while i<=n do begin

while (i<=n)and(was[i]) do inc(i);

if i<=n then sum:=sum+look(i);

end;

writeln(sum);

end.

Circuit

Задача. Дана цепочка, состоящая из k = 4n звеньев. Причем 2n звеньев - золотые и 2n звеньев - серебряные. Два разбойника желают справедливо разделить серебро и золото данной цепочки. Составьте программу, которая находит минимальное количество разрезов цепочки, таких, что после разрезания, как серебро, так и золото можно было разделить между двумя разбойниками.

Технические условия. Программа читает с клавиатуры количество звеньев k, а далее - k чисел 0 либо 1 (0 - серебряное звено, 1 - золотое). Все числа вводятся одной строкой через пробелы. Программа выводит на экран количество разрезов и номера звеньев, между которыми они были сделаны. Первый разрез должен находиться как можно ближе к началу цепи. N < 10000.

Пример

Ввод 8 0 1 0 0 1 1 0 1

Вывод 2 1 2 5 6

Решение. Создадим массив a[i], i=0..k по такому правилу: a[0]=0, a[i] - это разность золотых и серебряных звеньев цепи среди первых n (создается в один проход), легко видеть, что цепь можно разделить правильно одним разрезом тогда и только тогда когда a[2n]=0. Проверяем этот случай.

Докажем, что в ином случае можно обойтись двумя разрезами и найдем их. Рассмотрим функцию f(x) = a[x+2n-1]-a[x-1]. Она равна разности числа золотых и серебряных звеньев в отрезке цепи длиной 2n с x по x+2n-1. Если f(x)=0, то этот отрезок даем одному разбойнику, остаток - другому. Все довольны. Докажем, что у функции f всегда есть корень.

Пусть это не так. Заметим, что f всегда принимает чётные значения. f(1) = -f(2n) (так как соответствующие куски дают в сумме всю цепь, а количества звеньев в них меняются местами). Также заметим: f(x+1) отличается от f(x) не более чем на 2.

Кроме того, так как f(1)?0, f(1) и f(2n) имеют разный знак. Следовательно, найдётся такое t, что f(t) и f(t+1) имеют разный знак (не забываем, что, по предположению, значение 0 функция принимать не может). Однако из этого следует, что f(t) и f(t+1) отличаются как минимум на 4, что невозможно. Противоречие. Значит, f(x) имеет корень. Найдём наименьший из корней перебором, и выведем соответствующее ему разрезание цепи.

Следует отметить, что корни функции f(x) дают всевозможные соответствующие «хорошие» разрезания цепи двумя разрезами.

Сложность алгоритма: O(K).

Код программы на языке Паскаль:

{ NetOI-2005: Tour1: CIRCUIT}

Program CIRCUIT;

const

nmax=40000;

var

z:array[0..nmax]of integer;

i,n,k,t:word;

begin

z[0]:=0;

read(k);

n:= k div 2;

for i:=1 to k do begin

read(t);

if t=1 then z[i]:=z[i-1]+1 else

z[i]:=z[i-1]-1;

end;

if z[n]=0 then write(1,' ',n,' ',n+1) else

begin

t:=0;

for i:=1 to n do

if (z[i+n-1]=z[i-1])and(t=0) then

t:=i;

write(2,' ',t-1,' ',t,' ',t+n-1,' ',t+n);

end;

end.

Wood

Задача. Из деревянных палочек очень маленькой толщины сделан жесткий выпуклый многоугольник. Он размещен в вертикальной плоскости так, что опирается одной из своих сторон (назовем ее "основанием") на дно посудины, у-координата которых равна 0. Ширина посудины почти так же мала, как и толщина палочек, но трение между стенками и палочками отсутствует. В посудину понемногу наливают воду, на погруженную часть начинает действовать архимедова сила, и, при достижении некоторого критического уровня воды, многоугольник отрывается от опоры всегда одновременно всеми своими точками, то есть основание многоугольника достаточно велико, чтобы он не "опрокидывался" в процессе доливания воды, но в то же время достаточно мало, чтобы многоугольник не начал плавать, когда водой покрыто только лишь основание. Найдите критический уровень воды.

Технические условия. Программа читает с клавиатуры количество вершин деревянного многоугольника N (3<=N<=500), следующие N пар чисел содержат x- и y-координаты вершин (начиная с левой вершины основания, в порядке по часовой стрелке; значения координат - действительные числа, не превосходящие по модулю 2000000 (два миллиона); потом идет последнее число p - плотность древесины, измеренная в г/см³(0,3<=p<=0,98). Все числа разделены пробелами. Результат (единственное действительное число, с точностью не менее двух знаков после запятой) программа выводит на экран.

Пример

Ввод> 4 -2 0 4 3 6 2 6 0 0.75

Вывод> 1.92

Решение. Считываем координаты всех вершин, сохраняем их в массив. Нумеруем все вершины от 1 до n. Попутно создаем массив Long[i], i=1..n+1 по такому правилу: Long[1]=0, Long[i] = длина ломаной соединяющей вершины нашей фигуры от 1 до i. Также находится верхняя точка нашего многоугольника (если многоугольник содержит горизонтальный отрезок, отличный от основания, то этот факт отмечается). Задачу можно переформулировать так: найти уровень воды, при котором общая длина частей ребер ломаной, покрытых водой равна Long[n+1]*p. Легко видеть, что при возрастании уровня воды - суммарная длинна покрытых отрезков возрастает. Применим для поиска необходимого уровня двоичный поиск.

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

Иначе двоичным поиском находим, при каком уровне воды выполняется условие: общая длина частей ребер ломаной, покрытых водой равна Long[n+1]*p.

Для конкретного уровня воды длина частей отрезков, покрытых водой, определяется так: Находим, по каким двум отрезкам проходит поверхность воды (из-за выпуклости многоугольника таких отрезков всегда два) (Это делается двоичным поиском за О(log(n))). Добавляем к результату суммарную длину всех покрытых водой отрезков (благодаря массиву Long[i], это делается за О(1)), и считаем, какая их часть покрыта водой (лично я делал это из теоремы Фалеса) Потом полученные числа суммируем и получаем длину частей отрезков, покрытых водой. Далее определяется, всплывает ли многоугольник и продолжается поиск.

Сложность: О(n)

Код программы на языке Паскаль:

{NetOI-2005: Tour2: WOOD}

Program WOOD;

var

n,maxn,i,verh:integer;

long,p:real;

vmax,vmin,vtec,visota:real;

ver:array[1..500,1..2]of real;

dlinna:array[1..501]of real;

function min(a,b:real):real;

begin

if a<b then min:=a else

min:=b;

end;

function pod(n:integer;h:real):real;

begin

pod:=(dlinna[n+1]-dlinna[n])*abs(h-min(ver[n,2],ver[n+1,2]))/abs(ver[n,2]-ver[n+1,2]);

end;

function podvod(h:real):real;

var nmin,nmax,ntec:integer;

pv:real;

begin

pv:=0;

nmin:=1;

nmax:=verh;

ntec:=(nmin+nmax) div 2;

while nmin<nmax-1 do

begin

if h>=ver[ntec,2] then nmin:=ntec

else nmax:=ntec;

ntec:=(nmin+nmax) div 2;

end;

pv:=dlinna[ntec]+pod(ntec,h);

nmin:=verh;

nmax:=n;

ntec:=(nmin+nmax) div 2;

while nmin<nmax-1 do

begin

if h<=ver[ntec,2] then nmin:=ntec

else nmax:=ntec;

ntec:=(nmin+nmax) div 2;

end;

pv:=pv+dlinna[n+1]-dlinna[ntec+1]+pod(ntec,h);

podvod:=pv;

end;

begin

read(n);

verh:=-1;

read(ver[1,1],ver[1,2]);

dlinna[1]:=0;

for i:=2 to n do begin

read(ver[i,1],ver[i,2]);

long:=long+

sqrt((ver[i,1]-ver[i-1,1])*(ver[i,1]-ver[i-1,1])+

(ver[i,2]-ver[i-1,2])*(ver[i,2]-ver[i-1,2]));

dlinna[i]:=long;

if (verh=-1) and (ver[i,2]<=ver[i-1,2]) then verh:=i-1;

end;

long:=long+

sqrt((ver[n,1]-ver[1,1])*(ver[n,1]-ver[1,1])+

(ver[n,2]-ver[1,2])*(ver[n,2]-ver[1,2]));

dlinna[n+1]:=long;

read(p);

if (ver[verh,2]=ver[verh+1,2])and

(dlinna[n+1]+dlinna[verh]-dlinna[verh+1]<=dlinna[n+1]*p)

then write(ver[verh,2])

else begin

vmax:=ver[verh,2];

vmin:=0;

vtec:=(vmax+vmin)/2;

while (vmax-vmin>1e-3) do begin

visota:=podvod(vtec);

if visota<=dlinna[n+1]*p then vmin:=vtec else

vmax:=vtec;

vtec:=(vmin+vmax)/2;

end;

writeln(vtec);

end;

end.

DSP

Задача. Имеется прямоугольный кусок ДСП (древесно-стружечная плита). Из этого куска необходимо изготовить несколько одинаковых деталей прямоугольной формы. Специализированный станок может распилить любой кусок ДСП только параллельно кромке и только от края до края. Какое наибольшее количество деталей можно изготовить из данного куска?

Технические условия. Вы вводите с клавиатуры числа M и N - размеры листа, затем A и B - размеры детали (1 <= M,N,A,B <= 200). Все числа разделены пробелом. Вы выводите на экран искомое количество деталей.

Пример

Ввод> 12 6 2 5

Вывод> 7

Решение №1 (более долгое). Динамически создаем массив Kol[i, j] = количество деталей, которые можно получить из куска фанеры i*j. Находится он так Kol[a,b]=Kol[b,a], Иначе, перебираются все варианты первого разреза листа (для меньших листов мы уже знаем) В ответ идет Kol[M,N]. Всего мы заполняем m*n клеток массива, каждую за O(m+n).

Сложность: О(m*n*(m+n))

Решение №2 (более быстрое). Итак, у нас есть наверняка правильный алгоритм разрезания. В голову приходит теоретически верный алгоритм: Разрезаем весь кусок на две части, каждую из них снова на две, а четыре получившиеся части - на прямоугольники a*b, но с одинаковой ориентацией. Перебираем все разрезания (за O((m+n)^2)) и выводим наибольшее число. Казалось бы, этот алгоритм не доказан и не может быть принят без доказательства. Но у нас есть правильный (хотя и медленный) алгоритм. Полным перебором проверяем, что при всех допустимых входных данных ответы алгоритмов совпадают, а значит, второй алгоритм тоже верен.

Сложность: O((m+n)^2)

Код программы на языке Паскаль:

{NetOI-2005: Tour2: DSP}

Program DSP;

var

r,o1,o2,x1,y1,x2,y2,d,ps,l:real;

begin

read(r,o1,o2,x1,y1,x2,y2);

x1:=x1-o1;

x2:=x2-o1;

y1:=y1-o2;

y2:=y2-o2;

l:=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

ps:=abs(x1*y2-x2*y1);

if ps=0 then d:=0 else d:=ps/l;

if d>r+0.00001 then writeln(-1) else

if abs(d-r)<0.00001 then writeln(0) else

writeln(2*sqrt(r*r-d*d));

end.

PrimeNum

Задача. Даны три различных простых числа a, b, c. Найти N-е по счету число, представимое в виде a^m_*bⁿ_*c^k, где m,n,k - неотрицательные целые числа.

Технические условия. Вы вводите с клавиатуры через пробел числа a, b, c, N. Вы выводите на экран искомое число. Все числа в задаче принадлежат типу longint.

Пример

Ввод> 5 3 2 10

Вывод> 12

Решение №1. Просто генерируем все числа такого вида, не превышающие maxlongint, сортируем их и выводим n-е число.

Сложность: О(M*log(M)), где М - общее число чисел данного вида, не превышающих maxlongint

Решение №2. Сгенерировав массив, можно найти n-e по счету число за O(M) - для этого нужно несколько изменить алгоритм Quick Sort - когда мы разбили массив на две части (большие элементы и меньшие элементы), мы можем определить, в какой из частей оказался n-й элемент (по числу элементов в каждой из частей). Далее рекурсивно повторяем этот процесс для определенной нами части. Можно ожидать, что каждый раз массив разделится приблизительно пополам (для достаточно больших массивов это верно, однако, учитывая специфику данного массива, нужно обязательно организовать выбор случайного элемента для разделения надвое) в итоге мы пройдемся по logM массивам, каждый из которых примерно вдвое меньше предыдущего, значит, для нахождения n-го элемента понадобится O(M) операций.

Сложность: О(M)

Код программы на языке Паскаль:

{ NetOI-2005: Tour2: PrimeNum}

Program PRIMENUM;

var

pr:array[1..3]of longint;

prost,prost1:array[1..1700]of longint;

n,p1,p2,p3,i,nmax:longint;

procedure sliv(i_nc1,i_k1,i_k2:longint);

var i,j,k:longint;

procedure zan(var ind:longint);

begin

prost1[k]:=prost[ind];

inc(ind);

inc(k);

end;

begin

i:=i_nc1;j:=i_k1+1;k:=i_nc1;

while k<=i_k2 do

if i>i_k1 then zan(j) else

if j>I_k2 then zan(i) else

if prost[i]<prost[j] then zan(I) else

zan(J);

for k:=i_nc1 to i_k2 do prost[k]:=prost1[k];

end;

procedure ss(i_nach,i_kon:longint);

var r:longint;

begin

if i_kon > i_nach then

begin

r:=(i_nach+i_kon)div 2;

ss(i_nach,r);

ss(r+1,i_kon);

sliv(i_nach,r,i_kon);

end;

end;

procedure go2(n:longint);

begin

while n<=maxlongint div p3 do begin

inc(nmax);

prost[nmax]:=n;

n:=n*p3;

end;

inc(nmax);

prost[nmax]:=n;

n:=n*p3;

end;

procedure go1(n:longint);

begin

while n<=maxlongint div p2 do begin

go2(n);

n:=n*p2

end;

go2(n);

end;

procedure go(n:longint);

begin

while n<=maxlongint div p1 do begin

go1(n);

n:=n*p1

end;

go1(n);

end;

begin

read(p1,p2,p3,n);

nmax:=0;

go(1);

ss(1,nmax);

writeln(prost[n]);

end.

Country

Задача. На сельской улице в личных апартаментах живут лишь семьи Иваненков, Петренков и Сидоренков. Назначенный после помаранчевой революции председатель районной государственной администрации с целью упорядочения списка избирателей распорядился переселиться так, чтобы все Иваненки жили в начале улицы, все Петренки - в конце, а все Сидоренки - в середине. Найдите минимальное количество переселений, чтобы в каждом переселении участвовали не больше трех семей и чтобы каждая семья переезжала не более одного раза.

Технические условия. Вы вводите с клавиатуры количество семей N (1<=N<=50000), затем через пробел N чисел 1, 2 либо 3 (1 - Ивановы, 2 - Петровы, 3 - Сидоровы). Вы выводите на экран искомое количество переселений.

Пример

Ввод> 5 1 2 2 3 2

Вывод> 1

Решение. Считываем данные, запоминаем их в массив, далее подсчитываем количество Иваненков, Петренков и Сидоренков (k1, k2, k3). Разделяем улицу на три условные части - первая часть от дома №1 до дома №k1, вторая - от №k1+1 до №k1+k2 и третья от №k1+k2+1 №k1+k2+k3.

Потом считаем массив a[i,j] i=1..3, j=1..3, где a[i,j] означает сколько граждан с фамилией j проживает на части i. Обозначим за неправильность расстановки число, равное

A[1,2]+A[1,2]+A[2,1]+A[2,2]+A[3,1]+A[3,3]

Понятно, что в окончательной расстановке неправильность равна 0. Понятно, что если мы переселяем какого-нибудь из жителей в другой дом, то этот дом должен находиться на его участке (т.к. второй раз мы не сможем его переселить). Также можно заметить, что не имеет смысла делать переселения, при которых кто-нибудь из переселяемых остается на том же участке (тогда его можно было не переселять) Так как каждый житель может переселяться только 1 раз, то порядок переселений не важен (т.к. они не влияют друг на друга), значит, можно считать, что сначала делаются все тройные переселения. Легко видеть, что при тройном переселении неправильность изменяется на 3, а при двойном переселении - на 2. Значит, число тройных переселений должно быть максимальным. Это означает, что если есть возможность сделать тройное переселение, то мы должны делать его. Также при каждом двойном переселении неправильность уменьшается на 2, значит, если мы не можем делать тройные переселения, оставшееся число переселений будет равно (неправильность)/2. Осталось подсчитать максимальное число тройных переселений. Они бывают всего двух видов

...