시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 16 | 14 | 13 | 86.667% |
A number from 1 to n is inscribed in each cell of a 2 × n grid in such a way that each number appears exactly twice in the grid and each column contains two different numbers. An example of such a configuration is depicted below.
We would like to colour each of the cells white or gray in such a way that cells located in the same column receive different colours and cells containing same number receive different colours. An example of such a colouring of the grid from the previous figure is depicted below.
How many such colourings exist?
The first line of the standard input contains one integer n (2 ≤ n ≤ 100). Each of the following two lines contains n integers in the range [1, n], separated by single spaces. The numbers in these lines represent numbers inscribed in consecutive cells of the grid.
The first and only line of the standard output should contain a single integer - the number of different colourings of the grid with two colours that fulfill the described conditions.
5 1 5 3 1 5 4 2 2 4 3
4
Please note that the example describes the grid from the above figures.
Contest > Algorithmic Engagements > PA 2009 7-3번