Cantor – Kattis, Kattis
Hide Cantor Georg Cantor (public domain) The ternary expansion of a number is that number written in base $3$. A number can have more than one ternary expansion. A ternary expansion is indicated with a subscript $3$. For example, $1 = 1_{3} = 0.222\ldots _
open.kattis.com
0 이상 1 이하의 실수가 주어질 때 해당 수가 cantor set에 속하는지 판단하는 문제이다.
이때 입력은 소수점 아래 6자리까지 주어진다.
우선 0과 1을 제외한 모든 입력에 대하여 해당 수의 3진수 표기는 순순환소수이다.
증명은 나무위키를 참고하자.
그리고 어떤 실수 x가 cantor set에 속한다면 x / 3도 cantor set에 속한다.
가능한 상태의 수는 (1e6 + 1)개이고 각 상태에서의 전이는 유일하다.
현재 상태를 x라고 하면 다음 상태 y는 아래와 같이 정의된다.
y = 3 * x - min(3 * x / 1e6, 2) * 1e6;
초기 상태로 복귀할 때까지 조건을 만족하는지 검사하면 된다.
정해는 그래프로 모델링한 후 bfs를 돌린다.
테스트 케이스가 적고 모든 입력에 대하여 최대 30번만 검사하면 되기 때문에 굳이 필요하지는 않다.
끝
'일기 (사실 근황임)' 카테고리의 다른 글
| BOJ 26248번 - 겨울 숲의 수호자 (0) | 2022.12.17 |
|---|---|
| ACM-ICPC World Finals 2015 H - Qanat (0) | 2022.12.10 |
| CP4 Chapter 2. Data Structures and Libraries (0) | 2022.11.21 |
| solved.ac CLASS 7 구간 트리 문제 정리 (0) | 2022.11.08 |
| solved.ac CLASS 6 구간 트리 문제 정리 (2) | 2022.11.07 |
