E D R , A S I H C RSS

How Many Pieces Of Land?

원문보기
----
인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:2(1~4)

About HowManyPiecesOfLand?

타원 모양의 땅이 주어져 있는데, 그 땅의 테두리에 n개의 점을 임의로 선택한다. 그리고 나서 각 점들을 다른 모든 점과 직선으로 연결하면 n(n-1)/2 개의 선이 만들어진다. 이 때 테두리 위의 점을 잘 선택해서 나뉘어지는 땅의 개수가 최대가 되도록 만들면 몇 개의 조각으로 나눌 수 있을까? 다음은 n = 6 일 때 땅을 나눠놓은 모습이다.
http://online-judge.uva.es/p/v102/p10213.jpg

Input

파일의 첫번째 줄에는 테스트 케이스를 나타내는 0 보다 크고 3,511 보다 작은 정수 s가 입력된다. 그 다음 줄부터 s 개의 줄에 걸쳐서 0 이상, 2<sup>31</sup> 미만의 정수 n이 입력된다.

Output

각 테스트 케이스에 대해 n개의 점을 이은 직선에 의해 나뉘는 땅의 최대 개수를 출력한다. 한 줄에 하나씩의 결과만 출력한다.

Sample Input

{{| 4
1
2
3
4 |}}

Sample Output

{{| 1
2
4
8 |}}

풀이

작성자 사용언어 개발시간 코드
문보창 C++ 7시간 HowManyPiecesOfLand?/문보창
하기웅 C++ 3시간 HowManyPiecesOfLand?/하기웅

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.3068 sec