題目描述

人類終于登上了火星的土地并且見到了神秘的火星人。人類和火星人都無法理解對方的語言，但是我們的科學家發明了一種用數字交流的方法。這種交流方法是這樣的，首先，火星人把一個非常大的數字告訴人類科學家，科學家破解這個數字的含義后，再把一個很小的數字加到這個大數上面，把結果告訴火星人，作為人類的回答。

火星人用一種非常簡單的方式來表示數字――掰手指。火星人只有一只手，但這只手上有成千上萬的手指，這些手指排成一列，分別編號為?1,2,3,?1,2,3,?。火星人的任意兩根手指都能隨意交換位置，他們就是通過這方法計數的。

一個火星人用一個人類的手演示了如何用手指計數。如果把五根手指――拇指、食指、中指、無名指和小指分別編號為?1,2,3,41,2,3,4?和?55，當它們按正常順序排列時，形成了?55?位數?1234512345，當你交換無名指和小指的位置時，會形成?55?位數?1235412354，當你把五個手指的順序完全顛倒時，會形成?5432154321，在所有能夠形成的?120120?個?55?位數中，1234512345?最小，它表示?11；1235412354?第二小，它表示?22；5432154321?最大，它表示?120120。下表展示了只有?33?根手指時能夠形成的?66?個?33?位數和它們代表的數字：

三進制數	代表的數字
123123	11
132132	22
213213	33
231231	44
312312	55
321321	66

現在你有幸成為了第一個和火星人交流的地球人。一個火星人會讓你看他的手指，科學家會告訴你要加上去的很小的數。你的任務是，把火星人用手指表示的數與科學家告訴你的數相加，并根據相加的結果改變火星人手指的排列順序。輸入數據保證這個結果不會超出火星人手指能表示的范圍。

輸入格式

共三行。
第一行一個正整數?NN，表示火星人手指的數目（1≤N≤100001≤N≤10000）。
第二行是一個正整數?MM，表示要加上去的小整數（1≤M≤1001≤M≤100）。
下一行是?11?到?NN?這?NN?個整數的一個排列，用空格隔開，表示火星人手指的排列順序。

輸出格式

NN?個整數，表示改變后的火星人手指的排列順序。每兩個相鄰的數中間用一個空格分開，不能有多余的空格。

輸入輸出樣例

輸入 #1復制

5
3
1 2 3 4 5

輸出 #1復制

1 2 4 5 3

說明/提示

對于?30%30%?的數據，N≤15N≤15。

對于?60%60%?的數據，N≤50N≤50。

對于?100%100%?的數據，N≤10000N≤10000。

noip2004 普及組第 4 題

C語言代碼實現：

#include <stdio.h>
#include <stdlib.h>

// 交換數組中兩個元素的位置
void swap(int *a, int *b)?
{
? ? int temp = *a;
? ? *a = *b;
? ? *b = temp;
}

// 計算給定排列的下一個排列（按照字典序）
int next_permutation(int *arr, int n)?
{
? ? int i = n - 2;
? ? while (i >= 0 && arr[i] > arr[i + 1])?
?? ?{
? ? ? ? i--;
? ? }
? ? if (i < 0)?
?? ?{
? ? ? ? return 0;
? ? }
? ? int j = n - 1;
? ? while (arr[j] < arr[i])?
?? ?{
? ? ? ? j--;
? ? }
? ? swap(&arr[i], &arr[j]);
? ? int left = i + 1, right = n - 1;
? ? while (left < right) {
? ? ? ? swap(&arr[left], &arr[right]);
? ? ? ? left++;
? ? ? ? right--;
? ? }
? ? return 1;
}

int main() {
? ? int n, m,i;
? ? scanf("%d", &n);
? ? scanf("%d", &m);
? ? int *arr = (int *)malloc(n * sizeof(int)); ?// 動態分配內存?
? ? for (i = 0; i < n; i++)?
?? ?{
? ? ? ? scanf("%d", &arr[i]);
? ? }
? ??
? ? for (i = 0; i < m; i++)?
?? ?{
? ? ? ? next_permutation(arr, n);
? ? }
? ??
? ? for (i = 0; i < n; i++)?
?? ?{
? ? ? ? printf("%d", arr[i]);
? ? ? ? if (i!= n - 1)?
?? ??? ?{
? ? ? ? ? ? printf(" ");
? ? ? ? }
? ? }
? ? free(arr);
? ? return 0;
}