2017 Google CodeJam Qual

드디어 2017 Google CodeJam이 시작됐다.

2017.04.08 08:00 AM ~ 2017.04.09 10:00 AM (KST)

1,2번을 풀고

3번 봤는데 small문제가 2개나 있었다.

그냥 max heap써서 간단하게 해결했는데,

large문제는 맞게 짠거 같은데, 자꾸 틀린 결과가 나온다 ㅠ

방법은 k값이 짝수인지 홀수인지에 따라서

트리를 그릴 때 부모노드의 왼쪽 자식인지 오른쪽 자식인지를 판별할 수 있는데,

이 방식으로 루트노드까지 그리고 나면 다시 원래 지점까지 타고 내려오면서 계산하는 방식을 취했다.

어제 새벽 5시까지 고민하다가...

그냥 거기서 포기했다. ㅠㅠㅠㅠㅠㅠㅠㅠ

D번 문제는 보지도 않음.

그래도 작년 이맘 때 쯤엔 막 PS시작해서 퀄문제도 힘들게 풀었는데, 지금은 그 정도는 아닌 것 같아 다행이다.

A. Oversized Pancake Flipper

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
void chg(int idx, string &s, int k) {
    for(int i=idx; i<idx+k; i++) {
        if(s[i]=='-') s[i]='+';
        else s[i]='-';
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int n,k; cin >> n;
 
    for(int z=1; z<=n; z++) {
        string s=""; cin >> s >> k;
        int ans=0, len=s.size();
        for(int i=0; i<len; i++) {
            if(i<=len-k) {
                if(s[i]=='-') {
                    chg(i,s,k);
                    ans++;
                }
            } else {
                if(s[i]=='-') {
                    ans=inf;
                    break;
                }
            }
        }
        printf("Case #%d: ", z);
        if(ans>=inf) puts("IMPOSSIBLE");
        else printf("%d\n", ans);
    }
    return 0;
}
 

B. Tidy Numbers

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int n; cin >> n;
    for(int z=1; z<=n; z++) {
        string s,tmp;
        cin >> s;
        ll ans=0LL;
        int start=-1;
        for(int i=s.size()-1; i>=1; i--) {
            int cv=s[i-1]-'0', pv=s[i]-'0';
            if(cv>pv) {
                start=i;
                s[i-1]=cv-1+'0';
            }
        }
        if(start>=0) {
            for(int i=0; i<start; i++) tmp[i]=s[i];
            for(int i=start; i<s.size(); i++) tmp[i]='9';
        } else tmp=s;
        ans = stoll(tmp);
        printf("Case #%d: %lld\n", z,ans);
    }
    return 0;
}

C. Bathroom Stalls (This code is only for two small input cases)

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int tc; cin >> tc;
    for(int z=1; z<=tc; z++) {
        priority_queue<ll> mxh;
        ll n,k; cin >> n >> k;
        mxh.push(n);
 
        ll x,l,r;
        for(int i=0; i<k; i++) {
            x=mxh.top(); mxh.pop();
            l=(x-1LL)/2LL;
            r=x-l-1;
            mxh.push(l); mxh.push(r);
        }
 
        printf("Case #%d: %lld %lld\n", z,r,l);
    }
    return 0;
}