알고리즘/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번 답게 조금만 생각하면 풀 수 있..
알고리즘/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..
알고리즘/codeforces
Educational Codeforces Round 116 - B. Update Files
문제 설명 버클리 음대에는 새 운영체제를 위한 업데이트 파일을 받았다. 처음에 이 파일은 $1$번째 컴퓨터에만 설치되어 있다. 업데이트 파일은 모든 $n$개 컴퓨터에 설치되어야 하는데, 컴퓨터는 인터넷에 연결되어 있지 않기 때문에 케이블을 이용해서 컴퓨터끼리 케이블을 연결해서 업데이트 파일을 받아야 한다. 오직 한 컴퓨터에는 한 케이블만 연결 될 수 있다. 따라서 업데이트 파일이 설치되어있는 컴퓨터가 다른 컴퓨터에 케이블로 연결되어서 업데이트 파일을 전송하는데 정확히 한시간이 걸린다. 우리가 해야할 일은 만약 버클리음대에 케이블이 $k$개 밖에 없는 상태에서 $n$개 컴퓨터가 모두 패치파일을 받기 위해서 걸리는 최소 시간을 구하는 것이다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $..
알고리즘/codeforces
Educational Codeforces Round 116 - A. AB Balance
문제 설명 문자 a와 b로만 이루어져 있는 길이가 $n$인 문자열 $s$가 주어진다. $AB(s)$를 $s$의 substring 인 ab의 출현 횟수라고 하고, $BA(s)$를 $s$의 substring 인 ba의 출현 횟수라고 하자. 한 단계에서 우리는 index $i$를 선택하고 $s_i$를 문자 a나 b로 바꿀 수 있다. $AB(s) = BA(s)$ 가 되기 위해서 필요한 최소 연산은 무엇일까? Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 문자열 $s (1 \le |s| \le 100)$ 가 주어진다. 이때 $|s|$ 는 문자열 $s$의 길이를 의미하고 이 문자열은 a와 b로만 이루어져 있다. ..
알고리즘/codeforces
Codeforces Round #750 (Div. 2)-D. Vupsen, Pupsen and 0
문제 설명 카파와 수아는 정수 배열을 선물받았다. 카파는 숫자 $0$을 싫어하기 때문에 카파는 배열에서 $0$을 다 버려버렸다. 그 결과 길아기 $n$인 배열 $a$를 얻었다. 수아는 반대로 숫자 $0$을 좋아하기 때문에 $0$을 제외한 숫자로만 이루어져 있는 배열을 보고 화가 났다. 수아를 응원하기 위해서 카파는 길아가 $n$인 또 다른 배열 $b$를 생각해 냈다. 이 배열은 $\sum_{i=1}^{n} a_i \cdot b_i = 0$ 을 만족한다. 카파는 숫자 $0$을 싫어하기 때문에 배열 $b$는 숫자 $0$이 포함하면 안된다. 또한 숫자는 반드시 크면 안된다. 따라서 배열 $b$ 원소의 절대값의 총합이 $10^9$를 넘어가면 안된다. 위의 조건을 만족하는 배열 $b$를 찾을 수 있도록 도와주자...
