Description
Frieren wants to become a Dragon Warrior, like Po
As she determines to become one, she needs to learn the "Dragon Curve" kung fu style
What is Dragon Curve?
This is a Dragon Curve (Wikipedia)
Initially, there is only 1 stick
The next pattern is copying the previous pattern and rotating by 90 degree
As the pattern can go infinte, we can calculate what the patterns will be in a certain position
Question :
Let every stick length be 3x1, black boxes, and based on the dragon curve pattern, let :
- Index 1 is the first stick of the pattern,
- Index 2 is the second stick of the pattern,
- Index 3 is the third stick of the pattern,
- and so on ... until infinity
Given the pattern length is n and the pattern start at index s,
You need to draw the dragon curve start from index s until index s + n - 1, as the length of the pattern is n in the 2d array
The '#' indicates the pattern (Black), while the blank is '.' represents the blank (White)
The drawing must fit perfectly in the array, which means:
- The given pattern must fully be shown in the array
- The most left/right column and most up/down row can't be a blank row/column
Sample IO Explanation :
Note #1: If the gray box is inside the array, leave it as white '.'
Note #2: Beware of the size of the input, the starting index could be very large!
Click this link if you need a HINT! (Click only if you are desperate!)
Input
Input is 2 integers, n and s
1 ≤ n ≤ 2000
1 ≤ s ≤1018
Output
Output the piece of the dragon curve
You can try to download the sample output as the output shown is not arrange perfectly