알고리즘/codeforces
Codeforces Round #746 (Div. 2)-B. Hemose Shopping
문제 설명 핫산에게 정수 $n$개로 이루어진 배열이 주어진다. 핫산은 그의 친구 나비한테 이 배열을 오름차순으로 만들어야 한다고 말했다. 하지만 이 뿐이라면 문제가 너무 쉬워지기 때문에 정렬을 할 때 오직 다음 연산만을 사용해야 한다는 제약을 추가했다. $1 \le i,j \le n$, $|i - j| \ge x$ 를 만족하는 index $i$와 $j$를 선택하고, 그 다음 $a_i$와 $a_j$의 위치를 바꾼다. 우리가 해야할 것은 나비가 위에서 주어진 연산을 사용해서 배열을 오름차순으로 만들 수 있는지 판별하는 것이다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^5)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 두 정수 $n$과 $x (2 \le n \le x..
알고리즘/codeforces
Codeforces Round #746 (Div. 2)-A. Gamer Hemose
문제 설명 핫산은 블리자드의 최신 망한 게임 발로란트를 즐기고 있다. 발로란트에는 $n$개의 무기가 주어지고, $i$번재 무기의 데미지 값은 $a_i$로 주어진다. 그리고 핫산이 무찔러야 하는 적의 체력은 $H$로 주어진다. 핫산은 적이 죽을 때 까지 한번 혹은 여러번 행동을 취할 수 있다. 한번의 행동에서 핫산은 무기를 1개 선택할 수 있고, 무기의 공격력으로 적의 체력을 깎을 수 있다. 적은 적의 체력이 0이거나 0보다 작아지면 죽는다. 그러나 세상은 간단하지 않다. 핫산은 같은 무기를 연속으로 2회 선택할 수가 없다. 핫산이 적을 죽이기 위해서 무기를 선택해야하는 최소 횟수는 무엇일까? Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^5)$ 이 주어진다. 각 테스트 케..
알고리즘/codeforces
Educational Codeforces Round 114 (Rated for Div. 2)-C. Slay the Dragon
문제 설명 커리는 소설을 쓰고 싶다. 커리는 진짜 이상한 작가인데 오직 문자 'a', 'b', 'c', 'd', 'e'만 사용한다. 이야기를 구성하기 위해서 커리는 주어진 소문자만으로 이루어진 단어 $n$개를 작성했다. 커리는 재밌는 이야기를 만들기 위해서 선택해야 하는 최대 단어수를 구해야 한다. 단어를 선택하는 순서는 중요하지 않다. 이야기를 구성하는 모든 단어에 있는 5개의 문자중 한 문자의 개수가 다른 4개의 모든 문자의 개수 총합보다 큰 경우가 있으면 이 이야기는 흥미로운 이야기라고 한다. 예를 들어 이야기가 3단어 "bac", "aaada", "e"로 이루어져 있다면 이 이야기는 흥미로운 이야기이다. 왜냐하면 단어 'a'가 5번 나타났고, 다른 모든 단어가 총 4번 나타났기 때문이다. 그러나 ..
알고리즘/codeforces
Educational Codeforces Round 114 (Rated for Div. 2)-B. Combinatorics Homework
문제 설명 당신에게 4개 정수 $a$, $b$, $c$ 와 $m$가 주어진다. 다음 조건을 만족하는 문자열이 존재하는지 확인하는것이 문제이다. $a$개의 'A'문자 $b$개의 'B'문자 $c$개의 'C'문자 다른 문자는 없다. 정확히 인접한 문자가 같은쌍이 $m$개 있어야한다. ($i$번째 문자열과 $(i+1)$번째 문자열이 같은 쌍이 정확히 $m$개가 있어야한다.) Input 첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 10^4)$ 다음 t개의 줄에는 각 4개의 정수 $a, b, c$와 $m$이 주어진다. $(1 \le a, b, c \le 10^8, 0 \le m \le 10^8)$ Output 각 테스트케이스마다 위에서 ..
알고리즘/codeforces
Educational Codeforces Round 114 (Rated for Div. 2)-A.Regular Bracket Sequences
문제 설명 소괄호 수열은 소괄호 "("와 ")"로 이루어져있는 문자열이다. 정규 소괄호 수열은 원래 문자열사이에 "1"과 "+"를 넣어서 올바른 수학적 연산 표현으로 바꿀 수 있는 소괄호 수열을 말한다. 예를 들어 소괄호 수열 "()()"과 "(())"은 정규이다. (결과 수식은 각각 "(1) + (1)"과 "((1 + 1) + 1)"이다.) 그리고 ")(", "(", ")"은 정규가 아니다. 당신에게 정수 $n$이 주어진다. 당신의 목표는 길이가 $2n$개인 완전히 다른 $n$개의 정규 소괄호 수열을 구하는 것이다. Input 첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 50)$ 각 테스트케이스에 정수 $n$이 주어진다. $(1 \le n \le 50)$ Output..
알고리즘/codeforces
Codeforces Round #743 (Div. 2)-C. Book
문제 설명 $n$개 챕터로 이루어진 책이 있다. 각 챕터는 이해하기 위해서 필요한 다른 챕터의 목록이 있다. 이 목록에 있는 모든 챕터를 읽어야만 이 챕터를 읽고 이해할 수 있다. 현재 당신은 아무 챕터도 이해하지 못한상태이다. 당신은 처음부터 끝까지 책을 반복해서 읽을 것이고, 책에 있는 모든 챕터를 다 이해할때까지 이 과정을 반복한다. 당신이 한 챕터를 읽을때, 그 챕터를 이해하기 위한 목록에 있는 챕터를 모두 읽지 않았다면 당신이 읽은 챕터는 이해한 것이 아니다. 책에 있는 모든 챕터를 이해하기 위해서 반복해서 읽어야하는 책의 최소 횟수를 구해야한다. 혹은 책을 몇번이라도 읽더라도 모든 챕터를 절대로 이해할 수 없는지 결정해야한다. 입력 이 문제는 다수의 테스트케이스가 주어진다. 첫번째 줄에는 테스..
