To the Expert

문제 설명 당신에게 정수 $n$이 주어진다. 우리는 다음 행동중에서 한가지를 선택해서 할 수 있다. 숫자에서 아무 자릿수를 지운다. (이 행동은 숫자가 1자리 일때에서 수행 가능하며 이 연산이 끝나면 숫자는 "공백"이다.) 한 자리 숫자를 맨 오른쪽에 붙인다. 이 행동은 마음대로 수행할 수 있고, 몇번이든 수행할 수 있다. 주의해야 할 점은 아무 자릿수를 지울때 0이 맨 앞으로 나올 수 있는데, 이 0은 지울 수 없다. 만약 숫자 $301$이 주어질 때, 숫자 $3$을 지우면 결과가 $01$가 된다. ($1$이 아니다.) 우리는 주어진 숫자에 최소 연산을 수행해서 2의 제곱수인 $2^k(k \ge 0)$로 만들어야 한다. 최종 결과로 나오는 수는 반드시 $0$이 맨 앞에 나오면 안된다. 예를 들어 $n ..

문제 설명 재혁은 무한개의 수가 적혀있는 표를 가지고 있다. 이 표의 행과 열 모두 1부터 시작한다. 표의 초기상태는 아무것도 적혀있지 않다. 그 이후 좌상단에 1을 적으면서 시작한다. 그 이후 표에는 다음과 같은 방식으로 수를 적어나간다. 재혁의 친구는 자신이 가장 좋아하는 숫자 $k$를 가지고 있다. 그는 이 수가 재혁이 가지고 있는 표에서 어느 위치에 있는지 알고 싶다. 재혁이의 친구가 $k$가 위치한 행과 열을 찾을 수 있게 도와주자. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 위치를 반드시 찾아야 하는 정수 $k(1 \le k \le 10^9)$ 가 주어진다. Output 각 테스트케이스마다 표에서 $k$..

문제 설명 짝수명의 사람이 원형으로 서있다. 각 사람의 번호는 1부터 시계방향으로 차례대로 부여한다. 각 사람은 서로 원의 중심 방향을 향해 바라보고 있으며, 반대편 사람을 지켜본다. 당신은 한 원에 몇명의 사람이 서있는지 모른다.(하지만 수는 반드시 짝수다.) 우리가 알고 있는 사실은 사람 $a$가 사람 $b$를 마주보고 있는 상태라는 것이다. 그렇다면 $a, b$와는 다른 수 $c$가 주어졌을 때, $c$가 마주보고 있는 사람은 어떤 수를 가지고 있는 사람일까? 만약 $a, b, c$로 원이 만들어지지 않는다면 $-1$을 출력한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 서로 다른 세 정수 $a, b, c ..

문제 설명 효수는 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..

문제 설명 수인은 길이가 $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,..

문제 설명 당신은 최면 단계에서 갑자기 각 자리수가 0이 포함되지 않는 양의 정수 $n$이 떠올랐다. 최면을 끝내고 집에 돌아오는 길에 당신은 문득 이런 생각이 들었다. 최종 결과가 소수가 아니게 하기 위해서 지워야하는 숫자 개수가 최대 몇개일까? 여기서 말하는 소수는 1과 합성수들을 의미한다. 몇가지 숫자는 소수가 아니게 만들 수 없는데, 예를들어 $53$ 같은 경우는 $5$나 $3$ 모두를 지워도 소수이기 때문이다. 그러나 이 문제에 있는 모든 $n$은 정수 몇개를 지워서 반드시 소수가 아닌 수를 얻을 수 있다는걸 보장한다. 모든 숫자를 지울수 없다는 점에 유의하자. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^3)$이 주어진다. 각 테스트 케이스의 첫번째 줄에는 주..

문제 설명 두 정수 $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번 답게 조금만 생각하면 풀 수 있..

AtCoder Beginner Contest 206 A부터 D까지 업솔빙 진짜 아쉬웠던 대회, 내 수준은 엣코더를 6번째 하면서 D번까지 풀면 실력이 오른거고 D번을 못풀면 실력이 아직 재자리라고 느끼는데 이번에는 접근 방법은 다 생각했는데 구현 방식을 몰라서 못풀었다. 이런 작동을 하는 효율적인 알고리즘이 무엇일까? 라는 생각의 답을 찾기 위해서는 다양한 variation의 문제를 풀면서 경험을 쌓는 수밖에 없다. 이번 대회를 참여하면서 배운 것은 Disjoint-Set(분리집합)의 find함수의 쓰임새 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Maxi-Buying (*5) 접기/펼치기 문제 설명 Atcoder 공화국에서는 소비..

문제 설명 버클리음대에서는 $n$개 종류의 화폐를 사용하고 있다. $i$번째 타입은 $10^{a_i}$의 가치를 가지고 있다. 즉 첫번째 타입 화폐는 $1$원의 가치를 가지고 있다. $f(s)$를 정확히 $s$원을 내기 위해서 필요한 최소 화폐의 수라고 정의하자. 예를 들면 버클리음대에서 $1, 10, 100$원을 사용한다고 할 때 $f(59) = 14$ 이다. $1$원짜리 화폐 $9$개와 $10$원 짜리 화폐 $5$개로 최소 화폐 수로 $59$원을 낼 수 있기 때문이다. 그리고 이 방법 이외에는 더 적은 수로 화폐를 지불 할 수 없다. 정수 $k$에 대해서 화폐 개수가 $k$ 혹은 그보다 작은 화폐 개수로 낼 수 없는 최소 양수 $s$를 구하자. 즉 $f(s) > k$인 $s$를 구하는 것이다. Inp..

문제 설명 버클리 음대에는 새 운영체제를 위한 업데이트 파일을 받았다. 처음에 이 파일은 $1$번째 컴퓨터에만 설치되어 있다. 업데이트 파일은 모든 $n$개 컴퓨터에 설치되어야 하는데, 컴퓨터는 인터넷에 연결되어 있지 않기 때문에 케이블을 이용해서 컴퓨터끼리 케이블을 연결해서 업데이트 파일을 받아야 한다. 오직 한 컴퓨터에는 한 케이블만 연결 될 수 있다. 따라서 업데이트 파일이 설치되어있는 컴퓨터가 다른 컴퓨터에 케이블로 연결되어서 업데이트 파일을 전송하는데 정확히 한시간이 걸린다. 우리가 해야할 일은 만약 버클리음대에 케이블이 $k$개 밖에 없는 상태에서 $n$개 컴퓨터가 모두 패치파일을 받기 위해서 걸리는 최소 시간을 구하는 것이다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $..