パソコン甲子園2008 予選
From Usipedia
Contents |
問1 お化け屋敷
説明
普通に入力して出力する．お化け屋敷間の競争は激しそうだ．
ソース
#include <iostream> #include <string> using namespace std; int main(void){ string c; int am, pm; while(cin >> c >> am >> pm){ cout << c << " " << am + pm << " " << am * 200 + pm * 300 << endl; } return 0; }
問2 バトミントン
説明
これも普通に．問題の意味がよく理解出来てないので間違ってるかもしれません．
ソース
#include <iostream> #include <string> using namespace std; int main(void){ int a,b; string in; for(; cin >> in, in != "0";){ a = b = 0; for(int i = 1; i < in.size(); i++){ if(in[i] == 'A') if(++a == 11 && b < 10) break; if(in[i] == 'B') if(++b == 11 && a < 10) break; } (a > b) ? a++ : b++; cout << a << " " << b << endl; } return 0; }
問3 ハワイ好きの王様
説明
10進数を4進数に変換する．
問1もそうだけど，パソコン甲子園は問題の設定にこだわってる気がする．スパイダー人怖いです．
ソース
#include <iostream> #include <vector> using namespace std; int main(void){ for(int n; cin >> n, n != -1;){ vector<int> out; for(;;){ out.push_back(n%4); n=(n-n%4)/4; if(n<=4) break; } if(n != 0) cout << n; for(int i = out.size()-1; i >= 0; i--) cout << out[i]; cout << endl; } return 0; }
問4 どんな色？
説明
16進数の文字を10進数に変換するのが少し大変．もっと楽な方法ないかな．
double min = 99999; あたりに適当感が漂う．
ソース
#include <iostream> #include <string> #include <vector> #include <cmath> using namespace std; class color{ public: string name; int r, g, b; color(string n, string x, string y, string z){ name = n; r = to_int(x); g = to_int(y); b = to_int(z); } int to_int(string a){ return to_kazu(a[1]) + to_kazu(a[0]) * 16; } int to_kazu(char a){ if(a >= '0' && a <= '9') return a-'0'; if(a >= 'a') return a-'a'+10; } double d(color c){ return sqrt(pow(r-c.r, 2.0) + pow(g-c.g, 2.0) + pow(b-c.b, 2.0)); } }; int main(void){ vector<color> t; t.push_back(color("black" , "00", "00", "00")); t.push_back(color("blue" , "00", "00", "ff")); t.push_back(color("lime" , "00", "ff", "00")); t.push_back(color("aqua" , "00", "ff", "ff")); t.push_back(color("red" , "ff", "00", "00")); t.push_back(color("fuchsia", "ff", "00", "ff")); t.push_back(color("yellow" , "ff", "ff", "00")); t.push_back(color("white" , "ff", "ff", "ff")); for(string s; cin >> s, s != "0";){ color in("in", s.substr(1,2), s.substr(3,2), s.substr(5,2)); double min = 99999; int min_id; for(int i = 0; i < 8; i++){ double d = in.d(t[i]); if(d < min){ min = d; min_id = i; } } cout << t[min_id].name << endl; } return 0; }
問5 都市間の距離
説明
- 極座標を用いて2点のxyz空間での座標を求める(aベクトル, bベクトルとする)
- aベクトル, bベクトルのなす角を内積で求める
- 弧の長さを求めて四捨五入
3次元の極座標の2つの角度を逆にしてつまづいた．putはその名残です．
ソース
#include <iostream> #include <cmath> using namespace std; const double R = 6378.1, PI = 2.0 * acos(0.0); class pos{ public: double x, y, z; double t, p; pos(double i, double k){ i = 90 - i; t = (i/180)*PI; p = (k/180)*PI; x = R * sin(t) * cos(p); y = R * sin(t) * sin(p); z = R * cos(t); } void put(void){ cout << "(x, y, z)[km] = (" << x << ", " << y << ", " << z << ")" << endl; cout << "(t, p)[rad] = (" << t << ", " << p << ")" << endl; cout << "(t, p)[度] = (" << t*180/PI << ", " << p*180/PI << ")" << endl; } double sc(void){ return sqrt(pow(x, 2.0) + pow(y, 2.0) + pow(z, 2.0)); } double operator*(const pos& p){ return x*p.x + y*p.y + z*p.z; } }; int main(void){ double ido[2], keido[2]; for(;cin >> ido[0] >> keido[0] >> ido[1] >> keido[1], ido[0] != -1;){ pos a(ido[0], keido[0]), b(ido[1], keido[1]); cout << int(acos((a*b)/(a.sc() * b.sc())) * R + 0.5) << endl; } return 0; }
問6 テトリス
説明
置けるかどうか確認してから置くだけです．
左上を原点に，下向きにy軸，右向きにx軸をとっている点がミソ．
ソース
#include <iostream> #include <vector> using namespace std; int t[1000][5]; void init(void){ for(int i = 0; i < 500; i++){ for(int k = 0; k < 5; k++){ t[i][k] = 0; } } } int where_place(int m, int d, int p){ int c; for(c = 0; ; c++){ if(m == 1){ for(int i = p-1; i < p-1+d; i++){ if(t[c][i] == 1) break; if(i == d-1) return c; } } if(m == 2){ for(int i = c; i < c+d; i++){ if(t[i][p-1] == 1) break; if(i == d-1) return c; } } } } void block_set(int m, int d, int p){ int nowh = where_place(m, d, p); if(m == 1){ for(int i = p-1; i < p-1+d; i++){ t[nowh][i] = 1; } } if(m == 2){ for(int i = nowh; i < nowh+d; i++){ t[i][p-1] = 1; } } } int count_line(int n){ int sum = 0; for(int i = 0; i < 5; i++){ sum += t[n][i]; } return sum; } int count(void){ int sum = 0; for(int i = 0; i < 500; i++){ int nowc = count_line(i); if(nowc == 0) break; if(nowc == 5) continue; sum += nowc; } return sum; } int main(void){ for(int n; cin >> n, n!=0;){ init(); for(int i = 0; i < n; i++){ int m, d, p; cin >> m >> d >> p; block_set(m, d, p); } cout << count() << endl; } return 0; }
問7 ふしぎな虫
(注)この問題は相方が解いてくれました．問9も解いてくれたんだけど時間内に入力出来ず...
説明
条件を満たす「ふしぎな虫」が現れるまで生成し続ける．
特徴はstd::setを使っている点．重複確認から開放されていて少し楽．
全パターンが生成されたら終了するが，それだと遅いので答えが50以上になったら処理を打ち切って NA を出力する(まずい)
ソース
#include <iostream> #include <string> #include <set> using namespace std; typedef set<string>::iterator svi; char nokori(string s){ if(s[0] == s[1]) return s[0]; if(s[0] > s[1]) swap(s[0], s[1]); if(s == "br") return 'g'; if(s == "bg") return 'r'; if(s == "gr") return 'b'; } string henka(string s, int a){ s[a] = s[a+1] = nokori(s.substr(a,2)); return s; } bool check(string in){ for(int i = 0; i < in.size(); i++){ if(in[0] != in[i]) return false; } return true; } int solve(set<string> o, set<string> a, int t){ set<string> c; for(svi i = a.begin(); i != a.end(); i++){ for(int k = 0; k < (*i).length()-1; k++){ if((*i)[k] != (*i)[k+1]){ string s = henka(*i, k); c.insert(s); if(check(s)) return t; } } } if(c.size() == 0 || t > 50 || a == c) return -1; for(svi i = c.begin(); i != c.end(); i++){ o.insert(*i); } return solve(o, c, t+1); } int main(void){ for(string in; cin >> in, in != "0";){ set<string> a; a.insert(in); if(check( *a.begin() )){ cout << 0 << endl; continue; } int ans = solve(a, a, 1); if(ans == -1) cout << "NA" << endl; else cout << ans << endl; } return 0; }
