#1771 홍길주의 방법

41  1 s   128 MB  

Description

 

수학에서 두번 곱하여 A가 되는 수를 A의 제곱근이라고 한다. 제곱근은 땅의 넓이를 구하거나 이와 유사한 문제를 해결하기 위해서 널리 사용된다.
이에 동서양을 막론하고 제곱근을 구하기 위한 여러가지 방법이 고안되어 왔다. 조선시대 19세기 초 유학자이자 수학자인 홍길주는 나눗셈과 뺄셈만을 이용하여 제곱근을 구하는 매우 독자적이고도 창의적인 방법을 고안하였다.
이 방법은 독자적이고 창의적일 뿐만 아니라 수행하는데 있어서 매우 쉬운 풀이법을 그 특징으로 한다. 홍길주 스스로도 자신의 저서 ‘숙수념(孰遂念)’에서 “바보가 아닌 이상 어린아이들도 쉽게 할 수 있는 풀이법” 이라고 설명했다.
 
홍길주의 풀이법은 아래와 같다.
 
먼저 제곱근을 구할 수를 반으로 나누고 나눈 값을 1부터 오름차순으로 뺀다. 9의 경우 반으로 나눈 값 4.5에서 1을 빼고, 남은 값 3.5 에서 2를 빼는 식이다. 그렇게 더는 뺄 수 없을 때 남은 수를 2배한 뒤 그 수가 뺄 수와 같으면 제곱근이라는 것이다.
 
이 방법의 예시는 아래와 같다.
 
넓이가 441보인 정사각형 땅의 한 변의 길이를 구하라.
 
( 예제 출처 : http://www.donga.com/fbin/output?n=200703020120 )
 
위 문제에서는 우리는 실생활의 문제를 해결하는데 관심이 있기 때문에 양의 제곱근만을 구하도록 한다.

Input

입력은 여러개의 테스트 케이스로 주어지며, 입력의 첫 줄에는 테스트 케이스의 개수 T 가 입력으로 주어진다. ( 1 ≤ T ≤ 50 )

각 테스트 케이스는 한 줄에 하나의 숫자로 이뤄지며, 제곱근을 구해야 하는 정수 C 가 ( 1 ≤ C ≤ 200 ) 주어진다.

Output

각 테스트 케이스마다 제곱근을 구하는 중간 과정과 제곱근을 모두 출력하도록 한다. 각 테스트 케이스 처리 결과가 출력되기 직전에는 문자열 begin 을, 출력된 후에는 end 를 출력해주도록 한다.

단, 중간 계산 결과는 소숫점 두번째 자리에서 반올림해서 출력하도록 한다.

Sample Input

Sample Output

1
81
begin
40.5
39.5
37.5
34.5
30.5
25.5
19.5
12.5
4.5
9
end

Source

2011 Ajou University Programming Contest, Division 2