알고리즘/codeforces
Codeforces Round #739 (Div. 3)-C. Infinity Table
문제 설명 재혁은 무한개의 수가 적혀있는 표를 가지고 있다. 이 표의 행과 열 모두 1부터 시작한다. 표의 초기상태는 아무것도 적혀있지 않다. 그 이후 좌상단에 1을 적으면서 시작한다. 그 이후 표에는 다음과 같은 방식으로 수를 적어나간다. 재혁의 친구는 자신이 가장 좋아하는 숫자 $k$를 가지고 있다. 그는 이 수가 재혁이 가지고 있는 표에서 어느 위치에 있는지 알고 싶다. 재혁이의 친구가 $k$가 위치한 행과 열을 찾을 수 있게 도와주자. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 위치를 반드시 찾아야 하는 정수 $k(1 \le k \le 10^9)$ 가 주어진다. Output 각 테스트케이스마다 표에서 $k$..
알고리즘/codeforces
Codeforces Round #739 (Div. 3)-B. Who's Opposite?
문제 설명 짝수명의 사람이 원형으로 서있다. 각 사람의 번호는 1부터 시계방향으로 차례대로 부여한다. 각 사람은 서로 원의 중심 방향을 향해 바라보고 있으며, 반대편 사람을 지켜본다. 당신은 한 원에 몇명의 사람이 서있는지 모른다.(하지만 수는 반드시 짝수다.) 우리가 알고 있는 사실은 사람 $a$가 사람 $b$를 마주보고 있는 상태라는 것이다. 그렇다면 $a, b$와는 다른 수 $c$가 주어졌을 때, $c$가 마주보고 있는 사람은 어떤 수를 가지고 있는 사람일까? 만약 $a, b, c$로 원이 만들어지지 않는다면 $-1$을 출력한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 서로 다른 세 정수 $a, b, c ..
알고리즘/codeforces
Codeforces Round #739 (Div. 3)-A. Dislike of Threes
문제 설명 효수는 3으로 나누어떨어지거나 정수의 맨 뒷자리수가 3인 정수를 매우 싫어한다. 민수는 효수가 좋아하는 수를 1부터 큰 순서대로 차례로 쓰고있다. $1, 2, 4, 5, 7, 8, 10, 11, 14, 16, ...$ 우리가 해야할 것은 이 수열의 $k$번째 수를 찾는 것이다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 100)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 정수 $k (1 \le k \le 1000)$ 가 주어진다. Output 각 테스트케이스마다 민수가 쓴 수열의 $k$번째 수를 의미하는 정수 $x$를 출력한다. Example input 10 1 2 3 4 5 6 7 8 9 1000 output 1 2 4 5 7 8 10 11 14 1666..
알고리즘/codeforces
Codeforces Round #741 (Div. 2)-C. Rings
문제 설명 수인은 길이가 $n$인 문자열 $s$를 생각하고 있다. 수인은 마법의 함수 $f$를 알고있다. 이 함수는 이진수로 나타낸 문자열을 입력으로 받고 이진수를 십진수로 바꾼 값을 출력으로 한다. 예를 들면 $f(001010) = 10, f(111) = 7, f(11011101) = 221$ 그러나 수인은 다음 조건을 만족하는 두 개의 정수로 이루어진 2쌍 $(l_1, r_1), (l_2, r_2)$을 구하고 싶다. $1 \le l_1 \le n,; 1 \le r_1 \le n,; r_1 - l_1 + 1 \le [\frac{n}{2}]$ $1 \le l_2 \le n,; 1 \le r_2 \le n,; r_2 - l_2 + 1 \le [\frac{n}{2}]$ $(1_1, r_1)$ 과 $(l_2,..
알고리즘/codeforces
Codeforces Round #741 (Div. 2)-B. Scenes From a Memory
문제 설명 당신은 최면 단계에서 갑자기 각 자리수가 0이 포함되지 않는 양의 정수 $n$이 떠올랐다. 최면을 끝내고 집에 돌아오는 길에 당신은 문득 이런 생각이 들었다. 최종 결과가 소수가 아니게 하기 위해서 지워야하는 숫자 개수가 최대 몇개일까? 여기서 말하는 소수는 1과 합성수들을 의미한다. 몇가지 숫자는 소수가 아니게 만들 수 없는데, 예를들어 $53$ 같은 경우는 $5$나 $3$ 모두를 지워도 소수이기 때문이다. 그러나 이 문제에 있는 모든 $n$은 정수 몇개를 지워서 반드시 소수가 아닌 수를 얻을 수 있다는걸 보장한다. 모든 숫자를 지울수 없다는 점에 유의하자. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^3)$이 주어진다. 각 테스트 케이스의 첫번째 줄에는 주..
알고리즘/codeforces
Codeforces Round #741 (Div. 2)-A. The Miracle and the Sleeper
문제 설명 두 정수 $l$, $r$이 주어진다.$(l \le r)$ $r \ge a \ge b \ge l$ 을 만족하는 $(a, b)$쌍 중에서 $a mod b$의 값이 최대가 되는 쌍을 찾아라. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$이 주어진다. 각 테스트 케이스는 두 정수 $l, r(1 \le l \le r \le 10^9)$ 가 주어진다. Output 각 테스트케이스마다 문제에 맞는 답을 출력한다. Example input 4 1 1 999999999 1000000000 8 26 1 999999999 output 0 1 12 499999999 문제 접근 사용한 알고리즘: 구현, 수학, 정수론 걸린 시간 : 00:04 A번 답게 조금만 생각하면 풀 수 있..
