프로그래밍

https://codeforces.com/contest/1367/problem/C

[난이도] Div.3
[유형] Greedy

[풀이]
앞에서부터 사람을 앉혀보면 된다. 최대한 왼쪽에 붙도록 앉히는게 최적이다.

#include <string>
#include <cstdio>
using namespace std;
int tc,n,k,a[200000];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d",&n,&k);
        int fi=n;
        for(int i=0;i<n;i++) {
            scanf("%1d",&a[i]);
            if(a[i]==1 && fi==n) fi=i;
        }
        int cnt=fi/(k+1);
        if(fi==n) {
            cnt=1+(n-1)/(k+1);
        };
        for(int i=fi;i<n;){
            int ok=1;
            int j;
            for(j=i+1;j<=i+k&&j<n;j++) {
                if(a[j]) {
                    ok=0;
                    break;
                }
            }
            cnt+=ok&&!a[i];
            i=j;
        }
        printf("%d\n",cnt);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/C.cpp

https://codeforces.com/contest/1367/problem/B

[난이도] Div.3
[유형] Greedy

[풀이]
0~N-1까지 확인하면서 i번에서 Good을 만족하지 않으면
i+1~N-1까지의 j를 확인하면서 a[i]가 j에 들어갔을 때 Good을 만족하면서
a[j]가 i에 들어갔을 때도 Good을 만족하면 swap해주는 방식으로 몇번을 swap해줘야 하는지를 세준다.
만약 바꿀 수 있는 j가 없으면 답이 없으므로 -1을 출력한다.

#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
int tc,N,a[41];
int sol(){
    int cnt =0;
    for(int i=0;i<N;i++){
        if(a[i]%2==i%2) continue;
        bool ok = 0;
        for(int j=i+1;j<N;j++){
            if(i%2==a[j]%2 && j%2==a[i]%2){
                swap(a[i],a[j]);
                cnt++;
                ok=1;
                break;
            }
        }
        if(!ok) return -1;
    }
    return cnt;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        printf("%d\n",sol());
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/B.cpp

https://codeforces.com/contest/1367/problem/A

[난이도] Div.3
[유형] 구현

[풀이]
맨 앞, 맨 뒷 글자는 무조건 출력해주고
가운데 글자들은 같은 글자가 두번씩 나오므로 한번씩만 출력되도록 하면 된다.

#include <string>
#include <iostream>
using namespace std;
int tc;
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> s;
        cout << s[0];
        for(int i=1;i<s.size()-1;i+=2) cout << s[i];
        cout << s.back();
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/A.cpp

https://codeforces.com/contest/1409/problem/D

[난이도] Div.3
[유형] Greedy

[풀이]
N 제한이 10^18이기때문에 1씩 증가시켜서는 시간내에 통과가 불가능하다.
각 자릿수들의 합이 점점 작아지도록 할려면 0을 점점 늘려줘야 한다.
0을 늘리려면 10의 자리부터 자릿수 올림이 발생하도록 차례대로 숫자를 더해주면 된다.

#include <cstdio>
using namespace std;
using ll = long long;
int tc,s;
ll n,tn;
int sum(){
    int ret=0;
    ll tt=tn;
    while(tt>0){
        ret+=(tt%10);
        tt/=10;
    }
    return ret;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%lld%d",&n,&s);
        ll k = 10;
        tn=n;
        while(sum()>s){
            ll r = tn%k;
            if(r!=0) tn+=k-r;
            k*=10;
        }
        printf("%lld\n",tn-n);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/D.cpp

https://codeforces.com/contest/1409/problem/C

[난이도] Div.3
[유형] 구현

[풀이]
a2−a1=a3−a2=…=an−an−1=k 를 등차 k가 가장 적게하면서 만족할수록
max(a1,a2,…,an)의 값은 작아지게 된다. k=1부터 체크하면서 조건을 만족하는
수열을 만들 수 있는지 확인해보자

#include <cstdio>
using namespace std;
int n,x,y,tc;
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&n,&x,&y);
        int s,e,j;
        for(int i=1;;i++){
            int cnt=1;
            j=i;
            if((y-x)%i) continue;
            s=x,e=y;
            cnt+=(y-x)/i;
            if(cnt > n) continue;
            if(cnt == n) break;
            s -= ((x-1)/i)*i;
            if((x-1)/i+cnt>=n) {
                cnt+=(x-1)/i;
                s+=(cnt-n)*i;
                break;
            }
            cnt+=(x-1)/i;
            e+=(n-cnt)*i;
            break;
        }
        for(int i=s;i<=e;i+=j) printf("%d ",i);
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/C.cpp

https://codeforces.com/contest/1409

[난이도] Div.3
[유형] 구현

[풀이]
axb가 작아지려면 a와 b의 차이가 크게 날수록 작아진다.
n을 a에서 먼저 뺄수 있을 만큼 빼주고 b에서 뺄 수 있을 만큼 빼준값과
n을 b에서 먼저 뺄수 있을 만큼 빼주고 a에서 뺄 수 있을 만큼 빼준값을
비교해서 더 작은 값을 정답으로 하면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int tc; 
ll a,b,x,y,n,ret;
ll sol(){
    ll ans,tn;
    if(a-x>=n){
        ans = (a-n)*b;
    }else{
        tn = n-(a-x);
        ans = x*max(y,b-tn);
    }
    return ans;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d%d%d",&a,&b,&x,&y,&n);
        ret = sol();
        swap(a,b);
        swap(x,y);
        ret = min(ret,sol());
        printf("%lld\n",ret);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/B.cpp

https://codeforces.com/contest/1409/problem/A

[난이도] Div.3
[유형] 수학

[풀이]
a,b 차이의 절댓값을 d라고 했을 때 d/10의 값에다 d%10이 0이 아니라면 1을 더한 값을 출력해주면 된다.

#include <cstdio>
#include <cmath>
using namespace std;
int tc,a,b;
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d",&a,&b);
        int d = abs(a-b);
        printf("%d\n",d/10+(d%10!=0));
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/A.cpp