Codeforences #351 VK CUP

【A. Bear and Game:】
[제의] 이렇게 많은 시간을 주었는데 이 시간들은 인터럽트 포인트입니다. 15분 동안 인터럽트 포인트가 나타나지 않으면 바꿔야 합니다.제일 오래 볼 수 있냐고 물어봐요.
[분석] 직접 시뮬레이션을 하면 된다.
[AC 코드]

#include <bits/stdc++.h>
using namespace std;
int a[100];
int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=1; i<=n; i++){
            scanf("%d",&a[i]);
        }
        if(a[1]>15){
            puts("15");
            return 0;
        }
        for(int i=2; i<=n; i++){
            if(a[i]-a[i-1]>15){
                printf("%d
",a[i-1]+15);
                return 0;
            }
        }
        if(a[n]<75)
        {
            cout<<a[n]+15<<endl;
        }
        else{
            cout<<"90"<<endl;
        }
    }
    return 0;
}

【B. Problems for Round】
[제의] 1부터 n까지 이 수를 두 용기에 넣으면 첫 번째 용기의 그 어떤 수도 두 번째 용기의 그 어떤 수보다 작아야 한다. 그리고 비슷한 것은 한 조각도 넣을 수 없고 비슷한 것은 전달성이 없다.
【분석】 두 용기의 첫 번째는 최대치를 기록하고 두 번째는 최소치를 기록한다. 한 쌍의 비슷한 수에 대해 작은 것은 첫 번째에 놓고 큰 것은 두 번째에 놓는다. 동시에 최대치의 최소치를 충족시키는지 검사하고 최대치를 갱신해야 한다. 답은 두 개의 차이다!
[AC 코드]

#include <bits/stdc++.h>
using namespace std;
int a[100010];
const int INF = 0x3f3f3f3f;
int main(){
    int n,m,u,v,maxx=-1,minn=INF,ans;
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>u>>v;
        if(u>v)swap(u,v);
        maxx = max(maxx,u);
        minn = min(minn,v);
    }
    if(m==0)ans=n-1;
    else{
            if(minn<maxx) ans=0;
            else ans = minn-maxx;
    }
    cout<<ans<<endl;
    return 0;
}

【C. Bear and Colors】
[제의] 이렇게 많은 색깔을 제시했는데 한 서열에서dominant는 가장 많이 나온 숫자입니다. 만약에 가장 많이 나온 것이 하나가 아니라면 가장 작은 숫자입니다.
[분석] 바로 폭력 통계가 나옵니다.
[AC 코드]

#include <bits/stdc++.h>
using namespace std;
int n,a[5010];
int ans[5010];
int temp;
int main(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++){
        int cnt[5010]={0};
        int maxx=-1;
        for(int j=i; j<=n; j++){
            cnt[a[j]]++;
            if(cnt[a[j]]>maxx){
                maxx = cnt[a[j]];
                temp = a[j];
            }else if(cnt[a[j]]==maxx&&a[j]<temp){
                temp = a[j];
            }
            ans[temp]++;
        }
    }
    for(int i=1; i<=n; i++)cout<<ans[i]<<" ";
    return 0;
}

【D. Bear and Two Paths】
[제의] n개의 노드를 제시한 다음에 두 노선의 기점과 종점을 제시한다. 당신은 무방향도를 구성하여 무방향도에서 a, b간과 c, d간에 직접적으로 연결된 변이 없고 이 그림의 변의 수가 k를 초과하지 않도록 요구한다.
【분석】 n=4를 발견했을 때 아무리 해도 만족할 수 없었고 이런 무방향도를 구성할 수 있었다. 첫 번째 노선ac...db;두 번째 노선ca...bd, 이런 변은 n+1개로 가장 적다
[AC 코드]

#include <bits/stdc++.h>
using namespace std;
int n,k,a,b,c,d;
int ans[1010],vis[1010];
int main(){
    cin>>n>>k;
    cin>>a>>b>>c>>d;
    memset(vis,0,sizeof(vis));
    memset(ans,0,sizeof(ans));
    vis[a]=vis[b]=vis[c]=vis[d]=1;
    if(k<n+1||n==4){
        puts("-1");
        return 0;
    }
    ans[1]=a,ans[2]=c,ans[n-1]=d,ans[n]=b;
    int pos=3;
    for(int i=1; i<=n; i++){
        if(!vis[i]) ans[pos++]=i;
    }
    for(int i=1; i<=n; i++)cout<<ans[i]<<" ";cout<<endl;
    cout<<ans[2]<<" "<<ans[1]<<" ";
    for(int i=3; i<=n-2; i++)cout<<ans[i]<<" ";
    cout<<ans[n]<<" "<<ans[n-1]<<endl;
    return 0;
}

[ps: 뒷문제는 당분간 QAQ를 풀 수 없습니다.]