Іншопланетний словник#7049

Іншопланетний словник

14 секунд

64 мегабайти

Дуже легка

У віддаленому майбутньому землянами було знайдено планету, на якій раніше жили невідомі людству розумні істоти. Самих істот знайти не вдалося, але було знайдено їхню бібліотеку з великою кількістю писемних матеріалів. Вчені негайно приступили до розшифровування цих матеріалів, сподіваючись зрозуміти, де, власне, самі істоти.

Аналіз наявних текстів встановив, що в іншопланетній системі письма використовують абетку з $N$ літер, а кожне слово містить $M$ літер. Вчені знайшли щось схоже на словник, який має значно допомогти в розумінні цієї мови. Слова в цьому словнику упорядковано не в лексикографічному порядку, а в порядку спадання "важливості". Якщо "важливість" двох слів однакова, то раніше записано лексикографічно менше слово.

Для довільного слова $a_{1} a_{2} \dots a_{M}$ a_1a_2\dots a_M цю "важливість" знаходять як суму відповідних елементів матриці:

W = p_{1, a_{1}} + p_{2, a_{2}} + \dots + p_{M, a_{M}}

W = p_{1,a_1} + p_{2,a_2} + \dots + p_{M,a_M}

Розглянемо такий приклад. При $N = 2$ N = 2 (кількість літер) і $M = 3$ M = 3 (довжина слова) у цій мові можливі $8$ різних слів. Запишемо ці слова в лексикографічному порядку. Позначатимемо тут і далі $k$ -ту літеру іншопланетної абетки $k$ -ю літерою латиниці: aaa, aab, aba, abb, baa, bab, bba і bbb. Нехай матриця має такий вигляд:

Тоді важливість слів буде такою:

aaa: 8 = 1 + 5 + 2;

aab: 12 = 1 + 5 + 6;

aba: 10 = 1 + 7 + 2;

abb: 14 = 1 + 7 + 6;

baa: 12 = 5 + 5 + 2;

bab: 16 = 5 + 5 + 6;

bba: 14 = 5 + 7 + 2;

bbb: 18 = 5 + 7 + 6;

а у словнику порядок слів такий: bbb, bab, abb, bba, aab, baa, aba, aaa.

Для подальшого аналізу вченим-землянам потрібно вміти швидко обчислювати, яке слово буде міститися на певному місці в такому словнику згідно з описаними правилами впорядкування: спочатку за спаданням "важливості", а при однаковій "важливості" — у алфавітному порядку.

За відомими $N$ , $M$ , $K$ і матрицею $p_{j, c}$ p_{j, c} визначити, яке слово стоятиме на $K$ -му місці у словнику іншопланетних істот.

Вхідні дані

Перший рядок файлу містить три цілі числа: $N$ , $M$ і $K$ . Рядки з $2$ -го до $(M + 1)$ (M+1)-го містять по $N$ цілих чисел — відповідні елементи матриці $p_{j, c}$ p_{j, c} ( $2 \leq N \leq 16$ 2 \leq N \leq 16, $1 \leq M \leq 10$ 1 \leq M \leq 10, $0 \leq p_{j, c} \leq 1 0^{8}$ 0 \leq p_{j, c} \leq 10^8, $1 \leq K \leq N^{M}$ 1 \leq K \leq N^M).

Вихідні дані

Єдиний рядок файлу має містити слово, яке розташоване на $K$ -му місці у словнику іншопланетних істот.

Приклади

Приклад 1