Problem D
Mushrooms
Languages
en
sv
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 1. 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, \dots , 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, \dots , w_N$ ($0 \leq w_i \leq 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 \leq j \leq 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.
![\includegraphics[width=0.7\textwidth ]{scoring-en.pdf}](/problems/svampar/file/statement/en/img-0002.png)
Note that the x-axis is not linear.
If $R_{\max } \leq 9$, you get 100 points. The score values for $9 \leq R_{\max } \leq 20$ are also given in the table below.
|
$R_{\text{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 \neq 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 |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 0 1 2 2 |
2 p + 2 p + 4 p p < 2 + 4 |
