시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 45 | 18 | 13 | 40.625% |
3 × N개의 점이 찍혀있는 직사각형 그리드가 있다. 그리드 상의 모든 점은 최대 8개의 이웃한 점을 가지고 있다.
그리드 상의 점을 연결해서 만들 수 있는 다각형의 개수를 구하려고 한다. 다각형은 아래와 같은 조건을 만족해야 한다.
아래 그림은 N=6인 경우에 가능한 두 가지 다각형이다.
N이 주어졌을 때, 만들 수 있는 다각형의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에는 양의 정수 N이 주어진다. (N ≤ 1,000,000,000).
다각형의 만드는 방법의 수를 1,000,000,000로 나눈 나머지를 출력한다.
3
8
4
40
Olympiad > Baltic Olympiad in Informatics > BOI 2007 5번