Google Code Jam Qualification Round 2012
学校行って塾に行った後解くという過酷な感じになって辛かった
A,B,Cを解いたけどCのlargeを落として45点だった・・・まあ進めたのでいいか()
60点は普通に取れた感じがします(D読んでないですすみません)
A. Speaking in Tongues
やるだけ
全単射だし変換法則も決まっているのでsample inputとhintを見ましょう
#include <iostream> #include <map> #include <cstdio> #include <string> using namespace std; string s; int n; int main(){ scanf("%d\n", &n); map<char,char> hoge; hoge.insert(map<char,char>::value_type('a','y')); hoge.insert(map<char,char>::value_type('b','h')); hoge.insert(map<char,char>::value_type('c','e')); hoge.insert(map<char,char>::value_type('d','s')); hoge.insert(map<char,char>::value_type('e','o')); hoge.insert(map<char,char>::value_type('f','c')); hoge.insert(map<char,char>::value_type('g','v')); hoge.insert(map<char,char>::value_type('h','x')); hoge.insert(map<char,char>::value_type('i','d')); hoge.insert(map<char,char>::value_type('j','u')); hoge.insert(map<char,char>::value_type('k','i')); hoge.insert(map<char,char>::value_type('l','g')); hoge.insert(map<char,char>::value_type('m','l')); hoge.insert(map<char,char>::value_type('n','b')); hoge.insert(map<char,char>::value_type('o','k')); hoge.insert(map<char,char>::value_type('p','r')); hoge.insert(map<char,char>::value_type('q','z')); hoge.insert(map<char,char>::value_type('r','t')); hoge.insert(map<char,char>::value_type('s','n')); hoge.insert(map<char,char>::value_type('t','w')); hoge.insert(map<char,char>::value_type('u','j')); hoge.insert(map<char,char>::value_type('v','p')); hoge.insert(map<char,char>::value_type('w','f')); hoge.insert(map<char,char>::value_type('x','m')); hoge.insert(map<char,char>::value_type('y','a')); hoge.insert(map<char,char>::value_type('z','q')); for(int i = 1; i <= n; i++){ getline(cin,s); for(int j = 0; j < s.length(); j++){ if(s[j] != ' ')s[j] = hoge[s[j]]; } cout << "Case #" << i << ": "<< s << endl; } return 0; }
B. Dancing With the Googlers
貪欲でできた
#include <cstdio> #include <algorithm> using namespace std; int T, N, S, p, ans; int score[100]; int main(){ scanf("%d", &T); for(int t = 1; t <= T; t++){ ans = 0; scanf("%d %d %d", &N, &S, &p); for(int i = 0; i < N; i++){ scanf("%d", &score[i]); } sort(score, score + N); for(int i = 0; i < N; i++){ if(score[i] >= p * 3 - 2){ ans++; }else if((score[i] == p * 3 - 4 || (p >= 2 && score[i] == p * 3 - 3)) && S > 0){ S--; ans++; } } printf("Case #%d: %d\n", t, ans); } return 0; }
C. Recycled Numbers
数字の回転処理は数字のままでやったけど文字列としてやった人が多かったみたい?
重複があってlargeは落ちました(泣)
↓提出したソース
#include <cstdio> using namespace std; int T, a, b, tmp, digit, ans; int fact[10]; int main(){ fact[0] = 1; fact[1] = 10; for(int i = 2; i <= 10; i++){ fact[i] = 10 * fact[i-1]; } scanf("%d", &T); for(int t = 1; t <= T; t++){ ans = 0; scanf("%d %d", &a, &b); tmp = a; digit = 1; for(int i = 0; i <= 7; i++){ if(tmp / fact[i] >= 10) digit++; } for(int i = a; i <= b; i++){ for(int j = 1; j < digit; j++){ tmp = i / fact[j] + i % fact[j] * fact[digit - j]; if(tmp > i && tmp >= a && tmp <= b) ans++; } } printf("Case #%d: %d\n", t, ans); } return 0; }
set使ったら通ってた(憤怒)
#include <cstdio> #include <set> using namespace std; int T, a, b, tmp, digit, ans; int fact[10]; set<int> hoge[2000001]; int main(){ fact[0] = 1; fact[1] = 10; for(int i = 2; i <= 10; i++){ fact[i] = 10 * fact[i-1]; } scanf("%d", &T); for(int t = 1; t <= T; t++){ ans = 0; scanf("%d %d", &a, &b); tmp = a; digit = 1; for(int i = 0; i <= 7; i++){ if(tmp / fact[i] >= 10) digit++; } for(int i = a; i <= b; i++){ hoge[i].clear(); for(int j = 1; j < digit; j++){ tmp = i / fact[j] + i % fact[j] * fact[digit - j]; if(tmp > i && tmp >= a && tmp <= b){ hoge[i].insert(tmp); } } } for(int i = a; i <= b; i++){ ans += hoge[i].size(); } printf("Case #%d: %d\n", t, ans); } return 0; }