알고리즘/codeforces
Codeforces Round #743 (Div. 2)-C. Book
문제 설명 $n$개 챕터로 이루어진 책이 있다. 각 챕터는 이해하기 위해서 필요한 다른 챕터의 목록이 있다. 이 목록에 있는 모든 챕터를 읽어야만 이 챕터를 읽고 이해할 수 있다. 현재 당신은 아무 챕터도 이해하지 못한상태이다. 당신은 처음부터 끝까지 책을 반복해서 읽을 것이고, 책에 있는 모든 챕터를 다 이해할때까지 이 과정을 반복한다. 당신이 한 챕터를 읽을때, 그 챕터를 이해하기 위한 목록에 있는 챕터를 모두 읽지 않았다면 당신이 읽은 챕터는 이해한 것이 아니다. 책에 있는 모든 챕터를 이해하기 위해서 반복해서 읽어야하는 책의 최소 횟수를 구해야한다. 혹은 책을 몇번이라도 읽더라도 모든 챕터를 절대로 이해할 수 없는지 결정해야한다. 입력 이 문제는 다수의 테스트케이스가 주어진다. 첫번째 줄에는 테스..
알고리즘/codeforces
Codeforces Round #743 (Div. 2)-B. Swaps
개인적으로 div2의 b번 문제로는 너무 어려웠다는 느낌을 받았었는데, 아니나 다를까 난이도 1400문제 였다... 열심히 공부해야지 문제설명 길이가 $n$인 두 배열 $a$, $b$가 있다. 배열 $a$에는 $1$ 부터 $2n$까지 홀수 정수가 무작위로 중복되지 않게 있고, 배열 $b$에는 $1$ 부터 $2n$까지 짝수 정수가 무작위로 중복되지 않게 있다. 당신은 다음 연산을 사용할 수 있다. 두 배열중 하나를 선택한다. $1$ 부터 $n - 1$까지 index중 하나를 선택한다. 선택한 배열의 $i$번째 값과 $i+1$번째 값을 바꾼다. 우리의 목표는 a가 b보다 사전순으로 작은 배열이 되게 만드는 최소 연산의 수를 구해야한다. 두 배열의 $x$와 $y$의 길이가 같을때, 배열 $x$의 첫번째 원소가..
알고리즘/codeforces
Codeforces Round #743 (Div. 2) - A. Countdown
문제 설명 당신은 $n$ 자리 정수를 나타낼 수 있는 전자 시계를 가지고 있다. 각 자리는 $0$부터 $9$까지 정수를 표현할 수 있다. 그래서 모든 시계는 $0$부터 $10^{n} - 1$까지의 수를 표현한다. 이 시계는 만약 숫자가 $10^{n - 1}$보다 작으면 $0$으로 시작할 수 있다. 당신은 가능한 한 지시사항을 적게 사용해서 시계에 0이 나타나게 하고 싶다. 지시사항은 다음과 같고, 한번에 하나씩 수행할 수 있다. 시계의 숫자를 $1$ 줄인다. 두 숫자의 자리를 바꾼다. (어떤 자리수의 숫자를 바꿀 수 있을지 선택할 수 있으며, 이 두 숫자는 인접하지 않아도 된다.) 당신의 목표는 위에 적힌 지시사항을 최소로 사용해서 시계가 $0$이 나타나게 하는 것이다. Input 이 문제는 여러개의 테..
