hackercupai/hackercup

1_The only difference between chapters 1 and 2 is the maximum allowed grid size, given in bold below._2 3A *Drizzle* program is a 2D grid of the following four types of cells:4 - '`@`' (start) \(-\) there is exactly one start cell in the entire grid5 - '`#`' (wall)6 - '`.`' (space)7 - '`*`' (instruction)8 9The program uses two registers \(A\) and \(B\) (both initially \(0\)), and executes as follows:10 111. Compute the minimum distance from the start to each instruction cell using orthogonal movements, without going outside of the grid or passing through any wall cells. Instruction cells that cannot be reached are ignored. 122. In increasing order, for each unique distance \(D\) such that there’s at least one instruction cell that’s at distance \(D\) from the start cell:13   2a. Count the number of shortest paths, \(P\), to all instruction cells of distance \(D\).14   2b. Look up the instruction corresponding to \((P \text{ mod } 2, D \text{ mod } 2)\) in the table below and modify one of the registers accordingly.153. At the end, the value in register \(A\) is outputted.16 17```18┌─────────────┬─────────────┬─────────────┐19│             │ D mod 2 = 0 │ D mod 2 = 1 │20├─────────────┼─────────────┼─────────────┤21│ P mod 2 = 0 │ A := A + 1  │ A := A - 1  │22│ P mod 2 = 1 │ B := B + A  │ A := B      │23└─────────────┴─────────────┴─────────────┘24```25 26For a given value \(K\), output any Drizzle program that outputs \(K\) when executed, with the restriction that **the program must fit on a \(\mathbf{10}\) × \(\mathbf{10}\) grid**.27 28 29# Constraints30 31\(1 \le T \le 2{,}000\)32\(0 \le K \le 10{,}000\)33 34 35# Input Format36 37Input begins with an integer \(T\), the number of test cases. For each case, there is a line containing the single integer \(K\).38 39 40# Output Format41 42For the \(i\)th case, output "`Case #i: `" followed by two integers \(R\) and \(C\), the number of rows and columns in your program, respectively. Then output your program. It must be exactly \(R\) lines long, with each line containing exactly \(C\) characters.43 44 45# Sample Explanation46 47Here are the instructions executed for each of the sample programs. Note that many other programs would be accepted for any for these cases.48 49In the first case, there is a single instruction. There are \(2\) shortest paths of length \(2\) to that instruction, so \(P = 2\) and \(D = 2\). That means we perform \(A := A + 1\). There are no more instructions, so the program ends and outputs \(1\).50 51In the second case, there are three instruction cells. Each of them are an even distance from the start, and each have an even number of shortest paths leading to them, so each represents \(A := A + 1\):52 531) \(2\) paths of length \(2\) \(\;(A := A + 1 = 1)\)542) \(4\) paths of length \(6\) \(\;(A := A + 1 = 2)\)553) \(4\) paths of length \(12\) \(\;(A := A + 1 = 3)\)56 57In the third case, there are eight instruction cells, but some of them are at the same distance as each other. In particular, there are two instruction cells at distance \(2\), and three instruction cells at distance \(10\). There's a single shortest path to each of the cells at distance \(2\), so in total there are \(2\) shortest paths to instructions at distance \(2\). One of the cells at distance \(10\) has a unique shortest path, and the other has two shortest paths, so in total there are \(3\) shortest paths to instructions at distance \(10\).58 591) \(2\) paths of length \(2\) \(\;(A := A + 1 = 1)\)602) \(6\) paths of length \(4\) \(\;(A := A + 1 = 2)\)613) \(1\) path of length \(6\) \(\;(B := B + A = 2)\)624) \(1\) path of length \(8\) \(\;(B := B + A = 4)\)635) \(3\) paths of length \(10\) \(\;(B := B + A = 6)\)646) \(3\) paths of length \(11\) \(\;(A := B = 6)\)65