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