(Challenge) Sebi and CPU Design

All submissions for this problem are available.
### Read problem statements in [Mandarin Chinese](http://www.codechef.com/download/translated/SEPT19/mandarin/SEBICPU.pdf), [Bengali](http://www.codechef.com/download/translated/SEPT19/bengali/SEBICPU.pdf), [Russian](http://www.codechef.com/download/translated/SEPT19/russian/SEBICPU.pdf), and [Vietnamese](http://www.codechef.com/download/translated/SEPT19/vietnamese/SEBICPU.pdf) as well. The King of Chefland is a fan of triplets, especially Pythagorean triplets. His son, prince Sebi, designed the first CPU of Chefland. Nobody wants to argue with the son of the king, so everybody agrees that he is a great hardware designer. However, he forgot a lot of important instructions, like assigning a constant to a register. Chefland is now looking for a programmer who can load some given triplets to registers quickly. **Architecture of Sebi's CPU:**  There are four 64bit registers based on the [X64 architecture](https://docs.microsoft.com/enus/windowshardware/drivers/debugger/x64a...). These registers are named `rax`, `rbx`, `rcx` and `rdx`.  Parts of each 64bit register can be used as smaller registers. For `y` equal to `a`, `b`, `c` or `d`, we have the following registers:  `eyx`: the lower (least significant) 32 bits of `ryx`  `yx`: the lower 16 bits of `ryx`  `yl`: the lower 8 bits of `ryx`  `yh`: the upper 8 bits of `yx`  The CPU cannot access any memory storage other than these registers.  The CPU supports several instructions based on assembly languages. Each instruction takes one or two registers as operands. Immediate values as operands are not supported. If an instruction takes two operands, they do not have to be distinct.  If an instruction takes two operands, they must have registers with the same width (number of bits). When the operands of an instruction are registers with width $b$, the values stored in them are treated as unsigned $b$bit integers.  An instruction on registers with width $b$ computes a result ― an unsigned $b$bit integer ― and stores it in the register given as the first operand. In case of overflow or underflow, the result is treated as computed modulo $2^b$; all bits outside the firstoperand register remain unchanged.  The available oneoperand instructions and their results are:  `dec reg`: `reg` minus $1$  `inc reg`: `reg` plus $1$  `not reg`: bitwise NOT of `reg`  The available twooperand instructions and their results are:  `and reg1 reg2`: bitwise AND of `reg1` and `reg2`  `or reg1 reg2`: bitwise OR of `reg1` and `reg2`  `xor reg1 reg2`: bitwise XOR of `reg1` and `reg2`  `shl reg1 reg2`: `reg1` shifted left by `reg2` bits (and inserts `reg2` $0$s as the least significant bits)  `shr reg1 reg2`: `reg1` shifted right by `reg2` bits (and inserts `reg2` $0$s as the most significant bits)  `add reg1 reg2`: `reg1` plus `reg2`  `sub reg1 reg2`: `reg1` minus `reg2`  `mul reg1 reg2`: `reg1` multiplied by `reg2`  `div reg1 reg2`: `reg1` divided by `reg2` (integer division)  `mod reg1 reg2`: `reg1` modulo `reg2` (remainder of `reg1` after division by `reg2`)  `mov reg1 reg2`: `reg2` (the instruction copies the value of `reg2` to `reg1`)  The only operations where the result could overflow are `shl`, `add`, `sub`, `mul`, `inc` and `dec`. In `sub` and `dec`, the result of $ij$ modulo $2^b$ for $j \gt i$ is $2^b + i  j$. In all other instructions, modulo simply corresponds to discarding all except the least significant $b$ bits.  It is not allowed to use the `div` or `mod` operation if `reg2` contains $0$. Initially, all four registers contain $0$s. You are given $N$ triplets of 64bit integers $(a_1, b_1, c_1), (a_2, b_2, c_2), \ldots, (a_N, b_N, c_N)$ and you should write a program (a sequence of instructions) such that each triplet appears in the registers at some point during the execution of this program. The order in which they appear does not matter. Formally, for each valid $i$, there should be an instruction in your program such that **immediately** after this instruction is executed, one of the registers contains the value $a_i$, one contains $b_i$ and one contains $c_i$ (the fourth register may contain anything). ### Input  The first line of the input contains a single integer $N$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains three spaceseparated integers $a_i$, $b_i$ and $c_i$. ### Output  First, print a line containing a single integer $P$ ― the number of instructions in your program.  Then, print $P$ lines. For each valid $i$, the $i$th of these lines should contain the $i$th instruction from your program in the format described above. ### Constraints  $N = 64$  $0 \le a_i, b_i, c_i \lt 2^{64}$ for each valid $i$  $a_i \neq b_i$, $b_i \neq c_i$, $a_i \neq c_i$ for each valid $i$ ### Scoring If your program attempts to divide anything by zero or compute anything modulo zero, your submission will receive the Wrong Answer verdict. If $P$ exceeds $N \cdot 500$, your submission will also receive the Wrong Answer verdict. Otherwise, the score of your program is equal to $P$. Your goal is to minimise this number. There are ten test files. During the contest, the displayed score will account for exactly three test files. However, if your program gets a nonAC verdict on any test file, your submission's verdict will be nonAC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the other 7 test files. ### Generation There are five types of test files and two files of each type.  Type 1: Each triplet is chosen uniformly randomly among all valid triplets.  Type 2: For each valid $i$:  $a_i$ is chosen uniformly randomly among all 64bit integers which contain at least 25 0bits and at least 25 1bits.  $b_i$ and $c_i$ are chosen uniformly randomly among all pairs of distinct 64bit integers which only differs from $a_i$ in one or two bits.  Type 3: For each valid $i$:  If $i = 1 + 8k$ for some integer $k$, an unsigned integer $d$ ($1 \le d \lt 2^{63}$) is chosen uniformly randomly. This integer is used for this triplet and the next seven triplets.  First, $a_i$ is chosen uniformly randomly; $b_i = a_i + d$ and $c_i = a_i + 2d$. If $c_i \ge 2^{64}$, $a_i$ is chosen uniformly randomly again and $b_i$ and $c_i$ are updated.  This process is repeated until $c_i \lt 2^{64}$.  Type 4:  First, three 64bit unsigned integers are chosen uniformly randomly and assigned to three registers. The fourth register is unused; we may assume that it does not exist. Consider the following program which generates a list $L$:  If $L$ contains $9N$ integers, terminate.  Randomly choose two registers in some order. Randomly choose to use the whole registers or their lower 32 bits.  Randomly choose one of the instructions `xor`, `and`, `or`, `add` or `sub` and execute it with the chosen registers as operands.  Add the values in the three registers (in a fixed order) to the list $L$.  Consider every third element of the list $L$. The first three of these integers form the first triplet, the next three form the second triplet and so on.  While any triplet contains two equal elements, this process is repeated and the triplets regenerated.  Type 5:  A 64bit unsigned integer $K$ is chosen uniformly randomly.  Each triplet is chosen uniformly randomly among all valid triplets with sum of all three elements equal to $K$. ### Example Input 1 ``` 3 255 2 4 1 0 3 2 6 3 ``` ### Example Output 1 ``` 10 dec al inc rcx inc ecx mov rdx rcx add rcx rdx add rcx rdx mov rbx rcx div rbx rdx div rdx rdx div rcx rax ``` ### Example Input 2 ``` 1 18446743995541146810 18446743995541146811 18446743995541146809 ``` ### Example Output 2 ``` 13 dec ebx add bx bx mul rbx rbx not ebx sub eax ebx div ebx eax mul ebx ebx sub ebx eax mul rax rbx mov rdx rax dec rax mov rbx rax dec rbx ``` ### Explanation Note that $N \neq 64$ to keep the input short. This constraint holds for all input files. **Example case 1:** The 64bit values stored in the registers `(rax, rbx, rcx, rdx)` after each instruction is executed are as follows: ``` dec al (255, 0, 0, 0) inc rcx (255, 0, 1, 0) inc ecx (255, 0, 2, 0) mov rdx rcx (255, 0, 2, 2) add rcx rdx (255, 0, 4, 2) ― the first triplet appears add rcx rdx (255, 0, 6, 2) mov rbx rcx (255, 6, 6, 2) div rbx rdx (255, 3, 6, 2) ― the third triplet appears div rdx rdx (255, 3, 6, 1) div rcx rax (255, 3, 0, 1) ― the second triplet appears ```Author:  iscsi 
Tags  iscsi 
Date Added:  26082019 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 