수다닷컴

2008 정올 중고등부 시도 예선문제.질문 내용 :

고속철도의 시험선로를 구축해 열차를 시험운행 아는데, 선로의 상태를 검사하기 위해, 선로의 지정된 검사구간을 담당하는 로봇을 설치하였다. 그런데 검사구간이 서로 겹치는 로봇 사이에는 빈번한 데이터 고환이 필요하다. 따라서 이를 지원할 데이터 송수신 장치를 모든 로봇에 설치할 뿐만 아니라, 특별한 데이터처리장치를 로봇에 부착 하기로 하였다. 그러나 이 처리장치는 모든 로봇에 부착하지 않아도 되지만, 두 로봇이 담당하고 있는 검사구간이 서로 겹치면 이 두로봇 중에서 적어도 하나에는 반드시 부착되어야 한다.

시험선로를 눈금이 매겨진 직선으로 나타내면, 로봇의 검사구간은 이 직선 위에 있다고 할 때, 로봇들이 담당하는 선로의 검사구간을 입력 받아 로봇에 처리장치를 부착할 수 있는 모든 경우의 수를 구하시오. 경우의 수가 20,080,510이상일 때에는 20,080,510으로 나눈 나머지를 출력한다.

입력형식

입력파일의 이름은 input.txt이다. 첫째줄에 로봇의 개수 n이 입력된다. 둘째 줄부터 n개의 줄에 한 줄에 하나씩 로봇이 담당하는 검사구간의 왼쪽 끝점의 좌표와 오른쪽 끝점의 좌표가 빈 칸을 사이에 두고 주어진다. 각 검사구간의 왼쪽 끝점의 좌표가 오른쪽 끝점의 좌표보다 항상 작다. 또한 검사구간들의 끝점들의 좌표는 모두 서로 다르다. 다시 말하면, 어떤 좌표 값에도 두 개 이상의 검사구간의 끝점이 위치하지 않는다.

출력형식

출력 파일의 이름은 output.txt이다. 첫째 줄에 문제의 조건을 만족하면서 처리장치를 부착할 수 있는 경우의 수를 출력한다. 만약 경우의 수가 20,080,510 이상일 때에는 20,080,510 으로 나눈 나머지를 출력한다.

입력(intput.txt)
4
6 20
13 49
29 41
34 55

출력(output.txt)
7

프로그램
#include stdio.h
#include stdlib.h
#define maxn 10005

int n;
int train[maxn][2];
int nl[maxn][2];
int x[maxn];
int res[maxn];
void swap(int &a, int &b){
int t;
t=a;
a=b;
b=t;
}
void bsort(int ar[][2], int sz){
int i, j;
int m;
int index;
for(i=0; isz; i++){
m=ar[i][1];
index=i;
for(j=i+1; jsz; j++){
ㄱ

}
}
if(i != index){
swap(ar[i][0], ar[index][0]);
swap(ar[i][1], ar[index][1]);
}
}
}
int main(void)
{
file * fin=fopen(input.txt, r);
file * fout=fopen(output.txt, w);
int i, j;
int t;

fscanf(fin, %d, &n);
for(i=0; in; i++){
fscanf(fin, %d%d, &train[i][0], &train[i][1]);
}
fclose(fin);

bsort(train, n);
for(i=0; in; i++){
nl[1][0]=i;
nl[i][1]=train[i][0];
}
bsort(nl, n);

for(i=0; in; i++){
x[nl[i][0]]=n;
 sp; if(train[0][1]=nl[i][1]) break;
}

if(i != n){
t=0;
for(j=i; jn; j++){
while(tn && train[t][1]=nl[j][1]){
t++;
}
x[nl[j][0]]=t-1;
}
}

ㄷ

for(i=1; in; i++){
ㄴ

res[i]=res[i]%20080510;
}

fprintf(fout, %d\n, res[n-1]);
fclose(fout);

system(pause);
return 0;
}

33. 위 코드에서 bsort함수는 주어진 배열을 정렬하는 함수이다. bsort안에 있는 빈 칸 r에 알맞은 내용은?

답은
if(mar[j][1]){
m=ar[j][1];
index=j;
}

34 위의 빈 칸 ㄴ에 알맞은 내용은?

답은
res[i]=res[i-1]+res[x[i]];

35위의 빈칸 ㄷ에 알맞은 내용은?

답은
res[n]=1;
res[0]=2;

인데요;

저거 답을 빈칸에 넣고 실행하니까 출력이 이상하게 되네요.

예시에 나온 값을 입력했는데 출력된 값이 8이나오고...

이거 어떤 원리로 돌아가는 프로그램인지, 또 왜 이렇게 나오는건지 (문제가 이상한건지) 알려주세요.

신청하기