PS 이야기

문제 및 채점: 사이트 A. New Elements: Part 1 질량이 X인 원소 C가 있고, 질량이 Y인 원소 J가 있다. 분자 N개가 있는데, i번째 분자에 포함된 원소 C의 개수는 C[i]개고, 포함된 원소 J의 개수는 J[i]개다. 원소 C와 원소 J 이외에 다른 원소는 포함되어 있지 않다. 분자를 질량 순서대로 정렬하려고 한다. 다만, 분자의 질량은 모두 달라야 한다. 이때, 정렬 결과로 가능한 순서는 모두 몇 개인지 구하는 문제다. 서로 다른 i와 j에 대해, C[i] ≤ C[j], J[i] ≤ J[j]를 만족하면 질량 X, Y와 상관없이 질량의 대소 관계가 명확하다. 다만, C[i] < C[j], J[i] > J[j]와 같이 원소 C 개수의 대소 관계와 원소 J 개수의 대소 관계가 뒤집혀있..

참고자료: 위키백과 Stern-Brocot 트리는 모든 양의 유리수가 정점과 일대일이 되는 무한한 완전 이진트리다. 또한, 이진탐색트리처럼 왼쪽에서 오른쪽 방향으로 탐색 가능하다. 연분수에 의한 트리 양의 유리수는 $q$ 는 아래와 같은 연분수 꼴로 표현할 수 있고, 이를 수열 $a$로도 표현할 수 있다. $q = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_k}}}} = [a_0; a_1, a_2, \dots, a_k]$ 여기서 $k$와 $a_0$는 음이 아닌 정수고, 나머지 $a_i$는 양의 정수다. 이러한 표현은 유일하지 않은데 다음과 같이 수열의 맨 끝 $a_k$가 $1$일 때는 중복이 있기 때문이다. $[a_0; a_..

문제: 공식 홈페이지채점: Yandex 1. doll 0번 정점을 시작점이라고 부르고 0번 정점은 나가는 간선이 정확히 1개다. 1번부터 M번까지 번호가 매겨진 나가는 간선이 정확히 1개인 트리거 정점 M개가 존재한다. 그리고 스위치라고 불리는 정점들은 번호가 음수로, 개수가 S개일 때, -1번부터 -S번까지 번호가 매겨진다. 스위치 정점은 나가는 간선이 정확히 2개이며 스위치 상태가 'X'일 때는 'X'로 표시된 간선으로 나가게 되며, 스위치 상태가 'Y'일 때는 'Y'로 표시된 간선으로 나가게 된다. 정점을 나가면서 동시에 스위치 정점의 상태가 뒤집힌다. 초기 0번 정점에서 이동을 시작하며, 이동을 하다가 다시 처음 0번 정점으로 돌아오는 순간 모든 스위치 정점의 상태는 'X'여야하며 트리거 정점은 ..