読者です 読者をやめる 読者になる 読者になる

第7回JOI予選問題 2週目

Programming Algorithm JOI

全完までに2時間18分。問6のデバッグでかなり食った。よろしくない。

過去と比較すると、どの程度1年間でコーディング力が変わったか観察できて面白いかもしれない。内容自体に差はないがコードの可読性は結構上がったと勝手に思っている。

JOI 2007-2008 予選 問題・データ

1. おつり AOJ 0521 Change

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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;
}