MSTICK - Wooden Sticks
Tác giả: ll931110
Ngôn ngữ: Pascal
Program MSTICK;
Const
input = '';
output = '';
maxn = 5000;
Var
l,w: array[1..maxn] of integer;
a: array[1..maxn] of integer;
t,i,n,num: integer;
fi,fo: text;
Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);
Assign(fo, output);
Rewrite(fo);
End;
Procedure init;
Var
i: integer;
Begin
Readln(fi, n);
For i:= 1 to n do read(fi, l[i], w[i]);
End;
Procedure swap(var x,y: integer);
Var
t: integer;
Begin
t:= x;
x:= y;
y:= t;
End;
Procedure BubbleSort;
Var
i,j,t: integer;
Begin
For i:= 1 to n - 1 do
For j:= i + 1 to n do
if w[i] > w[j] then
Begin
swap(w[i], w[j]);
swap(l[i], l[j]);
End
else if w[i] = w[j] then
if l[i] > l[j] then swap(l[i], l[j]);
End;
Procedure solve;
Var
i,k: integer;
Begin
num:= 1;
a[1]:= l[1];
For i:= 2 to n do
if a[num] > l[i] then
Begin
inc(num);
a[num]:= l[i];
End
else
Begin
k:= 1;
While a[k] > l[i] do inc(k);
a[k]:= l[i];
End;
Writeln(fo, num);
End;
Procedure closefile;
Begin
Close(fo);
Close(fi);
End;
Begin
openfile;
Readln(fi, t);
For i:= 1 to t do
Begin
init;
BubbleSort;
solve;
End;
closefile;
End.