6. Длинная арифметика
Длинная арифметика позволяет производить точные вычисления с многоразрядными целыми числами без потери точности. Длинными будем называть целые числа, которые записываются в какой-либо системе счисления строкой из своих цифр. При выполнении арифметических операций удобно для выравнивания представлять числа от младших разрядов к старшим. Короткими будем считать числа, представленные стандартными целыми типами.
Ниже приводится простой вариант процедур и функций длинной арифметики [2]. Такой подход неэкономичен как по памяти, так и по скорости. Память используется неэффективно, так как для записи каждой цифры используется полный байт. Длина числа не хранится, а находится при вычислениях либо просто не используется, что снижает скорость. К тому же все вычисления производятся в десятичной системе счисления. В системах счисления с основанием 2 операции целочисленного деления и нахождения остатка можно свести к битовым операциям сдвигов, которые выполняются быстрее. Тем не менее, приводимый вариант реализации длинной арифметики пригоден для большинства практических задач и прост в применении. Более полное описание проблем, связанных с длинной арифметикой, можно найти в [3].
Const
numlen = <максимальное количество знаков в длинных числах>;
{ для параметров циклов используются переменные integer,
если numlen>MaxInt, нужно использовать переменные типа word }
Type
number=array[1..numlen] of byte;
{ длинное число от младших разрядов к старшим;
переменной A типа number представлено число SUM(a[i]*10^(i-1))}
Procedure Set0(var n:number); {обнуление длинного числа}
Var
i: integer;
Begin
For i:=1 to numlen do
n[i]:=0;
End;
Procedure SetN(Var n: number; short: integer);
{занесение короткого числа в длинное}
Var
i: integer;
Begin
Set0(n); i:=1;
While short>0 do
begin
n[i]:=short mod 10;
short:=short div 10;
i:=i+1;
end;
End;
Procedure Move(n1:number; Var n2:number);
{пересылка длинного числа n2:=n1}
Var
i: integer;
Begin
For i:=1 to numlen do
n2[i]:=n1[i];
End;
Function Len(var n:number): integer;
{получение длины числа, для нуля длина 1 }
Var
i: integer;
Begin
For i:=numlen downto 1 do
if n[i]<>0 then
begin
Len:=i;
Exit;
end;
Len:=1;
End;
Procedure Show(var n:number);
{вывод числа и перевод строки }
Var
i: integer;
Begin
For i:=Len(n) downto 1 do
Write(n[i]);
WriteLn;
End;
Procedure AddShort(Var n: number; short: integer);
{прибавление короткого числа}
Var
i: integer;
Begin
i:=1;
While short>0 do
begin
short:=short+n[i];
n[i]:=short mod 10;
short:=short div 10;
i:=i+1;
end;
End;
Procedure MulShort(Var n: number; short: integer);
{умножение на короткое число}
Var
i, carry: integer;
Begin
carry:=0;
For i:=1 to numlen do
begin
carry:=carry+n[i]*short;
n[i]:=carry mod 10;
carry:=carry div 10;
end;
if carry<>0 then {диагностика переполнения}
Halt(1);
End;
Procedure DivShort(Var n: number; divisor: integer; Var rem: integer);
{деление на короткое число и получение остатка}
Var
i: integer;
Begin
rem:=0;
For i:=numlen downto 1 do
begin
rem:=rem*10+n[i];
n[i]:=rem div divisor;
rem:=rem mod divisor;
end;
End;
Procedure Add(Var n1,n2: number);
{прибавление длинного числа}
Var
i, carry: integer;
Begin
carry:=0;
For i:=1 to numlen do
begin
carry:=carry+n1[i]+n2[i];
n1[i]:=carry mod 10;
carry:=carry div 10;
end;
if carry<>0 then {диагностика переполнения}
Halt(1);
End;
Procedure Mul(Var n1,n2: number; Var n3: number);
{умножение длинных чисел}
Var
i1,i2,i3,len1,len2,carry: integer;
Begin
Set0(n3);
len1:=Len(n1);
len2:=Len(n2);
For i1:=1 to len1 do
For i2:=1 to len2 do
begin
i3:=i1+i2-1;
carry:=n1[i1]*n2[i2];
While carry>0 do
begin
carry:=carry+n3[i3];
n3[i3]:=carry mod 10;
carry:=carry div 10;
inc(i3);
end;
end;
End;
Function Cmp(Var n1,n2: number): integer;
{ сравнение чисел:
если n1<n2 выдает -1
если n1=n2 выдает 0
если n1>n2 выдает 1
}
Var
i: integer;
Begin
For i:=numlen downto 1 do
begin
if n1[i]<n2[i] then
begin
Cmp:=-1;
Exit;
end;
if n1[i]>n2[i] then
begin
Cmp:=1;
Exit;
end;
end
Cmp:=0;
End;
Рассмотрим для примера задачу, связанную с применением длинной арифметики.
Маг. Имеется N супружеских пар. Маг должен определить, кто кому супруг. Какова вероятность угадать ровно K раз из N?
Ввод из файла INPUT. TXT. В первой строке задаются через пробел K и N (1 ≤ N ≤ 100, 0 ≤ K ≤ N).
Вывод в файл OUTPUT. TXT вероятности угадать ровно K раз из N в виде несократимой дроби либо единственного значения 0.
Примеры
Ввод 1 Ввод 2
2 5 9 10
Вывод 1 Вывод 2
1/6 0
Пронумеруем, например, мужчин от 1 до N. Сейчас нужно найти вероятность такого расположения женщин в позициях от 1 до N, чтобы ровно K из них соответствовали позиции своего мужа.
Пусть D(N) – функция, определяющая количество перестановок из N элементов 1, 2, …, N, в которых ни один из элементов не остается на своем месте. Такие перестановки называются беспорядками. Тогда ответ задачи определяет выражение
PNK = (CNK × D(N-K)) / N! = D(N-K)) / K! (N-K)! (1)
Действительно, для каждого набора из K элементов, остающихся на своих местах, существуют D(N-K) перестановок остальных элементов, а общее число перестановок N! Остается найти способ вычисления функции D(N).
Очевидно, что D(1) = 0, D(2) = 1, D(3)=2 - перестановки (2, 3, 1) и (3, 1, 2).
При N = 4 существуют 9 перестановок с элементами не на своих местах:
(2, 1, 4, 3), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3),
(4, 3, 1, 2), (4, 3, 2, 1), т. е. D(4)=9.
Поясним приведенную в [1] без доказательства рекуррентную формулу
D(N+1) = N × (D(N) + D(N-1)) (2)
Пусть имеется перестановка (S1, S2, …, SN) со всеми элементами не на своих местах. При любом 1 ≤ K ≤ N можно образовать перестановку (S1, S2, Sk-1, N+1, Sk+1, …, SN, Sk) из N+1 элемента, в которой все элементы находятся не на своих местах. Например, при N = 4 из перестановки (2, 1, 4, 3) образуются перестановки (5, 1, 4, 3, 2), (2, 5, 4, 3, 1), (2, 1, 5, 3, 4), (2, 1, 4, 5, 3). Количество полученных перестановок составляет N ×(D(N).
С другой стороны, из любой перестановки (S1, S2, …, SN-1) порядка N-1 с элементами не на своих местах можно образовать N перестановок вида (S1, S2, Sk-1, N+1, Sk+1, …, …, Sk, N) порядка N+1, в которых элементы также не на своих местах. Например, при N = 4 из перестановки (2, 3, 1) образуются перестановки (2, 3, 1, 5, 4), (2, 3, 5, 1, 4), (2, 5, 1, 3, 4), (5, 3, 1, 2, 4).
Суммирование по обоим вариантам дает рекуррентную формулу (2). В соответствии с ней, например, D(5) = 44.
Можно получить более очевидное, но и более сложное по форме соотношение для D(N+1). Всего имеется (N+1)! перестановок из N+1 элементов. Число перестановок с единственным элементом на своем месте составляет CN+11 × D(N), с двумя на своих местах CN+12 × D(N-1) и т. д. Ровно N элементов на своих местах быть не может, так как и последний элемент в этом случае на своем месте. Вычитая из общего числа перестановок количество случаев, когда хотя бы один элемент находится на своем месте, получим формулу
D(N+1)= (N+1)! - CN+11 × D(N) - CN+12 × D(N-1) -…- CN+1N-1 × D(2) – 1
Единица соответствует случаю, когда все элементы на своих местах.
Примеры:
N=4, K=1. Тогда S = CNK × D(N-K) = 4×2 = 8, PNK = 8 / 4! = 1 / 3 N=4, K=2, S = 6×1 = 6, PNK = 6/24 = 1 / 4 N=5, K=2, S = 10×2 = 20, PNK = 20 / 120 = 1 / 6 (пример из условия) N=6, K=2, S = 15×9 = 135, PNK = 135 / 6! = 135 / 720 = 3 / 16 N=10, K=9, S = C109 × D(1) =10×0 = 0, PNK = 0Для нахождения D(N-K) в формуле (1) будем использовать процедуры длинной арифметики. Каждое длинное число представим последовательностью байтов, содержащих его десятичные цифры от младших разрядов к старшим. Потребуются такие процедуры как преобразование короткого числа типа INTEGER в длинное, сложение длинных чисел, умножение короткого числа на длинное и т. п.
Для сокращения числителя и знаменателя представим знаменатель как массив сомножителей с кратностью каждого из них не более 2. Найденный числитель будем пытаться поделить нацело на каждый из сомножителей в порядке убывания их величины с учетом кратности сомножителей. Для этого потребуется процедура деления длинного числа на короткое.
Наконец, на заключительном этапе нужно найти произведение тех сомножителей знаменателя, которые не были сокращены.
По заданным ограничениям все числа не превосходят 100100, поэтому для представления любого длинного числа потребуется не более 200 байтов.
Приведем текст программы. Процедуры и функции длинной арифметики используются без изменений, поэтому в тексте содержатся только их заголовки.
Program Mag;
Const
numlen = 200; {число разрядов длинного числа - с запасом}
Label
Konec;
Type
number=array[1..numlen] of byte;
Var
M, N,K, L,i, j,jj : integer;
Min, Max: integer;
d1,d2,d3: number;
Num: array[1..100] of integer;
{кратность сомножителей знаменателя}
Fin, Fout: text;
Procedure Set0(var n:number); {обнуление длинного числа}
Procedure SetN(Var n: number; short: integer);
{занесение короткого числа в длинное}
Function Len(var n:number): integer;
{получение длины числа, для нуля длина 1}
Procedure Show(var n:number);
{вывод числа в файл Fout}
Procedure MulShort(Var n: number; short: integer);
{умножение длинного числа на короткое}
Procedure DivShort(Var n: number; divisor: integer;
Var rem: integer);
{деление длинного числа на короткое и получение остатка}
Procedure Add(Var n1,n2: number);
{сложение длинных чисел}
Procedure Move(n1:number; Var n2:number);
{пересылка длинного числа - n2:=n1}
Begin {основная программа}
Assign(Fin,'input. txt');
Reset(Fin);
ReadLn(Fin, K,N);
Close(Fin);
Set0(d1); { d1:=0 }
SetN(d2,1); { d2:=1 }
L:=N-K;
Assign(Fout,'output. txt');
Rewrite(Fout);
if L=1 then
begin
WriteLn(Fout,'0');
Goto Konec;
end;
{нахождение числителя d3}
if (L=0) or (L=2) then SetN(d3,1); { d3:=1 }
For i:=3 to L do
begin
Add(d1,d2); { d1:=d1+d2 }
Move(d1,d3); { d3:=d1 }
MulShort(d3,i-1);
Move(d2,d1); { d1:=d2 }
Move(d3,d2); { d2:=d3 - следующий шаг }
end;
if L<K then
begin
Min:=L;
Max:=K;
end
else
begin
Min:=K;
Max:=L;
end;
For i:=1 to Min do Num[i]:=2;
{кратность сомножителей знаменателя,
в K! и (N-K)! начальные сомножители повторяются}
For i:=Min+1 to Max do Num[i]:=1;
For i:=Max downto 2 do {проверка: можно ли сократить на i}
begin
jj:=Num[i]; {сомножитель i в знаменателе N[i] раз}
For j:=1 to jj do
begin
Move(d3,d1); {d1:=d3}
DivShort(d1,i, M); {M-остаток}
if M=0 then
begin
Num[i]:=Num[i]-1;
Move(d1,d3); {сокращение на i}
end
else break; {нет сокращения - выход из цикла по j}
end;
end;
SetN(d2,1);
{нахождение знаменателя d2 после сокращения}
For i:=2 to Max do
For j:=1 to Num[i] do
MulShort(d2,i);
Show(d3); {вывод в файл d3}
Write(Fout,'/');
Show(d2);
Konec:
Close(Fout);
End.
В качестве упражнений можно порекомендовать довести до конца при максимальных размерностях решение приведенных выше задач, которые требуют применения длинной арифметики. Полезно также переработать процедуры длинной арифметики на язык Си и протестировать их на небольших комбинаторных задачах.
Задачи для самостоятельного решения
6.1. Длинная разность (4)
Заданы два целых положительных числа. Требуется найти их разность.
Ввод. В первых двух строках файла INPUT. TXT содержатся два целых числа M и N (1 ≤ N < M ≤ 10200).
Вывод. В единственной строке выходного файла OUTPUT. TXT необходимо вывести разность M – N.
Примеры
Ввод 1 Ввод 2
123456787654321 1000000000000000
35 1
Вывод 1 Вывод 2
123456787654286 999999999999999
6.2. Длинное деление (7)
Заданы два целых положительных числа. Требуется найти их частное и остаток от деления.
Ввод. В первой строке файла INPUT. TXT задано делимое, во второй – делитель. Количество цифр делимого и делителя от 1 до 100.
Вывод. В первой строке файла OUTPUT. TXT вывести частное, во второй строке - остаток.
Примеры
Ввод
4 2
3456
47
Вывод
73
25
7. Метод сканирующей прямой
Рассмотрим следующую задачу.
Закраска прямой. На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти длину окрашенной части числовой прямой.
Ограничения: Li и R i - целые, -1000 ≤ Li ≤ Ri ≤ 1000, 1 ≤ N ≤ 1000.
Ввод. В первой строке файла INPUT. TXT. находится число N, в следующих N строках - пары Li и R i.
Вывод. Вывести в файл OUTPUT. TXT одно число – длину окрашенной части прямой.
Примеры
Ввод 1 Ввод 2
2 1
1 3 10 10
2 4
Вывод 1 Вывод 2
3 0
Отсортируем концы отрезков по возрастанию. Будем просматривать отсортированный массив слева направо, прибавляя к счетчику 1 в случае начала отрезка, и вычитая 1 для конца отрезка. Если счетчик получает значение 1 в начале очередного отрезка, запомним соответствующее значение координаты L. Если счетчик становится равным 0 в некотором конце отрезка с координатой R, то очередное объединение отрезков закончилось, и точки до следующего начала отрезка не принадлежат ни одному отрезку. Прибавляем величину R-L к общей длине окрашенной части.
Приведем текст программы для решения этой задачи.
Program PaintX;
Const
Max=2000;
Type
Segm=record
X: integer; {координата}
Vid: integer; {1-левый конец, -1-правый}
end;
Var
M, N,i, j,K, L: integer;
Lp: longint; {общая длина окрашенной части прямой}
S: array [1..Max] of Segm;
Fin, Fout: text;
Procedure Sort; {сортировка на месте}
Var
i, j: integer;
B: Segm;
Begin
For i:=2 to K do
For j:=K downto i do { пузырек }
if (S[j].X<S[j-1].X) then
begin
B:=S[j];
S[j]:=S[j-1];
S[j-1]:=B;
end;
End;
Begin
Assign(Fin,'input. txt');
Reset(Fin);
ReadLn(Fin, N);
K:=0; {число концов}
For i:=1 to N do
begin
K:=K+2;
ReadLn(Fin, S[K-1].X, S[K].X);
S[K-1].Vid:=1; {признак левого конца}
S[K].Vid:=-1; {признак правого конца}
end;
Close(Fin);
Sort;
Lp:=0; {общая длина окрашенной части прямой}
M:=0; {количество отрезков, содержащих текущую координату}
For i:=1 to K do
begin
M:=M+S[i].Vid;
if (M = 1) and (S[i].Vid = 1) then L:=S[i].X;
if (M = 0) and (S[i].Vid = -1) then Lp:=Lp+S[i].X-L;
end;
Assign(Fout,'output. txt');
Rewrite(Fout);
Write(Fout, Lp);
Close(Fout);
End.
При увеличении размерности необходимо использовать один из вариантов быстрой сортировки.
В рассмотренной задаче мы продвигаемся по числовой прямой, обрабатывая два вида событий: начало и конец какого-либо отрезка. Между точками событий принципиально ничего не изменяется.
Подобный подход называют методом сканирующей прямой (скользящей прямой, заметания, выметания, sweeping) [3]. Обычно он включает в себя следующие этапы:
- выделение точек событий; сортировка точек событий; последовательное продвижение по точкам событий с обработкой точек в зависимости от вида событий.
В нашей задаче всего два вида событий, но их может быть и больше. Приведем пример более сложной задачи на заметание.
Волки и овцы. На координатной плоскости заданы отрезками N волков и M овец. Пастух с ружьем находится в начале координат. Выстрел поражает всех животных по направлению полета пули. Найти наименьшее число выстрелов для того, чтобы убить всех волков и не тронуть овец.
Ввод из файла INPUT. TXT. В первой строке задаются через пробел значения N и M (1 ≤ N, M ≤ 103). В следующих N строках - целочисленные координаты начала (X1, Y1) и конца (X2, Y2) отрезка, соответствующего волку (-1000 ≤ X1, X2 ≤ 1000; 1 ≤Y1, Y2 ≤ 1000). Аналогично в следующих M строках указывается положение овец.
Вывод в файл OUTPUT. TXT единственного целого числа либо сообщения “No solution”.
Пример
Ввод
2 1
1 1 2 3
-5 4 2 2
999 1000 1000 9993
Вывод
2
Каждое животное определяет сектор своего нахождения. Как начало, так и конец любого отрезка находятся в пределах интервала углов (0, р). Поставим в соответствие сектору нахождения животного отрезок, определяемый котангенсами координат начала и конца того отрезка, который задает положение животного. Поменяем при необходимости начало и конец отрезка котангенсов так, чтобы левая граница отрезка не превосходила правую. При заданных ограничениях все отрезки котангенсов окажутся в пределах [-1000; 1000]. Такое соответствие позволяет вместо отрезков на плоскости рассматривать отрезки котангенсов на числовой прямой.
Сформируем из исходных данных массив записей размерности (N+M)×2, в котором будем хранить информацию о началах и концах отрезков котангенсов. Структура записи в терминах языка Паскаль:
Type
Point=record
X: real; {координата в пределах [-1000; 1000]}
Vid: char; {‘[’ для левого конца и ‘]’ для правого}
Pr: char; {‘w’-волк, ’s’-овца}
Ind: integer; {индекс в массиве парной скобки}
End;
Отсортируем массив по возрастанию координат. При равных координатах выберем следующий порядок расположения в массиве:
- начало отрезка для овцы; начало отрезка для волка; конец отрезка для волка; конец отрезка для овцы.
При сортировке будем корректировать значения переменной Ind в соответствии с изменениями индексов элементов в массиве.
Будем просматривать массив слева направо, то есть по возрастанию координат концов отрезков котангенсов. Чтобы отследить, находится ли текущая точка в секторе нахождения какой-либо овцы, будем поддерживать счетчик числа овец, поражаемых при текущем направлении выстрела. Сначала этот счетчик инициализируется нулем. Рассмотрим следующие случаи:
Элемент массива соответствует началу отрезка котангенсов для овцы. Если счетчик числа овец равен нулю, то запомним в переменной L индекс этого элемента. Пусть R – точка отрезка котангенсов для этого элемента. Увеличим на 1 счетчик числа овец. Элемент массива соответствует концу отрезка котангенсов овцы. Уменьшим на 1 счетчик числа овец. Элемент массива соответствует началу отрезка котангенсов для волка. Ничего не делаем. Чем больше волков в направлении выстрела, тем лучше. Элемент массива соответствует концу отрезка котангенсов для волка. Счетчик числа овец равен нулю. Чтобы волк не остался цел, необходим выстрел в направлении, соответствующем найденному концу отрезка. При этом будут убиты все волки, находящиеся на этом направлении. Нужно просмотреть массив назад, найти начала отрезков для волков и убрать из массива (пометить специальным признаком) концы этих отрезков. Для упрощения этой процедуры можно использовать счетчик числа волков в текущем направлении выстрела. К счетчику числа выстрелов прибавим 1. Счетчик числа овец больше нуля. Чтобы текущий волк был убит, необходимо произвести выстрел в том направлении, при котором волк поражается, но ни одна овца не затрагивается. В качестве такого значения по отрезкам котангенсов можно взять R-е. Обработаем такой выстрел аналогично предыдущему случаю. Если же начало отрезка для данного волка не меньше R, то решение невозможно, т. к. этот волк не может быть убит без поражения овец.Таким образом просмотрим весь массив. Если не возникнет ситуаций, когда какой-либо волк не может быть убит, то счетчик числа выстрелов даст необходимый ответ.
Задачи для самостоятельного решения
7.1. Отрезки (6)
На числовой прямой задано N отрезков, пронумерованных в порядке их ввода, начиная с 1. Отрезки могут пересекаться. Отрезок называется простым, если в нем не содержится целиком никакой другой. Найдите все простые отрезки из заданного набора.
Ввод из файла INPUT. TXT. В первой строке записано число N (1 ≤ N ≤ 106). В следующих N строках заданы целочисленные координаты левого и правого концов отрезка ai, bi (-109 ≤ ai, bi ≤ 109).
Вывод. В первую строка файла OUTPUT. TXT вывести количество простых отрезков. Во вторую – в порядке возрастания последовательность номеров простых отрезков. Если простых отрезков нет, в единственной строке вывести 0.
Ограничения: время 1 с.
Примеры
Ввод 1 Ввод 2
3 3
1 10 5 10
3 3 5 10
10 20 8 100
Вывод 1 Вывод 2
2 1
2 3 3
7.2. Ремонт дорог (4)
После схода с рельсов нескольких поездов, следовавших из пункта A в пункт B, решено отремонтировать железную дорогу. Для выявления дефектных участков дороги привлекли N независимых экспертов (1 ≤ N ≤ 105). Каждый эксперт назвал один участок дороги для ремонта в виде отрезка. Оказалось, что названные отрезки могут пересекаться и лежать один внутри другого. Ввиду нехватки средств, постановили отремонтировать только те части дороги, которые находятся не менее чем в M отрезках (1 ≤ M ≤ 10, M ≤ N).
Одна ремонтная бригада принимает заказ на ремонт в виде единственного участка дороги, заданного отрезком. Найти минимальное количество бригад для ремонта. Напоминаем, что концы отрезка считаются принадлежащими ему.
Ввод из файла INPUT. TXT. Первая строка содержит количество экспертов N и значение M через пробел. В следующих N строках задаются сами отрезки в виде двух целых чисел X и Y через пробел (0 ≤ X ≤ Y ≤ 109).
Вывод в файл OUTPUT. TXT в виде единственного целого числа.
Пример
Ввод
4 2
2 5
8 10
4 6
3 9
Вывод
2
7.3. Прямоугольники (6)
На координатной плоскости задано N прямоугольников со сторонами, параллельными координатным осям. Найти площадь фигуры, получающейся в результате объединения прямоугольников.
Ввод из файла INPUT. TXT. В первой строке содержится значение N (1 ≤ N ≤ 300). В каждой из следующих N строк – четыре целых числа Ai, Bi, Ci, Di через пробел, определяющие координаты левого верхнего и правого нижнего углов очередного прямоугольника (-1000 ≤ Ai, Bi, Ci, Di ≤ 1000).
Вывод в файл OUTPUT. TXT единственного целого числа – площади фигуры.
Пример
Ввод
2
5 15 25 5
0 10 20 0
Вывод
325
7.4. Муравьи (6)
Юный натуралист Билл изучает муравьев. Его муравьи питаются исключительно яблоками, растущими на диких яблонях. Имеется карта с координатами N муравейников и N яблонь. Муравьи из каждого муравейника добираются до яблони кратчайшим путем по прямой. Требуется так распределить яблони между муравейниками, чтобы
- у каждого муравейника была единственная яблоня; каждая яблоня принадлежала только одному муравейнику; пути муравьев из разных муравейников к своим яблоням не пересекались.
Ввод из файла INPUT. TXT. Первая строка единственное целое число N (1 ≤ N ≤ 100). Далее в N строках заданы через пробел координаты Xi, Yi (-10000 ≤ Xi, Yi ≤ 10000) муравейников. В последующих N строках заданы координаты яблонь. Никакие три точки не лежат на одной прямой.
Вывод в файл OUTPUT. TXT состоит из N строк по одному целому числу в строке. Число в i-й строке определяет номер яблони, предназначенной для i-го муравейника.
Пример
Ввод
5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60
Вывод
4
2
1
5
3
Подсказка. Перенести начало координат в самую левую точку из самых нижних. Отсортировать точки по полярному углу. Методом заметания по возрастанию угла найти такую точку, что по каждую сторону от прямой, соединяющей новое начало координат с этой точкой, окажется одинаковое количество муравейников и яблонь. Далее применить эту же процедуру (можно с использованием рекурсии) к точкам по каждую сторону от прямой.
7.5. Волки и овцы (7)
Написать программу для задачи ”Волки и овцы”, сформулированной в настоящем разделе.
7.6. Светофоры (8)
Главная улица столицы Берландии имеет длину s. Вдоль нее установлены светофоры, меняющие свет от красного к зеленому и наоборот. Каждый светофор описывается 4 числами xi, ri, gi, di, где
- xi – расстояние от начала улицы до светофора (1 ≤ xi ≤ s-1); ri – продолжительность красного света (10 ≤ ri ≤ 20); gi – продолжительность зеленого света (10 ≤ ri ≤ 20); di – минимальный неотрицательный момент времени, когда свет меняется от зеленого к красному (0 ≤ ri < ri + gi).
Каждый светофор с давнего времени работает в своем цикле постоянно.
Король проезжает по всей улице с постоянной скоростью v0 (vmin ≤ v ≤ vmax). Чтобы не останавливать его движение, часть светофоров может быть переключена на постоянный зеленый свет. Найти такое значение v0, при котором число переключаемых светофоров минимально. Если таких значений больше одного, выберите из них максимальное.
Ввод. В первой строке находятся числа n, s, vmin и vmax (1 ≤ n < 20000, 1 ≤ s ≤ 20000, 10 ≤ vmin ≤ v ≤ vmax ≤ 50), где n – число светофоров, S – длина улицы в метрах, vmin и vmax – минимальная и максимальная скорости в метрах в секунду. В следующих n строках описываются светофоры. Каждое описание состоит из 4 целых чисел xi, ri, gi, di. Величины ri, gi, di даны в секундах, а xi – в метрах. Никакие два светофора не находятся в одной точке.
Вывод. В первой строке выводится v0 с точностью 10 знаков после десятичной точки. Во второй строке выводится число «вечно зеленых» светофоров для скорости v0. Третья строка в случае присутствия таких светофоров должна содержать их номера в любом порядке.
Примеры
Ввод 1 Ввод 2 Ввод 3
3 1000 10 30 2 1000 10 30 4 1000 10 30
500 10 10 10 500 10 10 10 800 10 15 20
501 10 10 0 600 10 20 2 500 20 10 15
600 10 10 0 501 20 10 5
600 10 20 15
Вывод 1 Вывод 2 Вывод 3
16.70000000000 25.00000000000 20.04000000000
0 0 1
2
Подсказка. Выделить из отрезка времени возможного прохождения i-го светофора [xi / vmax, xi / vmin] те подотрезки, когда он горит зеленым светом. Далее перевести в шкалу скоростей все выделенные подотрезки и объединить их по всем светофорам. На отрезке скоростей [vmin, vmax] отсортировать концы полученных подотрезков и применить метод сканирующей прямой.
7.7. Межрегиональная олимпиада (7)
На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая i-я задача (1 ≤ i ≤ n) становится доступной участникам в свой момент времени si. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть ti минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение i-й задачи участник получает ci баллов.
Артур, представляющий на межрегиональной олимпиаде один из региональных центров искусственного интеллекта, понимает, что важную роль на такой олимпиаде играет не только умение решать задачи, но и правильный стратегический расчет того, какие задачи надо решать, а какие пропустить. Ему, как и всем участникам, до начала тура известно, в какой момент времени каждая задача станет доступной, сколько времени будет отведено на ее решение и сколько баллов можно получить за ее решение. Артур является талантливым школьником и поэтому сможет успешно решить за отведенное время и сдать на проверку любую задачу, которую он выберет для решения на олимпиаде.
Требуется написать программу, которая определяет, какое максимальное количество баллов Артур сможет получить при оптимальном выборе задач, которые он будет решать, а также количество и перечень таких задач.
Ввод. Первая строка входного файла содержит одно целое число n (1 ≤ n ≤ 100 000) ‑ количество задач на олимпиаде. Последующие n строк содержат описания задач, по три числа на каждой строке: si ‑ момент появления i-й задачи в минутах, ti ‑ время, отведенное на ее решение в минутах, ci ‑ сколько баллов получит участник за решение этой задачи (1 ≤ si, ti, ci ≤ 109).
Примеры
Ввод 1 Ввод 2
2 3
1 1 1 1 2 1
2 2 2 3 2 1
2 4 3
Вывод 1 Вывод 2
3 3
2 1
1 2 3
Пояснения. В первом примере Артур успевает решить все задачи и получить три балла. Во втором примере Артуру выгоднее решать последнюю задачу и получить за нее три балла, чем решать только первые две и получить два балла.
