27803번 - Pascal Walk 서브태스크스페셜 저지다국어채점 준비 중

Pascal's triangle consists of an infinite number of rows of an increasing number of integers each, arranged in a triangular shape.

Let us define (r, k) as the k-th position from the left in the r-th row, with both r and k counted starting from 1. Then Pascal's triangle is defined by the following rules:

• The r-th row contains r positions (r, 1), (r, 2), ..., (r, r).
• The numbers at positions (r, 1) and (r, r) are 1, for all r.
• The number at position (r, k) is the sum of the numbers at positions (r - 1, k - 1) and (r - 1, k), for all k with 2 ≤ k ≤ r - 1.

The first 5 rows of Pascal's triangle look like this:

In this problem, a Pascal walk is a sequence of s positions (r₁, k₁), (r₂, k₂), ..., (r_s, k_s) in Pascal's triangle that satisfy the following criteria:

• r₁ = 1 and k₁ = 1.
• Each subsequent position must be within the triangle and adjacent (in one of the six possible directions) to the previous position. That is, for all i ≥ 1, (r_{i + 1}, k_{i + 1}) must be one of the following that is within the triangle: (r_i - 1, k_i - 1), (r_i - 1, k_i), (r_i, k_i - 1), (r_i, k_i + 1), (r_i + 1, k_i), (r_i + 1, k_i + 1).
• No position may be repeated within the sequence. That is, for every i ≠ j, either r_i ≠ r_j or k_i ≠ k_j, or both.

Find any Pascal walk of S ≤ 500 positions such that the sum of the numbers in all of the positions it visits is equal to N. It is guaranteed that at least one such walk exists for every N.

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of a single line containing a single integer N.

For each test case, first output a line containing Case #x:, where x is the test case number (starting from 1). Then, output your proposed Pascal walk of length S ≤ 500 using S additional lines. The i-th of these lines must be ri ki where (r_i, k_i) is the i-th position in the walk. For example, the first line should be 1 1 since the first position for all valid walks is (1, 1). The sum of the numbers at the S positions of your proposed Pascal walk must be exactly N.

• 1 ≤ T ≤ 100.

• 1 ≤ N ≤ 501.

• 1 ≤ N ≤ 1000.

• 1 ≤ N ≤ 10⁹.

In Sample Case #1, only the starting position is needed.

In Sample Case #2, notice that although a shorter path exists, the path does not need to be of minimal length, as long as it uses no more than 500 positions.

The following image depicts our solution to Sample Case #3: