전체 글

[16282] Black Chain

%2021. 11. 11. 16:04에 작성된 글입니다% https://www.acmicpc.net/problem/16282 16282번: Black Chain n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어 www.acmicpc.net 1. 고리를 \(n\)번 분리하면 \(w=1\)인 고리가 \(n\)개 생긴다. 2. \(w=1\)인 고리 뭉탱이로 만들 수 있는 최대 무게는 \(n\)이다. 3. 따라서 \(n+1\)짜리 고리가 있어야 그보다 더 무거운 무게를 구성할 수 있다. 4. \(w=n+1\)짜리 고리와 \(w=1\)인 고리를 모두 선택하면 무게..

[10436] 무한 유리수 트리

%2021. 11. 10. 01:32에 작성된 글입니다% https://www.acmicpc.net/problem/10436 10436번: 무한 유리수 트리 무한 유리수 트리는 완전 이진 트리이며, 다음과 같이 정의된다. 루트는 1/1이다. p/q의 왼쪽 자식은 p/(p+q)이다. p/q의 오른쪽 자식은 (p+q)/q이다. 트리의 첫 세 층은 아래와 같이 구성된다. 이 무한 www.acmicpc.net 루트까지 올라갔다 내려와서 편하게 해결 보려는 생각은 꿈도 꾸지 말자. \(O(N)\)이라도 범위가 2147483647인지라... 주어진 값에서 바로 해결을 봐야 한다. 대단한 알고리즘은 없고 그냥 어디 종이 가지고 와서 트리 죽 적어본 뒤에 규칙을 찾으면 된다. 대부분의 경우에 간단하게 해결이 되고, 주..

[13705] Ax+Bsin(x)=C

일단 태그에서부터 임의 정밀도/큰 수 연산이 붙어 있으니 고생 좀 해야 하겠다... 만! 이런 끔찍한 문제들은 보통 python의 Decimal로 해결한다. ​ c/cpp로 구현하는 것도 불가능한 건 아니고 실제로 적잖은 AC가 있긴 하다... 언제 따로 cpp bigint를 따로 구현해봐야겠다. ​ 꽤 높은 수준의 정밀도를 요구하는 문제기 때문에 기본적으로 지원하는 sin함수를 써서는 안 된다. 테일러 전개를 활용해 새로 함수를 짜야 한다. 파이 값도 중요해서 인터넷에서 몇백자리 긁어다 Decimal에 때려박았다. $Ax+B\sin x\ (A \geq B)$는 미분해서 보면 전체 구간에서 증가함을 알 수 있으므로 이분 탐색을 쓸 수 있다. Decimal로 잡고 st en mid 돌려가며 구했다. ​ 이..

[19577] 수학은 재밌어

%2021. 11. 9. 00:30에 작성된 글입니다% https://www.acmicpc.net/problem/19577 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net 오일러 피 함수라는 걸 여기서 처음 봤다. 대충 위키에서 본 내용에 따르면 이 함수는 아래의 성질을 갖는다고 한다. \(\gcd \left(a,b\right)=1\)일 때, \(\phi \left(ab\right)=\phi \left(a\right)\phi \left(b\right)\)​ \(\phi \left(p^n\right)=p^n\left(1-\frac{1}{p}\right)=p^{n-1}\left(p-1\right)\..

[1007] 벡터 매칭

%2021. 11. 5. 14:39에 작성된 글입니다% https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 풀어보려고 전부터 꽤 노력했는데 결국 고등학교 기하를 배우고 나서야 풀 수 있었다. 벡터의 성질을 맨바닥에서 끄집어낼 수준의 머리는 안 되는 모양이다. 주어진 점을 각각 \(P_1, P_2, P_3... P_n\)이라고 하자. 임의의 점 P를 하나 잡고, \(\overrightarrow{PP_1}, \overrightarrow{PP_..

[6734] Radio direction finder

%2021. 11. 5. 00:11에 작성된 글입니다% https://www.acmicpc.net/problem/6734 6734번: Radio direction finder A boat with a directional antenna can determine its present position with the help of readings from local beacons (radio transmitters). Each beacon is located at a known position and emits a unique signal. When a boat detects a signal, it rotates its anten www.acmicpc.net 평소에 Bronze 5 레이팅 문제는 시간 때우기..

[1160] Random Number Generator

%2021. 8. 22. 15:14에 작성된 글입니다% https://www.acmicpc.net/problem/1160 1160번: Random Number Generator 첫째 줄에 6개의 정수 m, a, c, X0, n, g (m, a, c, X0, n ≤ 1018, g ≤ 108)가 차례대로 주어진다. a, c, X0는 음이 아닌 정수이고 m, n, g는 양의 정수이다. www.acmicpc.net \(X_{n+1}=aX_n+c \mod M\) \(\mod M\)은 일단 나중에 계산하게 떼고 보면 다음과 같은 꼴이 된다. \(X_{n+1}=aX_n+c\)​ \(X_n\)의 일반항은 \(X_n=a^nX_0+c\left(1+a+...+a^{n-2}+a^{n-1}\right)\)​ 의 형태가 된다. ..

[21094] Discrete Logarithm is a Joke

%2021. 6. 29. 02:35에 작성된 글입니다% https://www.acmicpc.net/problem/21094 21094번: Discrete Logarithm is a Joke $M = 10^{18} + 31$ is a prime number. $g = 42$ is a primitive root modulo $M$, which means that $g^{1} \bmod M, g^{2} \bmod M, \ldots, g^{M-1} \bmod M$ are all distinct integers from $[1; M)$. Let's define a function $f(x)$ as the smallest positive integer www.acmicpc.net 이산 로그 100만번 구하는건가보다..