情報オリンピック 第7回予選問題
1. おつり AOJ 0521 Change
#include <cstdio> int count(int x){ int coins = 0; while(x >= 500) coins++, x -= 500; while(x >= 100) coins++, x -= 100; while(x >= 50) coins++, x -= 50; while(x >= 10) coins++, x -= 10; while(x >= 5) coins++, x -= 5; while(x >= 1) coins++, x -= 1; return coins; } int main() { int n; while(scanf("%d\n", &n), n){ printf("%d\n", count(1000 - n)); } return 0; }
ださいが早くとけた。
2. JOIとIOI AOJ 0522 JOI and IOI
#include <iostream> #include <string> using namespace std; int main() { string s; while(cin>>s){ int icnt = 0, jcnt = 0; for(int i = 0; i < s.size(); i++){ if(s.find("IOI", i) == i){ icnt++; }else if(s.find("JOI", i) == i){ jcnt++; } } cout<<jcnt<<endl<<icnt<<endl; } return 0; }
3. カードゲーム AOJ 0523 Card Game
#include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { int n; while(scanf("%d\n", &n), n){ vector<int> tcards(n), hcards; for(int i = 0; i < n; i++) scanf("%d\n", &tcards[i]); sort(tcards.begin(), tcards.end()); for(int i = 1, p = 0; i <= 2*n; i++){ if(p < tcards.size()){ if(tcards[p] == i){ p++; }else{ hcards.push_back(i); } }else{ hcards.push_back(i); } } int ba = 0; int turn = 0; while(!tcards.empty() && !hcards.empty()){ if(turn == 0){/* taro */ int put = 0; for(int i = 0; i < tcards.size(); i++){ if(tcards[i] > ba){ ba = tcards[i]; tcards.erase(remove(tcards.begin(), tcards.end(), ba), tcards.end()); put = 1; break; } } if(!put) ba = 0; turn = 1; }else{ int put = 0; for(int i = 0; i < hcards.size(); i++){ if(hcards[i] > ba){ ba = hcards[i]; hcards.erase(remove(hcards.begin(), hcards.end(), ba), hcards.end()); put = 1; break; } } if(!put) ba = 0; turn = 0; } } int tscore = hcards.size(), hscore = tcards.size(); printf("%d\n%d\n", tscore, hscore); } return 0; }
4. 星座探し AOJ 0524 Searching Constellation
#include <cstdio> #include <vector> #include<set> using namespace std; typedef pair<int, int> px; int main() { int m; while(scanf("%d\n", &m), m){ vector<px> needle; set<px> haystack; for(int i = 0; i < m; i++){ int x, y; scanf("%d %d\n", &x, &y); needle.push_back(make_pair(x, y)); } int n; scanf("%d\n", &n); for(int i = 0; i < n; i++){ int x, y; scanf("%d %d\n", &x, &y); haystack.insert(make_pair(x, y)); } for(set<px>::iterator it = haystack.begin(); it != haystack.end(); it++){ int ox = (*it).first - needle[0].first, oy = (*it).second - needle[0].second, match = 1; for(int i = 1; i < needle.size(); i++){ if(haystack.find(make_pair(needle[i].first + ox, needle[i].second + oy)) == haystack.end()){ match = 0; break; } } if(match){ printf("%d %d\n", ox, oy); break; } } } return 0; }
一発Acceptして少しうれしかった。
5. おせんべい AOJ 0525 Osenbei
#include <cstdio> #include <vector> using namespace std; int main() { int R, C; while(scanf("%d %d\n", &R, &C), R || C){ vector<vector<int> > v(R, vector<int>(C)); for(int i = 0; i < R; i++) for(int j = 0; j < C; j++) scanf("%d", &v[i][j]); int dst = 0; for(int i = 0; i < (1 << R); i++){ vector<vector<int> > w = v; for(int j = 0; j < R; j++) if(i & (1 << j)) for(int k = 0; k < C; k++) w[j][k] = !w[j][k]; for(int k = 0; k < C; k++){ int rtotal = 0; for(int j = 0; j < R; j++) rtotal += w[j][k]; if(rtotal < (R / 2)) for(int j = 0; j < R; j++) w[j][k] = !w[j][k]; } int total = 0; for(int j = 0; j < R; j++) for(int k = 0; k < C; k++) total += w[j][k]; dst = max(dst, total); } printf("%d\n", dst); } return 0; }
6. 船旅 AOJ 0526 Boat Travel
AIZU ONLINE JUDGE
昔というかこの前Dijkstraの練習で解いた。時間があればもう一度やっておきたい。
AOJ 0526 Boat Travel - ペリャウドのプログラミングとか