알고리즘/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)$ 이 주어진다. 각 테스트 케..
