nodeal dev story

solved.ac 실버 5에 랭크되어 있지만 재미있는 문제다. 어지간히 복잡한 방법을 사용해서 해결하더라도 수열의 길이가 1,000을 넘지 않는다는 점에서 해결이 어려운 문제는 아니다. 하지만 상수 시간에 해결할 수 있다면 어떨까? 문제에서 주어진 수열은 다음과 같다: \(a_n\) = 1 2 2 3 3 3 4 4 4 4 5 5 5 ... 1이 1번, 2가 2번, 3이 3번, 4가 4번 나오는 방법이 반복되는 것이다. 이때 수열 \(a_n\)의 \(n\)번째 항까지의 합을 \(S(n)\)라고 하자. 문제에서 입력 A와 B가 주어질 때 A부터 B번째 수까지의 합은 다음과 같이 표현할 수 있다. $$S(B) - S(A) + a_A$$ 그렇다면 \(S(n)\)와 A번째 항 \(a_A\)를 상수 시간에 구할 수..

주어진 범위의 수들 중 k개의 등차수열의 합으로 표현가능한 수의 수를 구하는 문제다. 초항과 공차가 반드시 자연수이므로 각 k에 맞는 최소한의 수가 존재한다. k = 2) 1 + 2 = 3이므로, left가 3보다 작더라도 3부터 시작한다. 초항 n, 공차 d에서 n + n + d = 2n + d를 만족하는 모든 수가 해당된다. 따라서 3이상의 모든 수가 길이가 2인 등차수열의 합이다. (예: 4 = 1 + 3, 5 = 1 + 4 ...) k = 3) 1 + 2 + 3 = 6이므로, left가 6보다 작더라도 6부터 시작한다. 초항 n, 공차 d에서 n + n + d + n + 2d = 3n + 3d를 만족하는 모든 수가 해당된다. 따라서 6이상의 모든 3의 배수가 길이가 3인 등차수열의 합이다. k =..

이게 왜 solved.ac 골드 1에 있는 문제인지 의문스럽다. 문제의 제한 시간은 2초, 1,000,000보다 작거나 같은 모든 L에 대해 선분의 길이 쌍을 모두 구하고도 남을 시간이다. (3, 4), (5, 12), (8, 15) ... 와 같은 쌍을 모두 준비하는 방법을 생각해보자. 첫번째 조건은 세 성분을 잘 조합했을 때 '피타고리안 트리플'이 되어야 한다는 것이다. 3, 4가 있다면 다른 한 수는 5가 되어야 한다는 것이다. 두번째 조건은 폭보다 높이가 커야한다는 것으로, (3, 4), (4, 3)에서는 (3, 4)만이 유효하다는 것을 알 수 있다. 마지막 조건은 두 수의 최대공약수가 1이어야 한다는 것, 다시 말해 두 수가 서로소여야 한다는 것이다. (3, 4)는 허용해도, (6, 8)은 안 ..

두 수의 합이 다른 두 소수의 합으로 표현할 수 있는가에 대한 문제다. 문제에서 A와 B의 범위는 1 이상이므로 합은 2, 3, 4, ...로 나올 수 있다. 이때 A+B가 2 또는 3이라면) 가장 작은 소수 2를 뺐을 때 나머지 0 또는 1이 소수가 아니므로 두 소수의 합으로 표현할 수 없다. A+B가 4 이상의 짝수라면) 골드바흐의 추측*에 의해 '어지간한 수'까지는 두 소수의 합으로 표현할 수 있다. * 수학적으로 엄밀한 증명이 이뤄지지는 않았지만, 우리 문제 범위에서는 영향이 없다. A+B가 4 이상의 홀수라면) 2로 뺀 A+B-2가 소수라면 두 소수의 합으로 표현할 수 있고, A+B-2가 소수가 아니라면 두 소수의 합으로 표현할 수 없다. 예를 들어 19는 2+17의 쌍으로 표현할 수 있다. 하..

문제의 중요한 조건은 두 터렛의 좌표와 거리를 이용해서 원의 외부, 외접, 내접, 내부, 일치를 판별하는 것이다. 두 터렛 사이의 거리가 각 터렛에서0) 마린까지의 거리가 일치하고 두 터렛의 위치가 일치하면 일치1) 마린까지의 거리의 합보다 크면 외부2) 마린까지의 거리의 차보다 작으면 내부3) 마린까지의 거리의 합과 같으면 외접4) 마린까지의 거리의 차와 같으면 내접5) 마린까지의 거리의 차보다 크고 합보다 작으면 두 점에서 만난다. 원래대로라면 두 점 사이의 거리는 전부 제곱근을 이용해야하지만 제곱근을 구하는 것 보다 반대쪽을 제곱하는 편이 유리하니 이 방법을 사용하도록 한다. testcase는 반드시 0이상의 정수이므로 unsignedr1, r1은 자연수지만 뺄셈에서 결과를 위해 signed 굳이 ..

출력하고자 하는 다이아몬드의 변의 길이 N 입력) 3 출력) * ******** *** * #include int main() { int n; printf("Input N: "); scanf("%d", &n); int lines = 2 * n - 1; for (int i = 0; i < lines; i++) { int blanks = lines - n - ((i < n) ? i : (lines - i - 1)); int stars = lines - 2 * blanks; for (int j = 0; j < blanks; j++) { printf(" "); } for (int j = 0; j < stars; j++) { printf("*"); } printf("\n"); } return 0; }

5개의 문자열을 받아 긴 문자열부터 출력 입력) 00000 00 000 0 0000 출력) 0 00 000 0000 00000 #include #include #include int compare(const void *, const void *); // 비교 함수 선언 int main() { unsigned int input_length = 5; char **input = (char **) malloc(sizeof(char *) * input_length); // 문자열 저장 포인터 for (unsigned int i = 0; i < input_length; i++) { *(input + i) = (char *) malloc(sizeof(char) * 10); // 9개의 문자를 받을 수 있는 문자열 g..

출력) A A C A C E A C E G A C E G I A C E G I K A C E G I K M A C E G I K M O A C E G I K M O Q A C E G I K M O Q S A C E G I K M O Q S U A C E G I K M O Q S U W A C E G I K M O Q S U W Y #include int main() { for (unsigned int i = 0; i