화성 인 (martian. pas / c / cpp)

화성 인
(martian.pas/c/cpp)
 
[문제 설명]
 
인 류 는 마침내 화성의 땅 에 올 라 신비 한 화성 인 을 만 났 다.인간 과 화성 인 은 상대방 의 언어 를 이해 할 수 없 지만 우리 과학자 들 은 디지털 로 교류 하 는 방법 을 발명 했다.이런 교류 방법 은 이렇다. 우선 화성 인 들 은 매우 큰 숫자 를 인류 과학자 에 게 알려 주 었 다. 과학자 들 은 이 숫자의 의 미 를 풀 고 아주 작은 숫자 를 이 큰 숫자 위 에 올 려 결 과 를 화성 인 에 게 알려 인간 의 대답 으로 삼 았 다.
화성 인 들 은 손가락 을 쪼 개 는 아주 간단 한 방식 으로 숫자 를 표시 한다.화성 인 은 한 손 밖 에 없 지만 이 손 에는 수천 수만 의 손가락 이 있 는데 이 손가락 들 은 일렬 로 서서 각각 1, 2, 3 번 으로 번 호 를 매 긴 다.화성 인의 임의의 두 손가락 이 자 리 를 마음대로 바 꿀 수 있 는데, 그들 이 바로 이 방법 을 통 해 계산 한 것 이다.
화성 인 이 손가락 으로 계산 하 는 방법 을 인간 의 손 으로 보 여 주 었 다.다섯 손가락 인 엄 지, 검지, 중지, 약지, 새끼손가락 을 각각 1, 2, 3, 4, 5 로 번 호 를 매 긴 다 면 정상 적 인 순서 로 배열 할 때 5 자리 12345 가 형성 된다. 약지 와 새끼손가락 의 위 치 를 교환 할 때 5 자리 12354 가 형성 된다. 다섯 손가락 의 순 서 를 완전히 뒤 집 으 면 54321 이 형성 되 고 모든 형성 가능 한 120 개의 5 자리 에서12345 가 가장 작고 1 을 나타 낸다.12354 두 번 째 작은 것 은 2 를 나타 낸다.54321 이 가장 크 고 120 을 나타 낸다.아래 표 는 손가락 이 세 개 밖 에 없 을 때 형 성 될 수 있 는 6 개의 세 자릿수 와 이들 이 대표 하 는 숫자 를 보 여 준다.
 
3 진수
123
132
213
231
312
321
대표 적 인 숫자
1
2
3
4
5
6
 
이제 당신 은 화성 인과 교류 하 는 첫 번 째 지구 인 이 되 었 습 니 다.화성 인 이 손가락 을 보 여줄 것 이다. 과학자 가 더 해 야 할 아주 작은 숫자 를 알려 줄 것 이다.당신 의 임 무 는 화성 인 이 손가락 으로 표시 하 는 수 를 과학자 가 알려 준 수 와 더 하고 그 결과 에 따라 화성 인 손가락 의 배열 순 서 를 바 꾸 는 것 입 니 다.데 이 터 를 입력 하면 이 결 과 는 화성 인 손가락 이 표시 할 수 있 는 범 위 를 넘 지 않 을 것 이다.
 
[파일 입력]
 
입력 파일 martian. in 은 세 줄 을 포함 합 니 다. 첫 번 째 줄 에는 정수 N 이 있 습 니 다. 화성 인의 손가락 수 (1 < = N < = 10000) 를 표시 합 니 다.두 번 째 줄 은 정수 M 으로 더 할 작은 정수 (1 < = M < = 100) 를 나타 낸다.다음 줄 은 화성 인 손가락 의 배열 순 서 를 나타 내 는 1 에서 N 까지 의 정수 배열 이다.
 
[출력 파일]
 
출력 파일 martian. out 은 한 줄 뿐 입 니 다. 이 줄 은 N 개의 정 수 를 포함 하여 변 경 된 화성 인 손가락 의 배열 순 서 를 표시 합 니 다.서로 인접 한 두 개의 수 중 하 나 를 빈 칸 으로 나 누 어 여분의 빈 칸 이 있어 서 는 안 된다.
 
[샘플 입력]
 
5
3
1 2 3 4 5
 
 [샘플 출력]
 
1 2 4 5 3
 
[데이터 규모]
 
30% 의 데이터 에 대해 N < = 15;
60% 의 데이터 에 대해 N < = 50;
모든 데이터 에 대해 N < = 10000;
=======================
스스로 정렬 을 만들어 야 합 니 다.
1. 포인 터 는 뒤쪽 에서 앞쪽 으로 첫 번 째 왼쪽 의 수가 오른쪽 보다 큰 위치 로 이동한다
   오른쪽 위 치 를 k 로 기록 합 니 다.
2. k 위치 에서 n 위치 까지 k - 1 보다 크 고 가장 작은 수 를 찾 습 니 다.
   교환 하 다.
3. k + 1 위 치 를 n 위치 사이 의 숫자 로 작은 것 부터 큰 것 까지 정렬
4. 1 - 3 과정 M - 1 회 반복.
5. 출력
==============================================

var
  n,m:longint;
  a:array[0..10000]of longint;
procedure init;
begin
  assign(input,'p1045.in');
  assign(output,'p1045.out');
  reset(input); rewrite(output);
end;

procedure terminate;
begin
  close(input); close(output);
  halt;
end;

procedure main;
var
  i,i1,j,j1,tem:longint;
  k:longint;
begin
  readln(n);
  readln(m);
  for i:=1 to n do
    read(a[i]);
  a[0]:=-maxlongint;
  for i:=1 to m do
    begin
      k:=n;
      while a[k-1]>a[k] do dec(k);               //            
      j1:=k;
      for j:=k+1 to n do
        if a[j]>a[k-1] then if a[j]a[j1] then
begin
tem:=a[i1];
a[i1]:=a[j1];
a[j1]:=tem;
end;
end;
for i:=1 to n do
write(a[i],' ');
end;
begin
init;
main;
terminate;
end.