2016년 4월 10일 일요일

Google code jam - Qualification Round 2016

https://code.google.com/codejam/contest/6254486/dashboard
Google code jam - Qualification Round 2016 풀이

Problem A - Counting Sheep

N이 주어지면 N, 2N, ..., kN까지 진행했을 때, 0~9을 모두 사용하게 되는 시점 k에서의 kN을 구하는 문제이다.

문제 그대로 시뮬레이션하면 된다. large set에서 범위가 $0 \le N \le 10^6$ 이지만 0~9가 모두 나오게 되는건 최대 100배이므로 int 범위로 충분히 표현할 수 있다.

Problem B - Revenge of the Pancakes

앞에서부터 k번째까지를 뒤집을 수 있다. (0~k 를 k~0으로 뒤집고 모든 -를 +로 뒤집는다. +-- 를 전부 뒤집는다면 ++- 이 된다.) 최소 몇 번을 이런 식으로 뒤집으면 +로만 이루어진 문자열을 만들 수 있을까?

small set은 재귀로 구현했으나 코딩이 미숙하여 계속 틀렸다. 각 문자열을 1, 2, ..., n번까지 뒤집으면서 BFS를 진행하였다. small set은 길이 $S \le 10$ 이므로 모든 경우의 수는 $2^S$ 라서 최대 1024개만 탐색할 것이다.

small set의 정답을 들여다보고 large set을 해결할 수 있었다. 다음 문자열들은 모두 같은 연산 횟수를 가진다.
++---
+++--
+--
+-
+++-
그러면 문제를 분할할 수 있다. 위 2개의 합은 세번째의 결과와 같다.
+++---
+--
+++---+--
연속되어 있는 문자열은 하나로 생각해도 무방하다. (뒤집는 과정을 생각하면 연속되어 있는 것은 한번에 뒤집는 것이 좋다는 걸 알 수 있다.) 그렇다면 -+ 또는 +- 들만 계산하면 된다.

- 로 시작하는 경우는 처음에 등장한 - 를 뒤집고 나머지를 계산하면 된다.

Problem C - Coin Jam (small)

2진수의 길이가 N인 1~~~1의 형태(~는 0 또는 1)를 가진 10진수를 2, 3, ..., 10진수로 해석한 모든 수가 소수가 아닌 것들을 J개 출력하는 문제이다.

small set은 단순 시뮬레이션으로 해결했다.

N=16, J=50인 경우의 결과를 보면 답이 3 2 5 2 7 2 3 2 11가 자주 등장하는 데, 각 진수들이 3 2 5 2 7 2 3 2 11로 나뉘는 경우들을 출력하면 large set(N=32, J=500)도 해결된다고 한다. (Big-Integer를 사용)

Problem D - Fractiles

문제 이해 못함


소스


A-Counting-Sheep.cpp
#include <bits/stdc++.h>
using namespace std;

string sum(int& bit, string &s, string &p){
        int slen = s.length(), plen = p.length();
        int i, j, cr = 0;
        string r = "";
        for(i=j=0; i<slen || j<plen; ++i, ++j){
            if(i<slen) cr += s[i]-'0';
            if(j<plen) cr += p[j]-'0';
            r.push_back(cr%10 + '0');
            bit |= 1<<(cr%10);
            cr /= 10;
        }
        if(cr > 0){
            r.push_back(cr%10 + '0');
            bit |= 1<<(cr%10);
        }
        return r;
}

int main(){
    int T;
    cin >> T;
    for(int tc=0; tc<T; ++tc){
        string s;
        cin >> s;
        printf("Case #%d: ", tc+1);
        if(s.compare("0") == 0){
            puts("INSOMNIA");
            continue;
        }
        int fqBit = 0, cnt = 0;
        reverse(s.begin(), s.end());
        string r = s;
        for(int i=0; i<r.size(); ++i) fqBit |= 1<<(r[i]-'0')
        for(; fqBit != 1023; ++cnt){
            r = sum(fqBit, r, s);
        }
        for(int i=(int)r.length()-1; i>=0; --i) putchar(r[i]);
        puts("");
    }
    return 0;
}

B-Revenge-of-the-Pancakes(small).cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

string ans;
map<string, bool> cache;

string menuever(string s, int k){
    std::reverse(s.begin(), s.begin()+k);
    for(int i=0; i<k; ++i)
        s[i] = s[i]=='-' ? '+' : '-';
    return s;
}

int solve(string s){
    queue<string> q;
    q.push(s);
    cache[s] = true;
    int dist = 0, len = s.length();
    while(!q.empty()){
        int qs = q.size();
        while(qs--){
            string p = q.front();
            // cout<< p <<'\n';
            q.pop();
            
            if(ans.compare(0, len, p) == 0) return dist;
            
            for(int i=1; i<=len; ++i){
                string rv = menuever(p, i);
                if(cache[rv]) continue;
                cache[rv] = true;
                q.push(rv);
            }
        }
        ++dist;
    }
    return dist;
}

int main(){
    for(int i=0; i<100; ++i) ans.push_back('+');
    int T;
    scanf("%d ", &T);
    for(int tc=0; tc<T; ++tc){
        string s;
        cin >> s;
        cache.clear();
        printf("Case #%d: %d\n", tc+1, solve(s));
    }
    return 0;
}

B-Revenge-of-the-Pancakes(large).cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    int i, T;
    scanf("%d ", &T);
    for(int tc=0; tc<T; ++tc){
        string s;
        cin >> s;
        string r(1, s[0]);
        for(i=1; i<s.length(); ++i){
            if(r.back() != s[i]) r.push_back(s[i]);
        }
        int ret = 0;
        for(i=0; i<r.length(); ++i){
            if(r[i]=='-') ret += 2;
        }
        printf("Case #%d: %d\n", tc+1, ret-(r[0]=='-'));
    }
    return 0;
}

C-Coin-Jam(small).cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

lld interpret(const string& s, lld k){
    lld sum = 0;
    for(int i=0; i<s.length(); ++i)
        sum = sum*k + (s[i]-'0');
    return sum;
}

lld divisor(lld n){
    for(lld i=2; i*i<n; ++i)
        if(n%i == 0) return i;
    return 1;
}

vector<lld> isOk(const string& s){
    vector<lld> ret;
    for(int i=2; i<=10; ++i){
        lld k = interpret(s, i);
        if( divisor(k) == 1 ) return vector<lld>();
        ret.push_back(divisor(k));
    }
    return ret;
}

int main(){
    int tc, T;
    scanf("%d ", &T);
    for(tc=0; tc<T; ++tc){
        int N, J;
        scanf("%d %d ", &N, &J);
        printf("Case #%d:\n", tc+1);
 
        lld c = 1 + (1LL<<(N-1)), bound = 1LL<<N;
        for(int j = 0; j < J && c < bound; c += 2){
            string bin;
            for(lld n = c; n > 0; n /= 2){
                bin.push_back((n%2)+'0');
            }
            std::reverse(bin.begin(), bin.end());
   
            vector<lld> v = isOk(bin);
            if(v.empty()) continue;
   
            printf("%s ", bin.c_str());
            for(int i=0; i<v.size(); ++i)
                printf("%lld ", v[i]);
            j += 1;
            puts("");
        }
    }
    return 0;
}
댓글 쓰기

게시글 목록