UVA 231 캐쳐 미사일 검사

[C++]UVA 231 캐쳐 미사일 검사

국방부 무기 납품 업체는 여러 공격 마사일을 차단하는 능력이 있는 캐쳐라고 불리는 새로운 방어용 마사일의 시험 검사를 방금 완료했다. 캐쳐는 훌륭한 방어용 마시일이 될 것이다. 캐처는 빠른 속도로 앞, 뒤 옆으로 이동할 수 있다. 그리고 위험하지 않게 공격용 마사일을 차단할수 있다. 그러나, 한 가지 결함이 존재했다. 캐쳐는 초기 높이에 도달하도록 발사되면, 차단한 마지막 미사일 보다 더 높이 움직일 동력을 갖고 있지 못하다.

납품업체가 완료했던 시험 검사는 컴퓨터 전쟁 시뮬레이션에서 적군이 공격하는 상황이다. 단지ㅣ 검사이기 때문에, 시뮬레이션이 캐쳐의 수직 이동 능력만 검사하였다. 각 시뮬레이션에서 캐쳐는 일정한 시간 간격으로 발사된 공격 미사일의 순서에 따라 발사된다. 각각의 공격 미사일에 대해 캐쳐가 얻는 정보는 순서대로 발사되는 공격 미사일이 차단될 지점의 높이로만 구성되었다. 하나의 검사에서 사용되는 공격 마사일은 단지 하나의 순열로 표현된다.

각 시험 결과는 순서대로 발사된 공격 미사일과 캐쳐에 의해 차단된 마사일의 최대 개수가 보고된다.

회계 감사원은 군 납품업체가 제출한 시뮬레이션 시험 결과에 따라 캐쳐가 기준치를 만족하는지를 확인하길 원했다. 여러 시험 데이터로 거사한다. 공격 미사일을 표현하는 입력 데이터를 입력 받아서, 캐쳐가 차단할 수 있는 미사일의 최대 개수를 출력 하는 프로그램을 작성해야 한다. 각 시험 검사에서 공격 미사일에 대해서, 캐쳐는 아래 두 가지 조건 중 하나를 만족하거나 둘 모두를 만족하면 캐쳐가 미사일을 차단할 수 있다. 공격 미사일인 경우

또는 차단된 마지막 미사일 이후에 발사된 미사일이 차단된 마지막 미아일보다 높이가 높지 않은 경우

입력

입력 데이터는 여러 개의 시험 거사 데이터가 입력된다. 각 검사 데이터는공격 미사일의 높이를 나타내는 32,767 이하의 양의 정수가 하나이상으로 이루어진 순열로 구성된다. 각 검사 패턴의 마지막은 -1 로 표시된다. -1 값은 미사일의 높이를 나타내는 것은 아니며, 단지 검사 패턴의 마지막을 나타내는 의미 없는 수일 뿐이다. 검사 패턴의 값으로 처음부터 -1 이 입력된다면, 입력 파일의 끝을 나타내는 값이다.

출력

각 시험 검사 패턴에 대해서 검사 번호를

"Test #1 , Test #2..."형식으로 먼저 출력하고, 캐쳐가 차단할 수 있는 공격 미사일의 최대 개수를출력 예제와 같은 형식으로 출력한다.

최대 개수는 검사 패턴 번호 아래에 출력하도록 한다.각 시험검사에 대한 결과를 구분하기 위해 공백 한 줄씩 검사 결과 사이에 출력하도록 한다.

주의 : 미사일의 개수는 한계가 없다. 무한 개의미사일에 처리되도록 프로그램 되어야 한다.

입력예제

389

207

155

300

299

170

158

65

-1

23

34

21

-1

-1

출력예제

Test #1:

maximum possible interceptions : 6

Test #2:

maximum possible interceptions : 2

소스

#include<stdio.h>
#define N 50000
FILE *fp=fopen("input.txt","r");
FILE *fp1=fopen("output.txt","w");
int p[N],count[N],n,cnt=0;
void process()
{
 int i,j,max;

 count[1]=1;
 for(i=1;i<n;i++)
 {
  max=-1;
  for(j=i;j>=0;j--)
  {
   if(max < count[j] && p[i]<p[j])
    max=count[j];
  }
  for(j=0;j<=i;j++)
  {
   if(count[j]==max)
   {
    if(count[i] <= count[j]+1)
     count[i]=max+1;
   }
  }
 }
 max=-1;
 for(i=1;i<n;i++)
 {
  if(max < count[i])
   max=count[i];
 }
 fprintf(fp1,"Text #%d\n", cnt);
 fprintf(fp1," maximum possible interceptions: %d\n\n", max);
}
void main()
{
 int a,i;

 while(1)
 {
  for(i=1;i<n;i++)
  {
   p[i]=0;
   count[i]=0;
  }
  n=1;
  fscanf(fp,"%d", &a);
  if(a == -1) break;
  else
  {
   p[n++]=a;
   while(1)
   {
    fscanf(fp,"%d", &a);
    if(a==-1) break;
    p[n++]=a;
   }
   cnt++;
   process();
  }
 }
}