시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 234 | 113 | 87 | 51.176% |
임의의 정수 i가 주어졌을 때, 어떤 수의 소수점 위 또는 아래 i째 자리 숫자를 계산하는 알고리즘이 존재한다면, 그러한 수를 "계산 가능한 수" (computable number)라고 한다.
반면에, 그러한 알고리즘이 존재하지 않는다면, 그러한 수를 "계산 불가능한 수" (uncomputable number)라고 한다. 예를 들어, 랜덤으로 생성된 프로그램이 무한 루프를 돌지 않을 확률을 나타내는 카이틴 상수 (Chaitin constant)는 계산 불가능한 수이다. 즉, 어떠한 알고리즘으로도 이 수를 임의의 정확도로 계산할 수 없다.
준석이는 분모와 분자가 자연수인 분수는 모두 계산 가능한 수인지 궁금해졌다. 준석이를 도와 a / b의 소수점 아래 i째 자리 숫자를 계산하는 알고리즘을 작성하여 모든 유리수가 계산 가능한 수임을 증명하자.
첫째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 100)
각 테스트 케이스의 첫째 줄에 정수 a와 b가 공백으로 구분되어 주어진다. (1 ≤ a, b ≤ 1018)
각 테스트 케이스의 둘째 줄에 정수 i와 n이 공백으로 구분되어 주어진다. (1 ≤ i ≤ 1018, 1 ≤ n ≤ 100)
각 테스트 케이스마다, a / b를 소수로 표현했을 때, 소수점 아래 i째 자리부터 (i + n - 1)째 자리까지 n개의 숫자를 출력하라.
소수를 표현하는 방법이 여럿 있는 경우에는, 소숫점 아래에 0이 무한히 많은 표현 방법을 선택한다.
1 1 7 1 6
142857
1 / 7 = 0.142857142857...에서 소수점 아래 1번째 자리부터 6개의 숫자는 142857이다.
2 1 625 2 7 3 1250 1 9
0160000 002400000
1 / 625 = 0.001600000...에서 소수점 아래 2번째 자리부터 7개의 숫자는 0160000이다.
3 / 1250 = 0.002400000...에서 소수점 아래 1번째 자리부터 9개의 숫자는 002400000이다.
1 295105340762488656 73766470618827515 165686182540289332 100
7647234964950876597705392951164898875222160879054875613327515544263303837362248466480172179521593664
University > 서강대학교 > 2019 Sogang Programming Contest > Champion E번