Description

I loved the part when she said “It’s cooking time!” And cooks everywhere, it really shows that she really cooks all the time.

Given a n x n board, each tile is either 1 or 0, you need to put n queens and count how many solutions are legal as the rules:

• 0 means you can put the queen in that tile.
• 1 means the tile is occupied, and we can't put the queen there.
•  Queens can't attack each other, therefore each row, column, and diagonal has only 1 queen.

For example, the answer of the sample input is 1 as the picture below speaks for itself. There is no other possible move.

Little help from the queen: use scanf("%1d") to scan 1 digit number.

Input

First line is an integer n (1 <= n <= 10)

The next n lines is the board state, each n digit, consist only number 1 and 0.

It's guaranteed that every row has atleast 1 number 0

Output

Output an integer with how many solution the input has.

Following with '\n'

Sample Input  Download

Sample Output  Download

Tags

Discuss

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  ≤10¹⁸

Output

Output the piece of the dragon curve

You can try to download the sample output as the output shown is not arrange perfectly

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Capybara-san really likes meat (vegan-friendly), so now he wants to gather a lot of meats and saves all of them in his tent.

He start from his tent (letter 'S') and want to gather all meat in the maze (letter 'M')
He can only bring one meat per trip and he wants to take all the meat to his tent.

• '.' is a path
• '#' is a wall
• 'S' is his tent
• 'M' is the meat

If Capybara-san is at position (x, y), then he can walk to:

• (x + 1, y)
• (x - 1, y)
• (x, y + 1)
• (x, y - 1)

​All 4 movements are counted by 1 step, and also valid if that position is not a wall

What is the smallest step does Capybara-san need to take to gather all the meat back to his tent?

The maze is made as:

• For every position (a, b) and (c, d), where (a, b) ≠ (c, d), there is only 1 path solution from (a, b) to (c, d) without overlapping path!

Sample IO Explanation:

 

HINT! LEGIT 100%

Input

The first input is X, and Y (X is row, Y is column) of the map
The next input is X * Y map,

5 <= X, Y <= 500
It's guaranteed that there is always S, M, and a path between that 2 points

Output

Output the steps, following with a newline

Sample Input  Download

Sample Output  Download

Tags

Discuss