1. Порядок
Максимальна оцінка: 20 балів
Обмеження на час: 5 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: order.dat
Вихідний файл: order.sol
Програма: order.*
Нехай n - довільне натуральне число, а послідовність i1, i2, ... , in містить усі натуральні числа від 1 до n включно. Порушенням порядку у такій послідовності називають систему таких двох нерівностей, що справджуються: j < k та ij > ik. Якщо послідовність зростає, то кількість порушень порядку дорівнює 0. Якщо послідовність спадає, то така кількість дорівнює n(n - 1)/2. В усіх інших випадках ця кількість розташована між вказаними величинами.
Завдання
Встановіть парність кількості порушень порядку послідовності.
Вхідні дані
У першому рядку вхідного файлу вказано кількість послідовностей m. Кожний з наступних m рядків містить натуральне число n і послідовність різних натуральних чисел від 1 до n включно: i1, i2, ... , in при 2 ≤ т ≤ 100, 2 ≤ n ≤ 1 048 576. У 50 % тестів n ≤ 4096.
Вихідні дані
Єдиний рядок вихідного файлу має містити число в шістнадцятковій системі числення, яке відповідає двійковому числу яке утворене з m символів - нулів або одиниць - без пропусків: k-й символ рядка - це залишок від ділення на 2 кількості порушень порядку k-ї послідовності, заданої (k + 1)-м рядком вхідного файлу.
Приклад
order.dat
|
orderd.sol
|
5
3 1 2 3
3 2 3 1
3 1 3 2
4 2 3 4 1
4 3 4 1 2
|
6
|
Пояснення (00110 )2=(6)16
2. Код Грея
Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: grey.dat
Вихідний файл: grey.sol
Програма: grey.*
Кодом Грея називають непозиційну систему запису цілих натуральних чисел за допомогою двох символів 0 та 1 таким чином. Нуль кодують послідовністю нулів. При зростанні цілого числа:
- наймолодший 1-й розряд у послідовності символів змінюють у такій послідовності: 0, 1, після чого у наступний 2-й розряд записують 1, а наймолодший розряд змінюють уже у протилежному порядку;
- два наймолодші розряди змінюють у такому порядку: 00, 01, 11, 10, після чого у 3-й розряд записують 1, а два наймолодші розряди змінюють уже у протилежному порядку: 10, 11, 01, 00 ... ;
- k наймолодших розрядів змінюють у порядку, визначеному попередніми кроками, після чого у наступний (k + 1)-й розряд записують 1, а молодші розряди змінюють уже у протилежному порядку.
Коди Грея довжини 4 чисел від 0 до 15 включно такі (записано у порядку зростання числа): 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.
Коди Грея двох послідовних натуральних чисел відрізняються лише в одному розряді. Це використовують для збільшення надійності роботи системи оптичних фотодіодів при встановленні кута повороту дисків - носіїв інформації.
Завдання
Визначте код Грея натурального числа.
Вхідні дані
Вхідний файл містить лише десятковий запис натурального числа n при n < 1018.
Вихідні дані
Вихідний файл має містити код Грея числа n мінімальної довжини. Інакше кажучи, цей код має починатися з одиниці й містити j символів,
де 2j - 1 ≤ n < 2j.
Приклади
grey.dat
|
grey.sol
|
2
|
11
|
7
|
100
|
13
|
1011
|