B. Козак Вус i програмування
Усiм вiдомо, що у Козака є його улюблений робот Атлас, з яким вiн багато грався у дитинствi. Сьогоднi Вус зрозумiв, що ще нiколи не намагався запрограмувати робота на якiсь iншi дiї, i тому почав читати iнструкцiю. З’ясувалося, що у пам’ятi Атласа зберiгаються 40 пронумерованих з одиницi регiстрiв, кожний iз яких мiстить 64 бiти. Це означає, що кожен регiстр складається з 64-ох нулiв та одиниць:
Вус також зрозумiв, що для програмування робота можна використовувати наступнi 7 команд, якi виконують операцiї над регiстрами. Для зручностi будемо регiстром i називати регiстр пiд номером i, а також a[i] — число, яке записане в i-му регiстрi
setValue(i, j) — замiнити регiстр i на регiстр j. Тобто кожен бiт першого регiстра замiни-ти на вiдповiдний бiт у другому регiстрi. Iншими словами, виконати операцiю присвоєння
a[i]=a[j].setXor(i, j, k) — замiнити регiстр i на побiтовий xor регiстрiв j та k. Тобто кожен бiт регiстра i замiнити на xor вiдповiдних бiтiв у регiстрiв j та k. Про операцiю xor буде зазначено нижче.
setAnd(i, j, k) — замiнити регiстр i на побiтовий and регiстрiв j та k. Тобто кожен бiт регiстра i замiнити на and вiдповiдних бiтiв у регiстрiв j та k. Про операцiю and буде зазначено нижче.
setOr(i, j, k) — замiнити регiстр i на побiтовий or регiстрiв j та k. Тобто кожен бiт регiстра i замiнити на or вiдповiдних бiтiв у регiстрiв j та k. Про операцiю or буде зазначено нижче.
shiftLeft(i, x) — зсунути всi бiти регiстру i на x позицiй влiво. Про операцiю зсуву буде зазначено нижче.
shiftRight(i, x) — зсунути всi бiти регiстру i на x позицiй вправо. Про операцiю зсуву буде зазначено нижче.
setNot(i, j) — замiнити регiстр i на iнвертований регiстр j. Тобто кожен бiт регiстра i замiнити на 1, якщо на вiдповiднiй позицiї регiстра j записане 0, i замiнити на 0, якщо на вiдповiднiй позицiї регiстра j записане 1.
Результатом операцiї xor двох бiтiв є 0, якщо бiти однаковi, та 1, якщо рiзнi.
Результатом операцiї and двох бiтiв є 1, якщо обидва бiти є рiвними 1, та 0, якщо хоча б один бiт рiвний 0.
Результатом операцiї or двох бiтiв є 0, якщо обидва бiти є рiвними 0, та 1, якщо хоча б один бiт рiвний 1.
Результатом операцiї зсув регiстру на x позицiй улiво є регiстр, у якому кожний бiт рiвний бiту, що був записаний у початковому регiстрi на x позицiй правiше, та рiвний 0, якщо не iснувало у початковому регiстрi позицiї на x правiше.
Результатом операцiї зсув регiстру на x позицiй управо є регiстр, у якому кожний бiт рiвний бiту, що був записаний у початковому регiстрi на x позицiй лiвiше, та рiвний 0, якщо не iснувало у початковому регiстрi позицiї на x лiвiше.
Прочитавши iнструкцiю, Козак Вус одразу ж придумав 6 досить цiкавих задач. Ще трохи подумавши, Козак зрозумiв, що для того, щоб запрограмувати робота на конкретну задачу, потрiбно лише ввести роботу набiр команд, який би вирiшував цю задачу. Припустимо, що t — кiлькiсть команд, яку ви виконали в певнiй задачi.
А ось i самi задачi:
Пiдзадача 1: (до 6 балiв) у регiстрi 1 записане число x. Усi iншi регiстри повнiстю складаються з 0 - iв. Нехай число y дорiвнює 1, якщо число x парне, i дорiвнює 0, якщо x непарне. Задача полягає втому, щоб пiсля виконання роботом операцiй у регiстрi 2 було записане число y. Ви отримаєте ??? балiв.
Пiдзадача 2: (до 10 балiв) у регiстрi 1 записане x, а в регiстрi 2 записане y. Усi iншi регiстри повнiстю складаються з 0-iв. Нехай z = x + y. Задача полягає в тому, щоб пiсля виконання роботом операцiй у регiстрi 3 було записане число z. Потрiбно зазначити, що якщо двiйковий запис числа z потребує бiльше нiж 64 розряди, то в регiстрi 3 мають бути записанi лише першi 64 розряди. Ви отримаєте ??? балiв.
Пiдзадача 3: (до 13 балiв) у регiстрi 1 записане x. Нехай число y — це кiлькiсть одиниць у двiйковому записi числа x. Тодi пiсля виконання роботом операцiй у регiстрi 2 має бути записане y. Ви отримаєте ⌊13 log(t min(1505; t) + 1)⌋ балiв.
Пiдзадача 4: (до 23 балiв) у регiстрах 1 та 2 записанi два рiзнi числа x та y вiдповiдно. Нехай якщо x > y, то a = 0; b = 1, а якщо y > x, то b = 0; a = 1. Задача полягає в тому, щоб пiсля виконання роботом операцiй у регiстрах 3 та 4 були записанi числа a та b вiдповiдно. Ви отримаєте ??? балiв.
Пiдзадача 5: (до 18 балiв) у регiстрi 1 записане число x. Нехай число y —це кiлькiсть одиницьу двiйковому записi числа x. Тодi пiсля виконання роботом операцiй у регiстрi 1 має бути записанечисло 2^y - 1. Ви отримаєте ??? балiв.
Пiдзадача 6: (до 30 балiв) нехай a — це масив, який мiстить 9 невiд’ємних цiлих попарно рiзних чисел. Тодi для кожного i вiд 1-ого до 9-и у i-ому регiстрi записане ai. Нехай b — це вiдсортований за зростанням масив a. Тодi пiсля виконання роботом операцiй, для кожного i вiд 1-ого до 9-и у i-ому регiстрi має бути записане bi. Потрiбно зазначити, що нумерацiя у масивах a та b починається з одиницi. Ви отримаєте ??? балiв.
Якщо про початкове значення регiстру нiчого не сказано, тодi на початку вiн повнiстю складається з нулiв. Усi числа вiд 0 до 2^64 - 1.
Козак Вус якимось чином дiзнався кiлькiсть команд, яка необхiдна для вирiшення кожної задачi, проте вiн ще не знає, якi саме команди потрiбно використати, i тому звернувся по допомогу до вас. Вiн просить вас знайти таку послiдовнiсть команд, яка розв’яже задачу для будь-яких можливих вхiдних даних.
Звернiть увагу, що ви можете виконати не бiльше 10^5 команд. Якщо ви виконаєте бiльше, то ви отримаєте 0 балiв та вердикт Неправильна вiдповiдь. Якщо ви виконаєте неправильний запит, то ви отримаєте 0 балiв та вердикт Помилка виконання. Результатом вашого рiшення в кожнiй пiдзадачi будуть тi регiстри, у яких мають бути записанi рiшення. В усiх iнших регiстрах можуть бути будь-якi числа.
####Протокол взаємодiї
Для кожної пiдзадачi вам потрiбно окремо реалiзувати одну функцiю:
void solve(int n), де n - номер підзадачі
ця функцiя не приймає нiяких параметрiв та нiчого не повертає.
Ви можете використовувати наступнi функцiї:
void setValue(integer i, integer j)
ця функцiя надає регiстру i (1 ⩽ i ⩽ 40) значення регiстра j (1 ⩽ j ⩽ 40).
void setXor(integer i, integer j, integer k)
ця функцiя надає регiстру i (1 ⩽ i ⩽ 40) значення операцiї xor регiстрiв j (1 ⩽ j ⩽ 40) та k (1 ⩽ k ⩽ 40).
void setAnd(integer i, integer j, integer k)
ця функцiя надає регiстру i (1 ⩽ i ⩽ 40) значення операцiї and регiстрiв j (1 ⩽ j ⩽ 40) та k (1 ⩽ k ⩽ 40).
void setOr(integer i, integer j, integer k)
ця функцiя надає регiстру i (1 ⩽ i ⩽ 40) значення операцiї or регiстрiв j (1 ⩽ j ⩽ 40) та k (1 ⩽ k ⩽ 40).
void shiftLeft(integer i, integer x)
ця функцiя реалiзовує зсув регiстру i (1 ⩽ i ⩽ 40) на x (0 ⩽ x ⩽ 64) позицiй улiво.
void shiftRight(integer i, integer x)
ця функцiя реалiзовує зсув регiстру i (1 ⩽ i ⩽ 40) на x (0 ⩽ x ⩽ 64) позицiй управо.
void setNot(integer i, integer j)
ця функцiя надає регiстру i (1 ⩽ i ⩽ 40) значення iнвертованого регiстру j (1 ⩽ j ⩽ 40).
####Приклад:
Припустимо, що в регiстрi 1 записане число 6, а в регiстрi 2 число 3, тодi якщо виконаємо такi команди:
setValue(3, 1)
setXor(4, 1, 2)
setAnd(5, 1, 2)
setOr(6, 2, 1)
shiftLeft(2, 3)
shiftRight(1, 2)
setNot(7, 2)
то першi сiм чисел масиву будуть виглядати так: [1, 24, 6, 5, 2, 7, 18446744073709551591].