B. Козак Вус i програмування
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, а також ai
— число, яке записане в i-му регiстрi
setValue(i, j) — замiнити регiстр i на регiстр j. Тобто кожен бiт першого регiстра замiни-ти на вiдповiдний бiт у другому регiстрi. Iншими словами, виконати операцiю присвоєння
ai
=aj
.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 має бути записане
число 2y
- 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 до 264
- 1.
Козак Вус якимось чином дiзнався кiлькiсть команд, яка необхiдна для вирiшення кожної задачi, проте вiн ще не знає, якi саме команди потрiбно використати, i тому звернувся по допомогу до вас. Вiн просить вас знайти таку послiдовнiсть команд, яка розв’яже задачу для будь-яких можливих вхiдних даних.
Звернiть увагу, що ви можете виконати не бiльше 105
команд. Якщо ви виконаєте б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].
1 2500 0 1 9223372036854775808 0 0 131072 72057594037927936 18014398509481984 4096 549755813888 16384 144115188075855872 144115188075855872 4 2097152 3 13835058055282163712 2 9223372036854775808 0 0 4629700416936869888 2251799947902976 288230376151777280 2305843009213693954 4503599627501568 4432406249472 35184372088833 2199023255808 72057594037927940 1099511627792 7 16140901064495857664 5 6917529027641081856 4 9223372036854775808 9007336827912192 36028805642452992 1374406311936 4611686020591648768 9241386435364257856 288230444871188992 144255925564211216 8796093022976 67108897 281475245146240 15 17293822569102704640 13 8070450532247928832 15 5764607523034234880 144115188084262912 137439363072 9367487224930631745 576461851831832576 18016597541126176 67699200 9071508848640 2305843009214744580 360288245067550720 144115531677433856 31 17870283321406128128 29 15564440312192434176 26 6341068275337658368 2603086082178285568 ...
3 7 2 1 5 2 63 6 2 63 958299301