NKSGAME - VOI08 Trò chơi với dãy số

Tác giả: ll931110

Ngôn ngữ: Pascal

Program NKSGAME;
        Const
                input  = '';
                output = '';
        Type
                arr = array[0..10000000] of longint;
        Var
                b,c: arr;
                  n: longint;

Procedure init;
          Var
                f: text;
                i: longint;
          Begin
                Assign(f, input);
                        Reset(f);
                        Readln(f, n);
                        For i:= 1 to n do read(f, b[i]);
                        For i:= 1 to n do read(f, c[i]);
                Close(f);
          End;

Procedure q1;

          Procedure partition(l,h: longint);
                    Var
                        i,j,p,x: longint;
                    Begin
                        If l >= h then exit;
                        p:= b[random(h - l + 1) + l];

                        i:= l;          j:= h;

                        Repeat
                                While b[i] < p do inc(i);
                                While b[j] > p do dec(j);

                                If i <= j then
                                        Begin
                                                If i < j then
                                                        Begin
                                                                x:= b[i];
                                                                b[i]:= b[j];
                                                                b[j]:= x;
                                                        End;
                                                inc(i);
                                                dec(j);
                                        End;
                        Until i > j;

                        partition(l,j);
                        partition(i,h);
                    End;
          Begin
                partition(1,n);
          End;

Procedure q2;

          Procedure partition(l,h: longint);
                    Var
                        i,j,p,x: longint;
                    Begin
                        If l >= h then exit;
                        p:= c[random(h - l + 1) + l];

                        i:= l;          j:= h;

                        Repeat
                                While c[i] < p do inc(i);
                                While c[j] > p do dec(j);

                                If i <= j then
                                        Begin
                                                If i < j then
                                                        Begin
                                                                x:= c[i];
                                                                c[i]:= c[j];
                                                                c[j]:= x;
                                                        End;
                                                inc(i);
                                                dec(j);
                                        End;
                        Until i > j;

                        partition(l,j);
                        partition(i,h);
                    End;
          Begin
                partition(1,n);
          End;

Procedure solve;
          Var
                      f: text;
                i,j,val: longint;
          Begin
                q1;
                q2;
                i:= 1;
                j:= n;
                val:= 2000000000;

                While (i <= n) and (j >= 1) do
                        Begin
                                If val > abs(b[i] + c[j]) then val:= abs(b[i] + c[j]);
                                If (b[i] + c[j]) >= 0 then dec(j) else inc(i);
                        End;

                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, val);
                Close(f);
          End;

Begin
          init;
          solve;
End.

Download