Educational Codeforces Round 109 (Rated for Div. 2) A, B

A. Potion-making

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int k;
        cin >> k;
        cout << 100/gcd(k, 100) << "\n";
    }
    return 0;
}

k% 백분율을 분수로 바꾸면 k/100 가 된다. 포션의 양이 최소가 되게 만드려면 기약분수 형태가 되어야 하므로, k 와 100 의 최소공약수를 구하며 100 에서 나눈 값을 출력해주면 된다.

B. Permutation Sort

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

bool chk(vector<int>& a){
    int n = a.size();
    for(int i = 0; i < n; i++){
        if(a[i] != i+1) return false;
    }
    return true;
}

int solve(int idx, vector<int>& a){
    int cnt = 0;
    int i = idx;
    while(true){
        if(chk(a)) break;
        if(i%2 == 0) sort(a.begin(), a.end()-1);
        else sort(a.begin()+1, a.end());
        i++;
        cnt++;
    }
    return cnt;
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        int tmp;
        for(int i = 0; i < n; i++){
            cin >> tmp;
            a[i] = b[i] = tmp;
        }
        cout << min(solve(0, a), solve(1, b)) << "\n";
    }
    return 0;
}

예제를 풀어보니 1~n-1, 2~n 범위를 번갈아가며 정렬할 때 최소 횟수로 정렬되는 것을 확인했다. 이미 정렬이 되어 있을 경우를 고려해 두 범위를 각각 시작점으로 하여 더 작은 횟수를 출력해준다.

---

D. Armchairs (Upsolving)

C++