IOI 2018 4번) Mechanical Doll
https://www.acmicpc.net/problem/20064 20064번: Mechanical Doll Let M = 4, N = 4, and A = [1, 2, 1, 3]. The grader calls create_circuit(4, [1, 2, 1, 3]). The above figure shows a circuit, which is described by a call answer([1, -1, -2, 0, 2], [2, -2], [3, 1]). The numbers in the figure are the serial numbers of the dev www.acmicpc.net Switch의 성질 관찰 Switch는 다시 초기 상태로 돌아와야 하기 때문에, 공이 짝수 번 들어와야 합니다. ..
오늘의 문제 2일차 ~ 6일차 풀이
6일차 (장미) : 실버 I $a \times c$개의 장미를 살 때는, $\frac{b}{a}, \frac{d}{c}$ 중 작은 쪽의 장미를 사는 것이 무조건 이득입니다. 따라서, 장미 한 개당 가격이 높은 장미를 $a \times c$개 이상 사지 않습니다. 따라서 $\frac{b}{a} > \frac{d}{c}$라면 a의 한 개당 가격이 더 비싸니까, a개 짜리를 0묶음, 1묶음, ..., c-1묶음 사는 경우를 고려해주면 됩니다. 시간복잡도 : $\frac{b}{a} > \frac{d}{c}$이면 $O(c)$, $\frac{b}{a} j인 모든 (i, j)에 대해, dp[i][j]를 구해줍니다. 이분탐색으로 수열의 i번째 항 - j번째 항 = j번째 항 - m번째 항인 m을 찾으면, dp[i][j..
(BOJ 17372) 피보나치 수의 최대공약수의 합
https://www.acmicpc.net/problem/17372 17372번: 피보나치 수의 최대공약수의 합 첫 번째 줄에 구하는 합을 1,000,000,007로 나눈 나머지를 출력합니다. www.acmicpc.net 모바일 환경일 경우 수식이 깨질 수 있습니다. 수열 F가 $F_{1} = 1, F_{2} = 1, F_{n+1} = F_{n} + F_{n-1}$를 만족할 때, $\sum_{i=1}^{n}{\sum_{j=1}^{n}{gcd(F_{i}, F_{j})}}$ 를 구하는 문제입니다. 배경지식 gcd(a, b) : a, b의 최대공약수로, 자연수 a와 b를 모두 나누는 가장 큰 자연수입니다. $I$ : 자연수 n에 대해 f(n) = 1을 만족하는 함수입니다. $Id$ : 자연수 n에 대해 f(n..
2021.01.03 PS - CEOI 2017 2번
1번 문제 2번 문제 3번 문제 난이도 순서대로 2번 -> 1번 -> 3번 순서대로 풀 예정입니다. 2번. SURE BET 서브태스크 1 : N b[i]; } sort(a, a+n, cmp); sort(b, b+n, cmp); double ans = 0; sum_a[0] = 0, sum_b[0] = 0; for(int i=1;i a[i] >> b[i]; } sort(a+1, a+n+1, cmp); sort(b+1, b+n+1, cmp); double profit_a = 0, profit_b = 0, ans = 0; for(int x = 0, y = 0; x + y < 2*n ;){ if(x == n){ y++; profit_a += -1; profit_b += b[y] - 1; ans = max(ans,..
