#include<cstdio> #define INF 5000000000000000000 #define L 61 long long int tab[L]; long long int get2n(long long int n) { return n >= L ? INF : tab[n]; } bool czyMniejsze(int k, long long int n, int mnoznik) { if (get2n(n) >= INF) { return true; } long long int n2 = get2n(n) - 1; if (k <= mnoznik * n2) { return true; } else { return false; } } long long int absM(long long a) { return a > 0 ? a : -a; } int ktoraPolowa (long long int k, long long int lkp, long long int pkp) { if (pkp >= INF) { return 1; } return absM(k - lkp) < absM(k - pkp) ? 1 : 2; } char dajZnak(char znak, int ktory) { if (znak == 'a' && ktory == 1) return 'b'; if (znak == 'a' && ktory == 2) return 'c'; if (znak == 'b' && ktory == 1) return 'a'; if (znak == 'b' && ktory == 2) return 'c'; if (znak == 'c' && ktory == 1) return 'a'; if (znak == 'c' && ktory == 2) return 'b'; return '\n'; } int main () { long long int n, k; tab[0] = 1; for (int i = 1; i < L; i++) { tab[i] = 2 * tab[i-1]; } scanf("%lld %lld", &n, &k); long long int lkp, pkp; char znak; if (czyMniejsze(k, n, 1)) { printf("a"); znak = 'a'; lkp = 1; if (get2n(n) >= INF) { pkp = INF; } else { pkp = get2n(n) - 1; } } else if (czyMniejsze(k, n, 2)) { printf("b"); znak = 'b'; lkp = get2n(n); pkp = 2 * (get2n(n) - 1); } else if (czyMniejsze(k, n, 3)) { printf("c"); znak = 'c'; lkp = 2 * (get2n(n) - 1) + 1; pkp = 3 * (get2n(n) - 1); } else { printf("NIE\n"); return 0; } long long int i = 0; while (true) { if (k == lkp) { printf("\n"); break; } int polowa = ktoraPolowa(k, lkp + 1, pkp); znak = dajZnak(znak, polowa); printf("%c", znak); if (polowa == 1) { lkp = lkp + 1; if (pkp >= INF) { pkp = get2n(--n) + i++; } else { pkp = (lkp + pkp) / 2 ; } } else { lkp = (lkp + pkp) / 2 + 1; //pkp bez zmian } } return 0; }
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 119 120 121 122 123 | #include<cstdio> #define INF 5000000000000000000 #define L 61 long long int tab[L]; long long int get2n(long long int n) { return n >= L ? INF : tab[n]; } bool czyMniejsze(int k, long long int n, int mnoznik) { if (get2n(n) >= INF) { return true; } long long int n2 = get2n(n) - 1; if (k <= mnoznik * n2) { return true; } else { return false; } } long long int absM(long long a) { return a > 0 ? a : -a; } int ktoraPolowa (long long int k, long long int lkp, long long int pkp) { if (pkp >= INF) { return 1; } return absM(k - lkp) < absM(k - pkp) ? 1 : 2; } char dajZnak(char znak, int ktory) { if (znak == 'a' && ktory == 1) return 'b'; if (znak == 'a' && ktory == 2) return 'c'; if (znak == 'b' && ktory == 1) return 'a'; if (znak == 'b' && ktory == 2) return 'c'; if (znak == 'c' && ktory == 1) return 'a'; if (znak == 'c' && ktory == 2) return 'b'; return '\n'; } int main () { long long int n, k; tab[0] = 1; for (int i = 1; i < L; i++) { tab[i] = 2 * tab[i-1]; } scanf("%lld %lld", &n, &k); long long int lkp, pkp; char znak; if (czyMniejsze(k, n, 1)) { printf("a"); znak = 'a'; lkp = 1; if (get2n(n) >= INF) { pkp = INF; } else { pkp = get2n(n) - 1; } } else if (czyMniejsze(k, n, 2)) { printf("b"); znak = 'b'; lkp = get2n(n); pkp = 2 * (get2n(n) - 1); } else if (czyMniejsze(k, n, 3)) { printf("c"); znak = 'c'; lkp = 2 * (get2n(n) - 1) + 1; pkp = 3 * (get2n(n) - 1); } else { printf("NIE\n"); return 0; } long long int i = 0; while (true) { if (k == lkp) { printf("\n"); break; } int polowa = ktoraPolowa(k, lkp + 1, pkp); znak = dajZnak(znak, polowa); printf("%c", znak); if (polowa == 1) { lkp = lkp + 1; if (pkp >= INF) { pkp = get2n(--n) + i++; } else { pkp = (lkp + pkp) / 2 ; } } else { lkp = (lkp + pkp) / 2 + 1; //pkp bez zmian } } return 0; } |