레야몬

1. 문제 최백준 조교는 그가 가진 금액을 동전으로 교환하되, 그 개수를 최소화하고자 한다. -1- 최백준 조교가 가진 금액 \(M(10^9 \leq M \leq 10^18)\) -2- 동전의 종류 \(N(1 \leq N \leq 1,000)\) -3- 동전의 금액 \(A_i(1 \leq A_i \leq 10,000)\)가 N개 주어진다. N가지의 동전 중 1원짜리 동전은 항상 존재한다. 동전으로 딱 맞는 금액을 만들 때, 그 최소 개수를 출력하라. 2. 재정의 X 3. 해결 방법 \(M = A[N-1] \times x + r)\)로 나타내어질 수 있고 10,000*10,000은 \(10^9\)보다 작기 때문에 나머지가 r이되도록 동전의 개수를 최소화 하고 나머지는 A[N-1]로 더하는 방법으로 그리디를..

1. 문제 랜덤 숫자 생성기(RNG)는 아래와 같은 선형 점화식으로 나타낼 수 있다. \(A_i = (A_{i-1} \times C_1 + A_{i-2} \times C_2 + \cdots + A_{i-k} \times C_k) mod 104857601\) N과 A1, A2, ..., Ak 그리고 C1, C2, ..., Ck가 주어졌을 때, AN을 구하는 프로그램을 작성하시오. 입력 -1- : \(k, N(1 \leq k \leq 30,000, 1 \leq N \leq 10^{18})\) -1- : \(A_i, C_i(0 \leq A_i, C_i < 104857601)\) 출력 -1- A_N 2. 재정의 X 3. 해결 방법 키타마사법에서 다항식의 곱과 나머지 연산을 NTT를 이용해 처리하면 된다. 자세한..

1. 문제 N개의 수로 이루어진 배열 X, Y가 주어진다. 이때 배열은 순환이동이 가능하다. (ex: {1, 2, 3} -> {3, 1, 2}) 점수 S는 아래와 같이 계산한다. \(S=\sum_{i=1}^{N}X[i]\cdot Y[i]\) S의 최댓값을 구하여라. 입력 -1- : 배열의 크기 \(N(1 \leq N \leq 60,000)\) -1- : 배열 X -1- : 배열 Y \((0 \leq x, y < 100)\) 출력 -1-: S의 최댓값 2. 재정의 X 3. 해결 방법 X 배열의 값을 차례대로 계수로 갖는 다항식을 f라고 하자. Y 배열의 값을 역방향으로 계수로 갖는 다항식을 g라고 하자. X와 Y를 곱하면 X 배열의 값과 Y 배열의 곱을 나타내는 항이 N개 만들어지는데 이는 모두 차수가 i..

1. 문제 골프 기계가 할 수 있는 거리 모음 N개의 정수와, 떨어진 구멍까지의 거리 모음 M개의 정수가 주어진다. 두 번 쳐서 공이 들어가는 구멍의 개수는 몇 개인가? 단, 구멍을 향하여 정면으로만 칠 수 있으며 뒤로 치는 것은 불가능하다. 입력 -1- : 정수 \(N(1 \leq N \leq 200,000)\) -N- : 공을 보낼 수 있는 거리 \(k_j(1 \leq k_j \leq 200,000)\) -1- : 정수 \(M(1 \leq M \leq 200,000)\) -M- : 구멍까지의 거리 \(d_j(1 \leq d_j \leq 200,000)\) 출력 -1- : 공이 들어갈 수 있는 구멍의 개수 2. 재정의 N개의 정수중 2개를 중복 가능하게 뽑아서 합이 M개의 정수들 중 같을 수 있는 정수..

1. 문제 두 원이 주어졌을 때, 교차하는 영역의 넓이를 소수점 셋째 자리까지 구하시오. - 1 - 두 원의 중심과 반지름 \(x_{1}, y_{1}, r_{1}, x_{2}, y_{2}, r_{2}\) 실수는 최대 소수점 둘째자리까지 구한다 - 1 - 교차하는 영역의 넓이를 반올림해 소수점 셋째 자리까지 출력한다. 2. 재정의 X 3. 해결 방법 두 점 사이의 거리 \(d = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}}\) 코사인 제2법칙 \(x^{2} + y^{2} - 2xycos(\theta) = z^{2}\) 사인 법칙 \(S = \frac{1}{2} absin(\theta)\) 4. 실수한 점, 개선한 점 X #include #include using ..

1. 문제 크기가 N*N인 행렬 A가 주어질 때 A의 B제곱을 구하는 프로그램을 작성하시오. 각 원소를 1,000으로 나눈 나머지를 출력한다. - 1 - \(N, B(2 \leq N \leq 5, 1 \leq B \leq 100,000,000,000)\) - N개의 줄 - 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수, 또는 0이다. 행렬 A를 B 제곱한 결과를 출력한다. 2. 재정의 X 3. 해결 방법 X 4. 실수한 점, 개선할 점 문제 조건, 특히 숫자 범위를 확인하고 long long 범위를 넘어갈 수 있는지 재차 확인하기! #include #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);..

1. 문제 M개의 자연수 N과 정수 K가 주어졌을 때 이항 계수 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 구하는 프로그램을 작성하시오 - 1 - \(M(1 \leq M \leq 100,000)\) - M개의 줄 - \(N, K(1 \leq N \leq 4,000,000, 0 \leq K \leq N)\) M개의 줄에 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 출력한다. 2. 재정의 X 3. 해결 방법 factorial값을 모두 저정한 다음 페르마의 소정리를 이용해 간단하게 풀면 된다. 4. 실수한 점, 개선할 점 항상 나오지만 자료형 범위 조심하자 분할 정복 사용할 때 재귀 함수를 사용하지 않고 반복문을 이용해하는 방법도 있었다. 이렇게 ..

1. 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오. - 1 - \(N, K, M(1 \leq N \leq 10^{18}, 0 \leq K \leq N, 2 \leq M \leq 2,000, M is prime)\) \(_{n}C_{k}\)를 \(M\)으로 나눈 나머지를 출력한다. 2. 재정의 X 3. 해결 방법 뤼카의 정리를 이용하면 간단하게 풀 수 있다. 4. 실수한 점, 개선할 점 binomial을 사용할 때 dp를 사용하지 않고 Euler's little theorem을 사용하면 0ms로 풀 수 있다. #include #include using namespace std; typedef long long ll; const int MAX..