Университет ИТМО Сакт-петербурга (olymp.ifmo.ru) ежегодно проводит перечневую олимпиаду по информатике первого уровня. Задачи олимпиады напоминают задания ЕГЭ. Мы предлагаем Вам попробовать решить на пробном туре вариацию одной задачи с олимпиады СПБГУ ИТМО 2015 года. Пете подарили n гирь и чашечные весы. Каждая гиря весит ai грамм. Первым делом он разложил гири на чаши. При этом одна из чаш может быть пустой. Теперь он хочет выяснить, какой наименьшей разницы весов на чашах можно достичь, не более чем за одно перекладывание гирь. Одно перекладывание происходит следующим образом: Петя выбирает некоторую гирю, лежащую на одной чаше весов и перекладывает ее на другую чашу весов. Обратите внимание, что Петя не обязан сделать это перекладывание.

Формат ввода
В первой строке входного файла weight.in находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирь. В каждой из следующих n строк находятся два натуральных числа ai, bi (1 ≤ ai ≤ 1000, 1 ≤ bi ≤ 2) — масса гири и номер чаши весов, на которой она находится.

Формат вывода
В выходной файл weight.out требуется вывести одно число — наименьшую разницу весов, которую можно достичь, сделав не более одного перекладывания гирь.

Основа взята на сайте progmatem.ru. К сожалению, автор статьи там не был указан.

// PascalABC.NET 3.1, сборка 1204 от 24.03.2016
uses graphABC;
const
  w=1000;
  h=600;

function f(x:real):=0.5*x*cos(2*x);

begin
  SetWindowSize(w,h);
  // поле для графика в окне
  var xLeft:=50;
  var yLeft:=50;
  var xRight:=w-xLeft;
  var yRight:=h-yLeft;
  // интервалы по осям
  var ax:=-12.0;
  var bx:=12.0;
  var hx:=1.0;
  var ay:=-6.5; // минимум f(x) с запасом
  var by:=6.5;
  var hy:=0.5;
  // масштабы по осям
  var mx:=(xRight-xLeft)/(bx-ax);
  var my:=(yRight-yLeft)/(by-ay);
  // точка начала координат графика
  var x0:=xLeft+Trunc(abs(ax)*mx);
  var y0:=yRight-Trunc(abs(ay)*my);
  // рисование координатных осей
  Line(xLeft,y0,xRight+10,y0);
  Line(x0,yLeft-10,x0,yRight);
  SetFontSize(12); SetFontColor(clBlue);
  TextOut(xRight+15,y0-10,'X');
  TextOut(x0-4,yLeft-30,'Y');
  SetFontSize(8); SetFontColor(clGreen);
  // рисование засечек
  var s:string;
  for var i:=1 to Round((bx-ax)/hx)+1 do begin
    var num:=ax+(i-1)*hx;
    var x:=xLeft+Trunc(mx*(num-ax));
    Line(x,y0-3,x,y0+3);
    Str(num,s);
    if abs(num)>1E-15 then TextOut(x-TextWidth(s) div 2,y0+10,s)
    end;
  for var i:=1 to Round((by-ay)/hy)+1 do begin
    var num:=ay+(i-1)*hy;
    var y:=yRight-Trunc(my*(num-ay));
    Line(x0-3,y,x0+3,y);
    Str(num,s);
    if abs(num)>1E-15 then TextOut(x0+7,y-TextHeight(s) div 2,s)
    end;
    TextOut(x0-10,y0+10,'0');
  // собственно график
  var xi:=ax;
  while xi<=bx do begin
    var yi:=f(xi);
    var x:=x0+Round(xi*mx);
    var y:=y0-Round(yi*my);
    if (y>=yLeft) and (y<=yRight) then SetPixel(x,y,clRed);
    xi+=1e-3
    end
end.

*******************************************
// PascalABC.NET 3.1, сборка 1204 от 24.03.2016
uses graphABC;
const
  w=1000;
  h=600;

function f(x:real):=8*sin(x)*sin(2*x);

begin
  SetWindowSize(w,h);
  // поле для графика в окне
  var xLeft:=50;
  var yLeft:=50;
  var xRight:=w-xLeft;
  var yRight:=h-yLeft;
  // интервалы по осям
  var ax:=-15.0;
  var bx:=15.0;
  var hx:=1.0;
  var ay:=-6.5; // минимум f(x) с запасом
  var by:=6.5;
  var hy:=0.5;
  // масштабы по осям
  var mx:=(xRight-xLeft)/(bx-ax);
  var my:=(yRight-yLeft)/(by-ay);
  // точка начала координат графика
  var x0:=xLeft+Trunc(abs(ax)*mx);
  var y0:=yRight-Trunc(abs(ay)*my);
  // рисование координатных осей
  Line(xLeft,y0,xRight+10,y0);
  Line(x0,yLeft-10,x0,yRight);
  SetFontSize(12); SetFontColor(clBlue);
  TextOut(xRight+15,y0-10,'X');
  TextOut(x0-4,yLeft-30,'Y');
  SetFontSize(8); SetFontColor(clGreen);
  // рисование засечек
  var s:string;
  for var i:=1 to Round((bx-ax)/hx)+1 do begin
    var num:=ax+(i-1)*hx;
    var x:=xLeft+Trunc(mx*(num-ax));
    Line(x,y0-3,x,y0+3);
    Str(num,s);
    if abs(num)>1E-15 then TextOut(x-TextWidth(s) div 2,y0+10,s)
    end;
  for var i:=1 to Round((by-ay)/hy)+1 do begin
    var num:=ay+(i-1)*hy;
    var y:=yRight-Trunc(my*(num-ay));
    Line(x0-3,y,x0+3,y);
    Str(num,s);
    if abs(num)>1E-15 then TextOut(x0+7,y-TextHeight(s) div 2,s)
    end;
    TextOut(x0-10,y0+10,'0');
  // собственно график
  var xi:=ax;
  while xi<=bx do begin
    var yi:=f(xi);
    var x:=x0+Round(xi*mx);
    var y:=y0-Round(yi*my);
    if (y>=yLeft) and (y<=yRight) then SetPixel(x,y,clRed);
    xi+=1e-3
    end
end.

Const n=20;
var 
a,b:array[1..n] of integer;
i,j,k,m,c:integer; 
begin
Randomize;
writeln('Исходный массив:');
for i:=1 to n do
 begin
  a[i]:=random(51)-25;
  write(a[i]:5);
 end;
writeln;
j:=0;
for i:=1 to n do
 if a[i]<0 then begin j:=j+1; b[j]:=a[i]; end;
m:=j;
for k := 1 to m-1 do
  for i := 1 to m-k do
     if (b[i]<b[i+1]) then 
       begin
       c:=b[i]; b[i]:=b[i+1]; b[i+1]:=c;
       end;
writeln('Вс массив:');
for i:=1 to m do write(b[i]:5);
writeln;
j:=0;
for i:=1 to n do
 if a[i]<0 then begin j:=j+1; a[i]:=b[j]; end;
writeln('Полученный массив:');
for i:=1 to n do write(a[i]:5);
writeln;
end.

Пример:
Исходный массив:
  -15   -8   -6  -13   15   24    5   -2   14   -1   19   -2   -7   -8  -23   20   -2    7   -2  -10
Вс массив:
   -1   -2   -2   -2   -2   -6   -7   -8   -8  -10  -13  -15  -23
Полученный массив:
   -1   -2   -2   -2   15   24    5   -2   14   -6   19   -7   -8   -8  -10   20  -13    7  -15  -23