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;
}
댓글 없음:
댓글 쓰기