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

情報オリンピック 第7回予選問題

Programming Algorithm AOJ JOI

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

1. おつり AOJ 0521 Change

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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

AIZU ONLINE JUDGE

#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 - ペリャウドのプログラミングとか