第7回JOI予選問題 2週目
全完までに2時間18分。問6のデバッグでかなり食った。よろしくない。
過去と比較すると、どの程度1年間でコーディング力が変わったか観察できて面白いかもしれない。内容自体に差はないがコードの可読性は結構上がったと勝手に思っている。
1. おつり AOJ 0521 Change
#include <cstdio> int main() { int src; while (scanf("%d\n", &src), src) { const int coins[] = {500, 100, 50, 10, 5, 1}; int n = 1000 - src, res = 0; for (int i = 0; i < 6; ++i) { res += n / coins[i]; n = n % coins[i]; } printf("%d\n", res); } return 0; }
2. JOIとIOI AOJ 0522 JOI and IOI
#include <cstdio> #include <cstring> using namespace std; int main() { char s[10002]; while (~scanf("%s\n", s)) { int joi = 0, ioi = 0; for (int i = 0, l = strlen(s); i < l - 2; ++i) { const char c = s[i]; if (c == 'J' || c == 'I') if (s[i + 1] == 'O' && s[i + 2] == 'I') { if (c == 'J') joi++; else ioi++; } } printf("%d\n%d\n", joi, ioi); } return 0; }
3. カードゲーム AOJ 0523 Card Game
#include <cstdio> #include <list> #include <vector> #include <algorithm> using namespace std; int giveCard(list<int>& hand, int deck) { for (list<int>::iterator it = hand.begin(); it != hand.end(); ++it) { const int cur = *it; if (*it > deck) { hand.erase(it); return cur; } } return -1; } void proceed(vector<list<int> >& hands) { bool turn = false; int deck = -1; while (hands[0].size() && hands[1].size()) { deck = giveCard(hands[turn], deck); turn = !turn; } } int main() { int n; while (scanf("%d\n", &n), n) { vector<bool> dist(2 * n, true); /* false: taro, true: hanako*/ for (int i = 0, t; i < n; ++i) { scanf("%d\n", &t); dist[t - 1] = false; } vector<list<int> > hands(2); for (int i = 0; i < dist.size(); ++i) { hands[dist[i]].push_back(i); } proceed(hands); printf("%d\n%d\n", hands[1].size(), hands[0].size()); } return 0; }
4. 星座探し AOJ 0524 Searching Constellation
#include <cstdio> #include <cassert> #include <set> #include <algorithm> using namespace std; class Star { public: pair<int, int> pa; Star(){return;} Star(int x, int y) { this->pa.first = x, this->pa.second = y; return; } inline int x() const { return pa.first; } inline int y() const { return pa.second; } bool operator<(const Star& to) const { return pa < to.pa; } Star operator+(const Star& to) const { return Star(this->x() + to.x(), this->y() + to.y()); } Star operator-(const Star& to) const { return Star(this->x() - to.x(), this->y() - to.y()); } }; bool consExists(const set<Star>& needle, const set<Star>& haystack, const Star diff) { bool res = true; for (set<Star>::iterator it = needle.begin(); it != needle.end(); ++it) { const Star cur = *it + diff; if (haystack.find(cur) == haystack.end()) { res = false; break; } } return res; } Star find(const set<Star>& needle, const set<Star>& haystack) { set<Star>::iterator origin = needle.begin(); for (set<Star>::iterator it = haystack.begin(); it != haystack.end(); ++it) { const Star diff = *it - *origin; if (consExists(needle, haystack, diff)) { return diff; } } assert(1); return Star(); } int main() { int m; while (scanf("%d\n", &m), m) { set<Star> cons, photo; for (int i = 0, x, y; i < m; ++i) { scanf("%d %d\n", &x, &y); cons.insert(Star(x, y)); } int n; scanf("%d\n", &n); for (int i =0, x, y; i < n; ++i) { scanf("%d %d\n", &x, &y); photo.insert(Star(x, y)); } const Star res = find(cons, photo); printf("%d %d\n", res.x(), res.y()); } return 0; }
5. おせんべい AOJ 0525 Osenbei
#include <cstdio> #include <vector> #include <algorithm> #include <climits> using namespace std; int solve(vector<vector<bool> > v) { int res = 0; for (int i = 0, l = (1 << v.size()); i < l; ++i) { int cur = 0; for (int j = 0; j < v[0].size(); ++j) { int turned = 0; /* turned sembei is normally false sembei */ for (int k = 0; k < v.size(); ++k) turned += (i & (1 << k) ? v[k][j]: !v[k][j]); cur += max(turned, (signed int)v.size() - turned); } res = max(res, cur); } return res == INT_MAX ? -1 : res; } int main() { int R, C; while (scanf("%d %d\n", &R, &C), R || C) { vector<vector<bool> > v(R, vector<bool>(C)); /* increase false */ for (int i = 0; i < R; ++i) for (int j = 0, t; j < C; ++j) { scanf("%d", &t); v[i][j] = (bool)t; } const int res = solve(v); printf("%d\n", res); } return 0; }
6. 船旅 AOJ 0526 Boat Travel
#include <cstdio> #include <vector> #include <queue> #include <climits> using namespace std; class Course { public: int to, value; Course(){return;} Course(int to, int value) { this->to = to, this->value = value; } bool operator<(const Course& to) const { return this->value < to.value; } }; class Way { public: int cur, value; Way(){} Way(int cur, int value) { this->cur = cur, this->value = value; } bool operator<(const Way& to) const { return this->value < to.value; } bool operator>(const Way& to) const { return this->value > to.value; } }; int solve(vector<vector<Course> > v, int from, int to) { vector<int> distance(v.size(), INT_MAX); priority_queue<Way, vector<Way>, greater<Way> > pq; pq.push(Way(from, 0)); distance[from] = 0; while (!pq.empty()) { const Way curWay = pq.top(); pq.pop(); //if (curWay.cur == to) //break; if (distance[curWay.cur] < curWay.value) continue; const vector<Course>& curCourses = v[curWay.cur]; for (int i = 0; i < curCourses.size(); ++i) { const int curVal = curWay.value + curCourses[i].value; const int curTo = curCourses[i].to; if (curVal < distance[curTo]) { distance[curTo] = curVal; pq.push(Way(curTo, curVal)); } } } const int res = distance[to]; return res == INT_MAX ? -1 : res; } int main() { int n, k; while (scanf("%d %d\n", &n, &k), n || k) { vector<vector<Course> > v(n); for (int i = 0; i < k; ++i) { int type; scanf("%d ", &type); if (type == 0) { int a, b; scanf("%d %d\n", &a, &b); a--, b--; printf("%d\n", solve(v, a, b)); } else if (type == 1) { int c, d, e; scanf("%d %d %d\n", &c, &d, &e); c--, d--; v[c].push_back(Course(d, e)); v[d].push_back(Course(c, e)); } } } return 0; }
