Доставка пиццы
в городе открылось две пиццерии одной сети, которые занимаются доставкой пиццы на дом. в каждой пиццерии работает по одному курьеру, каждый из которых может доставлять одновременно только один заказ.
в сеть пиццерий поступило n заказов, каждый из заказов может быть выполнен в любой из пиццерий. для каждого заказа и каждой из двух пиццерий известно время, необходимое для доставки и возвращения курьера обратно в пиццерию. заказы могут выполняться в любом порядке. курьер может приступать к выполнению следующего заказа сразу после возвращения в пиццерию.
для каждого из заказов определите, какой из курьеров должен его доставлять чтобы последний из двух курьеров вернулся в пиццерию после выполнения всех своих заказов как можно раньше.
формат входных данных
в первой строке задаётся число n (1 ≤ n ≤ 1000) — количество заказов.
в каждой из следующих n строк идёт описание заказов, по одному в строке. в i-й из этих строк даны 2 числа ai и bi (1 ≤ ai, bi ≤ 100) — время необходимое для доставки и возвращения в пиццерию первого и второго курьера соответственно для выполнения i-го заказа.
формат результата
выведите n чисел 1 или 2, номер курьера, который будет выполнять соответствующий заказ.
если правильных ответов несколько — выведите любой из них.
примеры
входные данные
3
1 1
10 2
1 4
результат работы
1 2 1
задача1 чтобы подсчитать общее количество равновероятных событий (количество подъездов) воспользуемся формулой N=2^i вместо i подставим 2 и получим N=2^2, т.е. 4
ответ: в доме 4 подъезда
задача2 чтобы подсчитать общее количество равновероятных событий (количество ящиков) воспользуемся формулой N=2^i вместо i подставим 3 и получим N=2^3, т.е. 8
ответ: на склад поступило 8 ящиков
задача4 в тексте 61 символ. при использовании 256 -символьного алфавита, вес 1 символа составляет 8 бит
умножим 8 на 61 получим 488 бит
задача5
запишем условие: страниц=3, строк=60, символы=65, I=8775 байт, N=?
решение: выразим информационный объем текста в битах
I=8775*8=70200 бит
узнаем сколько всего символов в тексте
К=3*60*65=11700
теперь вычислим вес одного символа
i=I/K=70200/11700=6 бит
применим теперь формулу мощности алфавита:
N=2^i, N=2^6, N=64
const
n=1000; {максимальное количество цифр в числе}
type
big=record
v:array[1..n] of byte; {массив с цифрами числа}
m:integer {количество цифр в числе}
end;
function Str2Big(s:string):big;
{Переводит строковое представление в big}
var
i,n,k,err: integer;
r:big;
begin
n:=Length(s);
r.m:=n;
for i:=1 to n do
begin
Val(s[i],k,err);
r.v[i]:=k
end;
Str2big:=r
end;
function Big2Str(p:big):string;
{Переводит представление big в строковое}
var
i,n:integer;
c,s:string;
begin
s:='';
n:=p.m;
for i:=1 to n do
begin
Str(p.v[i],c);
s:=s+c
end;
Big2Str:=s
end;
function TruncBig(a:big):big;
{Усекает незначащие нули}
var
i,p,n:integer;
r:big;
begin
n:=a.m;
p:=0;
while (p<n) and (a.v[p+1]=0) do p:=p+1;
for i:=1 to n-p do r.v[i]:=a.v[i+p];
r.m:=n-p;
TruncBig:=r
end;
function MultBig(a,b:big):big;
{Возвращает произведение чисел типа big}
var
i,j,k,m,n,s:integer;
r:big;
begin
m:=a.m; n:=b.m;
for i:=m to m+n do r.v[i]:=0;
r.m:=m+n;
for j:=n downto 1 do
begin
if b.v[j]=0 then r.v[j+m+n-1]:=0
else begin
k:=0;
for i:=m downto 1 do
begin
s :=a.v[i]*b.v[j]+r.v[i + j]+k;
r.v[i+j]:=s mod 10;
k:=s div 10
end;
r.v[j] := k
end
end;
MultBig:=TruncBig(r);
end;
var
i:integer;
s:string;
bi,bs:big;
begin
bs:=Str2Big('1');
for i:=1 to 200 do begin
Str(i,s);
bi:=Str2Big(s);
bs:=MultBig(bs,bi);
end;
s:=Big2Str(bs);
Writeln(s)
end.
Результат
788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000