알고리즘/codeforces
Codeforces Round #747 (Div. 2)-B. Special Numbers
문제 설명 지우는 양의 정수로 이루어진 수열을 매우 좋아한다. 따라서 지우의 선생님인 혜린은 지우에게 오직 특별한 숫자로만 이루어진 수열에 관한 문제를 냈다. 서로 다른 음이 아닌 $n$의 제곱수의 합으로 양의 정수를 나타낼 수 있으면 그 수를 특별하다고 한다. 예를 들어 $n = 4$ 일때 $17$은 특별하다. 왜냐하면 $4^0 + 4^2 = 1 + 16 = 17$ 로 표현 할 수 있기 때문이다. 하지만 $9$ 는 그렇지 않다. 지우는 특별한 수가 오름차순으로 정렬되어있는 수열 중에서 $k$번째 수를 구해야한다. 이 숫자는 매우 크기 때문에 값을 $10^9 + 7$ 로 나눈 나머지값을 구한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트..
알고리즘/codeforces
Codeforces Round #747 (Div. 2)-A. Consecutive Sum Riddle
문제 설명 지우는 정수에게 수수께끼를 냈다. 정수 $n$이 있는데, 우리가 구해야 할 것은 $-10^{18} \le l < r \le 10^{18}$ 과 $l + (l + 1) + ... + (r - l) + r = n$ 을 만족하는 두 정수 $l$과 $r$을 구해야 한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 정수 $n (1 \le n \le 10^{18})$이 주어진다. Output 각 테스트케이스마다 $-10^{18} \le l < r \le 10^{18}$ 과 $l + (l + 1) + ... + (r - l) + r = n$ 을 만족하는 두 정수 $l$과 $r$을 출력한다. 답이 여러개 있으면 아무거..
알고리즘/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 각 테스트케이스마다 위에서 ..
