eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

B. Козак Вус i програмування

B. Козак Вус i програмування

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Ус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в та одиниць:

B1.gif

Вус також зрозумiв, що для програмування робота можна використовувати наступнi 7 команд, якi виконують операцiї над регiстрами. Для зручностi будемо регiстром i називати регiстр пiд номером i, а також a[i] — число, яке записане в i-му регiстрi

  1. setValue(i, j) — замiнити регiстр i на регiстр j. Тобто кожен бiт першого регiстра замiни-ти на вiдповiдний бiт у другому регiстрi. Iншими словами, виконати операцiю присвоєння a[i] = a[j].

  2. 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 буде зазначено нижче.

  3. 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 буде зазначено нижче.

  4. 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 буде зазначено нижче.

  5. shiftLeft(i, x) — зсунути всi бiти регiстру i на x позицiй влiво. Про операцiю зсуву буде зазначено нижче.

  6. shiftRight(i, x) — зсунути всi бiти регiстру i на x позицiй вправо. Про операцiю зсуву буде зазначено нижче.

  7. 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.

B2.gif

Результатом операцiї and двох бiтiв є 1, якщо обидва бiти є рiвними 1, та 0, якщо хоча б один бiт рiвний 0.

B3.gif

Результатом операцiї or двох бiтiв є 0, якщо обидва бiти є рiвними 0, та 1, якщо хоча б один бiт рiвний 1.

B4.gif

Результатом операцiї зсув регiстру на x позицiй улiво є регiстр, у якому кожний бiт рiвний бiту, що був записаний у початковому регiстрi на x позицiй правiше, та рiвний 0, якщо не iснувало у початковому регiстрi позицiї на x правiше.

B5.gif

Результатом операцiї зсув регiстру на x позицiй управо є регiстр, у якому кожний бiт рiвний бiту, що був записаний у початковому регiстрi на x позицiй лiвiше, та рiвний 0, якщо не iснувало у початковому регiстрi позицiї на x лiвiше.

B6.gif

Прочитавши 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].

Пример

Входные данные #1
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
...
Выходные данные #1
3
7 2 1
5 2 63
6 2 63
958299301