Codeforces Round #741 (Div. 2)

이 날 또 블루 퍼포먼스를 만들어내고 블루 코앞까지 다가갔다. 최근 4번 동안의 코포로 260점 가량 올라왔다. 

그래도 아쉬운 점이 꽤 많았다. C를 한번에 맞췄다면 퍼플 퍼포먼스가 나왔을텐데.....

C를 풀고 D1을 7분만에 풀었으니 충분히 가능했다. 아깝다 ... 

---

A. The Miracle and the Sleeper

Tag : Math

 

풀이

모듈러한 값이 커지려면 풀이는 뻔하다.

 

시간복잡도 : \(O(1)\)

 

전체 코드

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)),(x).erase(unique(all(x)),(x).end())
#define endl '\n'
using namespace std;
using ll = long long;
 
mt19937 rd((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
ll gen(ll l = 0, ll r = 32767) { return uniform_int_distribution<ll>(l, r)(rd); }
 
void solve(){
    ll l, r; cin >> l >> r;
    ll a=r;
    ll b=max((r+1)/2+!(r%2), l);
    cout<<a%b<<endl;
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0),cout.tie(0);
 
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

B. Scenes From a Memory

Tag : Math, sieve of Eratosthenes

 

풀이

지워서 한자리수로 만들 수 있으면 만들고 안되면 두자리수 그거도 안되면 세자리수를 시도해본다. 

이게 왜 되는지는 에라토스테네스의 체를 그려보면 이해가 갈 듯 하다.

 

시간복잡도 : \(O(K^3)\)

 

전체 코드

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)),(x).erase(unique(all(x)),(x).end())
#define endl '\n'
using namespace std;
using ll = long long;
 
mt19937 rd((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
ll gen(ll l = 0, ll r = 32767) { return uniform_int_distribution<ll>(l, r)(rd); }
 
vector<int>prime(1010,1);
 
void solve(){
    ll K;string N;
    cin>>K>>N;
    for(auto&i:N){
        if(prime[i-'0']==0){
            return cout<<1<<endl<<i<<endl,void();
        }
    }
    for(int i=0;i<K;i++){
        for(int j=i+1;j<K;j++){
            int a=N[i]-'0';
            a = 10 * a + N[j]-'0';
            if(prime[a]==0){
                return cout<<2<<endl<<a<<endl,void();
            }
        }
    }
    for(int i=0;i<K;i++){
        for(int j=i+1;j<K;j++){
            for(int p=j+1;p<K;p++){
                int a = N[i]-'0';
                a = 10 * a + N[j]-'0';
                a = 10 * a + N[p]-'0';
                if(prime[a]==0) return cout<<3<<endl<<a<<endl,void();
            }
        }
    }
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0),cout.tie(0);
 
    prime[1]=0;
    for(int i=2;i<=1000;i++){
        if(prime[i]==0)continue;
        for(int j=i*i;j<=1000;j+=i)prime[j]=0;
    }
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

C. Rings

Tag : Constructive

 

풀이

비트 문자열에 0이 있다면 0을 포함한 왼쪽이나 오른쪽 둘 중 하나는 \(N/2\) 이상이기 때문에 0을 끝으로 하도록 출력하면 된다.

비트 문자열에 0이 없다면 \(N/2\)이상인 것 중 아무거나 출력하면 된다.

여기서 0이 없는 경우를 잘못 처리해놓고 애꿎은 0이 있는 경우를 디버깅해버렸다.. 그래서 시간이 날라가버렸다....

퍼플 퍼포먼스를 볼 수 있었는데 ... 

 

시간복잡도 : \(O(N)\)

 

전체 코드

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)),(x).erase(unique(all(x)),(x).end())
#define endl '\n'
using namespace std;
using ll = long long;
 
mt19937 rd((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
ll gen(ll l = 0, ll r = 32767) { return uniform_int_distribution<ll>(l, r)(rd); }
 
 
 
void solve(){
    ll N;cin>>N;
    vector<char>v(N + 1);
    for(int i=1;i<=N;i++)cin>>v[i];
    for(int i=1;i<=N;i++){
        if(v[i]=='1')continue;
        if(i>=N/2+1){
            cout<<1<<' '<<i<<' '<<1<<' '<<i-1<<endl;
            return;
        }
        if(N-i+1>=N/2+1){
            cout<<i<<' '<<N<<' '<<i+1<<' '<<N<<endl;
            return;
        }
    }
    int a=0;for(auto&i:v)a+=i=='0';
    assert(a==0);
    cout<<1<<' '<<N/2<<' '<<2<<' '<<N/2+1<<endl;
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0),cout.tie(0);
 
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

D1. Two hundred Twenty one

Tag : adhoc, constructive

 

풀이 

입력된 구간의 합이 홀수라면 1 ~ i-1의 합이 i+1~r과 같은 i를 찾아내면 된다.

짝수라면 맨 뒤에를 하나 지우고 홀수를 처리하듯이 풀면 된다.

 

전체 코드

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)),(x).erase(unique(all(x)),(x).end())
#define endl '\n'
using namespace std;
using ll = long long;
 
mt19937 rd((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
ll gen(ll l = 0, ll r = 32767) { return uniform_int_distribution<ll>(l, r)(rd); }
 
 
 
void solve(){
    int N,Q;cin>>N>>Q;
    string s;cin>>s;
    int a=0;vector<int>sum(N);
    for(int i=0;i<N;i++){
        int p=1;
        if(i%2)p=-1;
        if(s[i]=='-')p=-p;
        a+=p;
        sum[i]=(i>0?sum[i-1]:0)+p;
    }
    while(Q--){
        int l,r;cin>>l>>r;l--,r--;
        int p=sum[r];
        if(l>0)p-=sum[l-1];
        if(p==0)cout<<0<<endl;
        else if(p%2)cout<<1<<endl;
        else cout<<2<<endl;
    }
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0),cout.tie(0);
 
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

D2. Two hundred Twenty one

Tag : adhoc, constructive

 

풀이 

D1에서 조금만 수정해주면 된다. 

홀수 일 때는 \(PS_l + PS_r = PS_x + PS_x-1 \)인 \(x\)를 찾아주면 된다. \(PS\)는 누적합이다.

짝수일 때는 맨 뒤를 하나 제거하고 홀수처럼 풀어주면 된다.