Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#define maxn 5003
#include "string.h" 
#includev "stdio.h" 
long int  k,l[maxn],w[maxn],h[maxn];
void make1(long int s,long int t)
  {int i,j,x,t1;
   i=s;j=t;x=i;
   do 
    {while ((i < j) && (l[j] >= l[x])) j-=1; 
       t1=l[j];l[j]=l[x];l[x]=t1;
       t1=w[j];w[j]=w[x];w[x]=t1;
       x=j;
     while ((i < j) && (l[i] <= l[x])) i+=1;
       t1=l[i];l[i]=l[x];l[x]=t1;
       t1=w[i];w[i]=w[x];w[x]=t1;
       x=i;}
  while (i < j);
  k=x;
  }
void make2(long int s,long int t)
 {
   if (s < t)
      { make1(s,t);
        make2(s,k-1);
        make2(k+1,t);
      }
 }
int main()
{long int max,sec,i,j,q,k,m,n;
 scanf("%ld",&m);
 for (q=1; q <= m; q++) 
  { memset(l,0,sizeof(l));
    memset(w,0,sizeof(w));  
    scanf("%ld",&n);
    for (i=1; i <= n; i++){scanf("%ld",&l[i]);scanf("%ld",&w[i]);}  
    k=0;make2(1,n);
    for (i=1; i <= n-1; i++)
	 for(j=i+1; j <= n; j++)
	 {if ((l[i] == l[j]) && (w[i] > w[j]))
	 {max=w[i];w[i]=w[j];w[j]=max;}
	 if (l[j] > l[i]) break;
	 }
	memset(h,0,sizeof(h));k=1;h[1]=w[1];
    for (i=2; i <= n; ++i)
     {max=-1;
      for (j=1; j <= k; ++j)
	  if (w[i] >= h[j] && max < h[j]) {max=h[j];sec=j;}
       if (max==-1) h[++k]=w[i];
	      else h[sec]=w[i];
     }            
    printf("%ld\n",k);
  }
}