Codeforces Round #630 (Div. 2) 민트의 왕이라네~

인생

조져따....

https://codeforces.com/contest/1332

Dashboard - Codeforces Round #630 (Div. 2) - Codeforces

A. Exercising Walk

최근 ? 푼 코포들중 젤 어려운 A였는듯

int T;
    cin >> T;
    while (T--) {
        int che=0;
        ll a, b,c,d;
        ll x, y, x1, y1, x2, y2;
        cin >> a >> b>>c>>d;
        cin >> x >> y >> x1 >> y1 >> x2 >> y2;
        //큰 if else 들은 지워도 됨
        if (a < b) {//오른쪽
            if (x2 - x <  b - a) che = 1;
        }
        else if (a == b) {
            if (a && x1 == x &&x2==x) che = 1;
        }
        else {
            if (x - x1 < a - b)    che = 1;
        }
        if (c < d) {
            if (y2 - y <  d - c)    che = 1;
        }
        else if (c == d) {
            if (d && y2 == y &&y1==y)    che = 1;
        }
        else {
            if (y - y1 <  c - d)    che = 1;
        }
        if (che)
            cout << "No";
        else
            cout << "Yes";
        cout << '\n';
    }

a와 b가 같은데 a가 0이 아니고 x1==x==x2면 체크 해줘야함! d대신에 중간에 a하나 써서 두번 틀림.. ㅠ

 

 

B. Composite Coloring

 

너무 슬픈문제 애매한 숫자 11의 정체는 바로 루트 1000이하 소수의 갯수 였다... 진짜 이런건줄 모르고 완탐하다가 계속 틀렸었음.. 

int arr[12] = { 1,2,3,5,7,11,13,17,19,23,29,31 };
int gcd(int a, int b) {
    if (b == 0)return a;
    else return gcd(b, a % b);
}
int brr[12];
int a, b;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        for (int i = 1; i <= 11; i++)
            brr[i] = 0;
        vector<int> v;
        vector<int> v2;
        set<int> s;
        cin >> a;
        for (int i = 1; i <= a; i++) {
            int tem;
            cin >> tem;
            for (int j = 1; j <= 11; j++) {
                if (gcd(arr[j], tem)!=1) {
                    v.push_back(j);
                    brr[j] = 1;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= 11; i++)
            if (brr[i])ans++;
        cout << ans << "\n";
        int cou = 1;
        for (int i = 1; i <= 11; i++)
            if (brr[i])brr[i] = cou++;
        for (int a : v)
            cout << brr[a] << ' ';
        cout << '\n';
    }
}

 

C. K-Complete Word

k칸씩 뛰고 좌우 대칭해서 도달할수 있는 칸들을 다 하나로 묶으면 되는 문제

27번줄에 +b를 해주면서 갈수 있으면 queue에 넣어준다. -b 는 대칭이동후 처음 queue에서 꺼낼때 고려해야 하는데 대칭이동 시키기전 값에  +b를 해주고 대칭을 시킨 값과 같으므로 고려하지 않아도 된다.

int vis[MAXN];
int a, b;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> a >> b;
        for (int i = 0; i < a; i++)
            vis[i] = 0;
        string s;
        cin >> s;
        int ans = a;
        for (int i = 0; i < a; i++) {
            if (vis[i]) continue;
            map<int, int> m;
            queue<int> q;
            int maxn = 0;
            q.push(i);
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                vis[node] = 1;
                m[s[node]]++;
                maxn = max(maxn, m[s[node]]);
                if (node + b < a && !vis[node + b]) {
                    vis[node + b]=1;
                    q.push(node + b);
                } 
                if (!vis[a - 1 - node]) {
                    vis[a - 1 - node] = 1;
                    q.push(a - 1 - node);
                }
            }
            ans -= maxn;
        }
        cout << ans << "\n";
    }
}

 

D. Walk on Matrix

레게노 문제

문제에 나와있는 Dp는 잘못되었다. 정답을 고려하지 않고 큰값으로 바꾸기 때문에 마지막 값보다 큰 비트가 중간에 나오면 큰 비트로 바꿔 버린다. 2^17인 131072가 2,2에서 거르는 역할을 한다.

잘못된 dp는 2,2에서 dp값이 131072가 되고 3,3에서는 0이된다. 

제대로된 dp는 2,2에서 k가 되고 3,3에서 k가되고 차이는 k다.

    int k;
    cin >> k;
    cout << 3 << ' ' << 3 << '\n';
    cout << 131072 + k << ' ' << k << ' ' << 0 << "\n";
    cout << 131072 << ' ' << 131072 + k << ' ' << 0 << "\n";
    cout << 0 << ' ' << 131072 + k << ' ' <<  k;