1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 #include #include #include #include #include using namespace std; bool wantToEatSomethingButProgrammingIsLife(vector numbers) { int invertions = 0; for(int i = 0; i < numbers.size() - 1; i++) { for(int j = i + 1, k = numbers[i] - 1; j < numbers.size() && k > 0; j++) { if(numbers[i] > numbers[j]) { invertions++; k--; } } } for(int i = numbers.size() - 1; i >= 1; i--) { for(int j = i - 1, k = numbers[i-1] - 1; j >= 0 && k > 0; j--) { if(numbers[i] > numbers[j]) { invertions--; k--; if(invertions < 0) return false; } } } return invertions == 0; } int factorial(long long n) { if(n == 1) return 1; else return(factorial(n-1) * n); } int main() { vector numbers; int permutation; unsigned long long stablePermutationNumber; unsigned long long currentPermutation = 0; scanf("%u %ull", &permutation, &stablePermutationNumber); for(int i = 1; i <= permutation; i++) { numbers.push_back(i); } int maxZXC = factorial((long long)permutation); for(int zxc = 0; zxc < maxZXC; zxc++) { for(int i = permutation - 1; i > 0; i--) { if(numbers[i] > numbers[i-1]) { int smallestDigitToRight = permutation; int smallestPos = i; for(int j = i; j < permutation; j++) { if(numbers[j] < smallestDigitToRight && numbers[i-1] < numbers[j]) { smallestDigitToRight = numbers[j]; smallestPos = j; } } numbers[smallestPos] = numbers[i-1]; numbers[i-1] = smallestDigitToRight; for(int j = i; j < permutation - 1; j++) { for(int k = i + 1; k < permutation; k++) { if(numbers[j] > numbers[k]) { int temp = numbers[j]; numbers[j] = numbers[k]; numbers[k] = temp; } } } if(wantToEatSomethingButProgrammingIsLife(numbers)) { currentPermutation++; if(currentPermutation == stablePermutationNumber) { cout << "TAK" << endl; for(int j = 0; j < numbers.size() - 1; j++) { cout << numbers[j] << " "; } cout << numbers[numbers.size()-1]; return 0; } } break; } } } cout << "NIE" << endl; return 0; }