17768번 - Słowo 다국어

Zadanie polega na znalezieniu k-tego (w porządku leksykograficznym) spośród niepustych słów składających się z co najwyżej n liter ze zbioru {a, b, c} i takich, że każde dwie sąsiadujące litery w tym słowie są różne.

Przypomnijmy, że słowo s jest mniejsze od słowa t (s 6= t) w porządku leksykograficznym jeśli s jest prefiksem t lub jeśli na pierwszej pozycji, na której słowa s i t się różnią, w słowie s znajduje się mniejsza (w porządku alfabetycznym) litera niż w słowie t.

Jedyny wiersz wejścia zawiera dwie liczby całkowite n i k (1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 10¹⁸) z treści zadania.

Jeśli istnieje mniej niż k słów spełniających warunki zadania, na wyjście należy wypisać NIE. W przeciwnym razie w jedynym wierszu wyjścia powinno znaleźć się szukane słowo.