var
  a:array[1..500,1..3] of integer;
  c:array[1..500] of longint;
  ans:array[1..500] of longint;
  x,y,z,imax,max,i,j,n,nans:longint;

procedure readdata;
begin
  readln(n); if n=0 then begin writeln(0); halt end;
  for i:=1 to n do
  begin
    readln(x,y);
    if x>y then
    begin
      a[i,1]:=y;
      a[i,2]:=x;
    end else
    begin
      a[i,1]:=x;
      a[i,2]:=y;
    end;
    a[i,3]:=i;
  end;
end;

procedure sort;
begin
  for i:=2 to n do
  for j:=n downto i do
  if a[j-1,1]>a[j,1] then
  begin
    x:=a[j-1,1]; y:=a[j-1,2]; z:=a[j-1,3];
    a[j-1,1]:=a[j,1]; a[j-1,2]:=a[j,2]; a[j-1,3]:=a[j,3];
    a[j,1]:=x; a[j,2]:=y; a[j,3]:=z;
  end;
end;

function inn(ii,jj:integer):boolean;
begin
  if (a[ii,1]<a[jj,1]) and (a[ii,2]>a[jj,2]) then inn:=true else inn:=false;
end;

procedure solve;
begin
  for i:=1 to n-1 do
  for j:=i+1 to n do
  if inn(i,j) then inc(c[i]);  c[n]:=0;

  max:=-maxint;
  for i:=1 to n do if c[i]>max then begin max:=c[i]; imax:=i; end;

  x:=imax; nans:=1; ans[1]:=imax;

  repeat
    max:=-maxint;
    for i:=x+1 to n do
    if (c[i]>max) and (inn(x,i)) then
    begin
      max:=c[i];
      imax:=i;
    end;
    if max=-maxint then break;
    x:=imax; inc(nans); ans[nans]:=imax;
  until false;

end;

procedure writedata;
begin
  writeln(nans);
  for i:=nans downto 1 do write(a[ans[i],3],' ');
end;

begin
  readdata;
  sort;
  solve;
  writedata;
end.

A Test for you:
5
1 100
1 5
3 4
3 5
4 8
Your output is :
2
3 1
and correct output is:
3
3 2 1

My output is correct!!!
You said that correct out is:
3
3 2 1  ===>

3 4
1 5
1 100

How can it be so...????   (1,5) cant be in (1,100)
because of equality of their first point!

P.S. Ozuve Gel, Gaga6!

Edited by author 12.02.2006 23:51

Edited by author 13.02.2006 16:39

Edited by author 13.02.2006 18:49

Another Test:
10
1 10
2 8
3 7
4 6
11 39
12 13
14 15
16 17
18 19
Your Output is:
2
6 5
And correct output is:
4
4 3 2 1
Am i right?

PS: Qaqas nolar yene buzusdurme. bu defe azi 5 defe bu testi yoxladim ki sehv olmasin.

Your test:
10
1 -    1 10
2 -    2 8
3 -    3 7
4 -    4 6
5 -    11 39
6 -    12 13
7 -    14 15
8 -    16 17
9 -    18 19
10 -   ?????????

But, anyway thanks... I understood what's
worng with my code. In your test n should be 9 not 10!
5 times of cheking isnt enough for you ;) ... 50, maybe

P.S. Diqqetli ol!

Yes sorry again.
You can use something like this:
Firstly sort elementh in ascending order according to their lengths
Let c[i] be maximum lengths of sequences ending with i'th segment. Fill c with something like this:
for i:=1 to n do
 for k:=i+1 to n do if a[i] inside a[k] and c[i]>=[k]      then c[k]:=c[i]+1;
Remaining part is easy
Understand?


Basqa P.S:gorurem 1406-ni elemisen.
bir menim koduma baxa bilersen? meni deli eliyib o zibil.
kodu forumda vermisem

Edited by author 15.02.2006 21:25

Edited by author 15.02.2006 21:26

No, I didnt understood your algo,
maybe I didnt want to understand it....
Maybe your english is so-so...

But anyway you tried to help me, thx.
I'll solve it myself, I dont need any help.

He 1406 elemi6em, amma gorurem sende onu
artig eledin... Bir az gecikdim =)

Well...
Good luck then.

Any new ideas abou this damn test 5?! I've also got WA.
Usign similar DP from large segment to small ones:

FOR(i,n)
{
for(int j = i-1; j >= 0; --j)
{
if (v[j].beg < v[i].beg && v[i].end < v[j].end) //in segment
if (data[i][0] < data[j][0]+1)
{
data[i][0] = data[j][0]+1;
data[i][1] = j;                    //number of parent segment to get the sequence later
}