영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
To be able to run your new AI startup, you need to perform large-scale parallel computations. A strong candidate for this turns out to be mushrooms! To compute things, you have a cluster of N mushrooms numbered from 1 to N. You now want to load the weights of a neural network into the mushrooms. Each mushroom stores a number, which initially is 0.
To change the values stored in the mushrooms, you can perform a round. In each round, you give one instruction to each mushroom. All these instructions are then executed simultaneously. Let P[i] denote the value of mushroom i before the round, and A[i] the value of mushroom i after the round. The available operations for mushroom i are:
Instruction — Operation — Description
p— A[i] = P[i] — keep the previous value< j— A[i] = P[j]<<1 — where<<denotes bitwise left shift> j— A[i] = P[j]>>1 — where>>denotes bitwise right shift+ j— A[i] = P[j] + 1 — where+denotes addition^ j— A[i] = P[i]^P[j] — where^denotes bitwise XOR& j— A[i] = P[i]&P[j] — where&denotes bitwise AND| j— A[i] = P[i]|P[j] — where|denotes bitwise OR
Be sure to read the descriptions of the operations carefully. You can find definitions of all bitwise operations here (https://en.wikipedia.org/wiki/Bitwise_operations_in_C#Bitwise_operators). The mushrooms can store arbitrarily large numbers. This means that bitwise left shift and addition always cause the value to increase.
You are now given N weights w_1, w_2, …, w_N and need to find a sequence of rounds such that A[i] = w_i for all i.
The fewer rounds you use, the more points you get. In the test data, N is always 512.
Input
The first line of input contains the integer N (N = 512), the number of mushrooms. The reason this is part of the input is to make it easier to test your solution on smaller values of N.
The second line contains the integers w_1, w_2, …, w_N (0 ≤ w_i ≤ 255), the weights of the neural network.
Output
First, print the integer r, the number of rounds your solution uses.
Then print r lines, where each line describes one round. For each round, print the N operations, separated by spaces. The first operation is the one that mushroom 1 should execute, the second that mushroom 2 should execute, and so on. Each operation should be printed in the same format as in the table above, where j (1 ≤ j ≤ N) is the index of a mushroom. Two examples of how valid single operations could look like are “p” and “< 10”.
Scoring
Your solution will be tested on a number of test cases. If it ever prints a sequence of rounds that is invalid or does not produce the correct weights, you get zero points.
Otherwise, let R_max denote the largest number of rounds you use over all test cases. You then get points according to the following piecewise linear function.
(그림은 원문 저장소에서 볼 수 있습니다)
The number of points you get for a given R_max. Note that the x-axis is not linear.
If R_max ≤ 9, you get 100 points. The score values for 9 ≤ R_max ≤ 20 are also given in the table below.
| R_max | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| Points | 100 | 70 | 60 | 50 | 48 | 47 | 46 | 45 | 44 | 43 | 42 | 41 |
Sample Judge
To make it easier to test your program, a sample judge is provided in the attachments at the bottom. This is not the same judge code that is used on Kattis. A description of how to run the code is given in the comment at the beginning of the code.
Explanation of Sample
Note: the following sample case will not be run against your submission since N ≠ 512. It exists only to demonstrate the input and output format; all input that your solution is tested on has N = 512.
Initially, all mushrooms have the value 0. Below, the mushrooms' values before and after each operation are shown.
| 0 0 0 0 |
| 0 1 0 1 |
| 0 1 2 2 |