Codeforces Round #696 (Div. 2)

Codeforces Round #696 (Div. 2)

Codeforces Round #696 (Div. 2)

 

Codeforces Round #696 (Div. 2)에 대한 해설입니다.

 

 * 이 글은 code-review 항목의 포스트입니다. code-review 항목에 대해 자세히 알아보고 싶다면, 클릭!

 * 문항 원문은 아래 주소에서 확인 가능합니다. Codeforces 696

 - codeforces.com/contest/1474 [ 바로 가기 ]

 

[2021.01.22] 초판 발행

 

 A번과 B번까지만 해결해서 해당 문항에 대한 풀이를 올립니다.

 

[A번] Puzzle From the Future

 

[문제 및 풀이]

 

 주어진 이진수에 더했을 때, 더한 값이 최댓값이 되도록 하는 이진수를 구하는 문제이다. 다만, 이 때 다음 독특한 조건이 있다.

 

 1. 일반적인 덧셈과 달리, 받아올림(carry)을 하지 않고 2로 한다.

 2. 결과값에는 연속된 동일한 숫자가 존재하지 않아야 한다.

 

[구현]

 

 최댓값을 구하기 위해서는 높은 자릿수부터 구해야 한다. 구하고자 하는 이진수(코드에서는 $Ans$)와 덧셈의 결과(코드에서는 $Val$)을 높은 자리에서 하나씩 정해 나간다. 구하고자 하는 이진수의 제일 큰 자리수는 항상 $1$이 되어야 한다. 하지만 그 이후에는 한 자리 큰 구하고자 하는 이진수와 덧셈의 결과의 각 경우에 대해서, 따라서 그 다음 자리수가 유일하게 정해지므로 하나씩 정해나가면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
int N;
int Ans[150000], Val[150000];
char in[150000];
 
void process() {
    int i;
 
    scanf("%d%s", &N, in);
 
    Ans[0] = 1, Val[0] = (in[0] == '0') ? 1 : 2;
 
    for (i = 1; i < N; i++) {
        if (!Val[i - 1]) {
            if (in[i] == '0') Val[i] = 1, Ans[i] = 1;
            else Val[i] = 2, Ans[i] = 1;
        }
 
        else if (Val[i - 1] == 1) {
            if (in[i] == '0') Val[i] = 0, Ans[i] = 0;
            else Val[i] = 2, Ans[i] = 1;
        }
 
        else {
            if (in[i] == '0') Val[i] = 1, Ans[i] = 1;
            else Val[i] = 1, Ans[i] = 0;
        }
    }
 
    for (i = 0; i < N; i++) printf("%d", Ans[i]);
    printf("\n");
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[B번] Different Divisors

 

[문제 및 풀이]

 

 두 소수의 곱으로 이루어진 자연수 중에서, 그 자연수의 모든 약수의 차이가 적어도 $d$인 자연수 중에서 최솟값을 구하는 문제이다.

 

[구현]

 

 에라토스테네스의 체(Sieve of Eratosthenes) 이용해서 $1$보다 $d$만큼 큰 소수 $p$를 구하고, 그 소수 $p$보다 $d$만큼 큰 수소 $q$를 구하면, 정답이 $pq$이다.

 

 [참고] 출제자 editorial을 보고, $p^2$도 정답이 되는지를 검토를 안 했다. 증명해보면 약수가 주어진 조건을 만족하는 $pq (p \neq q)$가 $p^2$보다 항상 작다는 것을 알 수 있다. 정답에 영향을 안 주지만, 고민을 하고 넘어갔어야 하는 지점이다.

 

[예시 답안]

 

#include <stdio.h>
#include <vector>
#define Max 30000
 
using namespace std;
 
int N, M;
bool v[Max];
vector<long long> prime;
long long Ans_a, Ans_b;
 
void get_prime() {
    int i, u;
 
    v[0] = v[1] = true;
 
    for (i = 0; i < Max; i++) {
        if (v[i]) continue;
 
        prime.push_back(i);
        for (u = i + i; u < Max; u += i) v[u] = true;
    }
 
    M = prime.size();
}
 
void process() {
    int i;
 
    scanf("%d", &N);
 
    for (i = 0; i < M; i++) if (prime[i] >= 1 + N) break;
    Ans_a = prime[i];
 
    for (; i < M; i++) if (prime[i] >= Ans_a+N) break;
    Ans_b = prime[i];
 
    printf("%lld\n", Ans_a*Ans_b);
}
 
int main() {
    int T;
 
    get_prime();
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[C번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[D번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[E번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[F번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]