레야몬

1. 문제 최백준 조교는 그가 가진 금액을 동전으로 교환하되, 그 개수를 최소화하고자 한다. -1- 최백준 조교가 가진 금액 $M({10}^9\le M\le {10}^{1}8)$ -2- 동전의 종류 $N(1\le N\le 1,000)$ -3- 동전의 금액 $A_i(1\le A_i\le 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)mod104857601$ N과 A1, A2, ..., Ak 그리고 C1, C2, ..., Ck가 주어졌을 때, AN을 구하는 프로그램을 작성하시오. 입력 -1- : $k,N(1\le k\le 30,000,1\le N\le {10}^{18})$ -1- : $A_i,C_i(0\le 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\le N\le 60,000)$ -1- : 배열 X -1- : 배열 Y $(0\le x,y<100)$ 출력 -1-: S의 최댓값 2. 재정의 X 3. 해결 방법 X 배열의 값을 차례대로 계수로 갖는 다항식을 f라고 하자. Y 배열의 값을 역방향으로 계수로 갖는 다항식을 g라고 하자. X와 Y를 곱하면 X 배열의 값과 Y 배열의 곱을 나타내는 항이 N개 만들어지는데 이는 모두 차수가 i..

1. 문제 골프 기계가 할 수 있는 거리 모음 N개의 정수와, 떨어진 구멍까지의 거리 모음 M개의 정수가 주어진다. 두 번 쳐서 공이 들어가는 구멍의 개수는 몇 개인가? 단, 구멍을 향하여 정면으로만 칠 수 있으며 뒤로 치는 것은 불가능하다. 입력 -1- : 정수 $N(1\le N\le 200,000)$ -N- : 공을 보낼 수 있는 거리 $k_j(1\le k_j\le 200,000)$ -1- : 정수 $M(1\le M\le 200,000)$ -M- : 구멍까지의 거리 $d_j(1\le d_j\le 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\le N\le 5,1\le B\le 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\le M\le 100,000)$ - M개의 줄 - $N,K(1\le N\le 4,000,000,0\le K\le N)$ M개의 줄에 ${}_n{C}_k$를 $1,000,000,007$로 나눈 나머지를 출력한다. 2. 재정의 X 3. 해결 방법 factorial값을 모두 저정한 다음 페르마의 소정리를 이용해 간단하게 풀면 된다. 4. 실수한 점, 개선할 점 항상 나오지만 자료형 범위 조심하자 분할 정복 사용할 때 재귀 함수를 사용하지 않고 반복문을 이용해하는 방법도 있었다. 이렇게 ..

1. 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오. - 1 - $N,K,M(1\le N\le {10}^{18},0\le K\le N,2\le M\le 2,000,Misprime)$ ${}_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..