Volume 5 / 0521->0523

情報オリンピック 2007予選 解答

Problem 0521 : Change / おつり

大きい硬貨から引いていく。

#include <iostream>

using namespace std;


int main(void)
{
	int n, i, cnt;
	int table[6] = { 500, 100, 50, 10, 5, 1 };

	while( cin >> n, n!=0 ){
		n = 1000 - n;

		cnt = 0;
		for( i=0; i<6 && n!=0; i++ ){
			while( n >= table[i] ){
				n -= table[i];
				cnt++;
			}
		}

		cout << cnt << endl;
	}

	return 0;
}

Problem 0522 : JOI and IOI / JOIとIOI

順に探索。

#include <iostream>
#include <string>

using namespace std;


int main(void)
{
	int joi, ioi, i;
	string str;

	while( cin >> str ){
		joi = ioi = 0;
		for( i=0; i<str.size()-2; i++ ){
			if( str[i] == 'J' && str[i+1] == 'O' && str[i+2] == 'I' )
				joi++;
			if( str[i] == 'I' && str[i+1] == 'O' && str[i+2] == 'I' )
				ioi++;
		}

		cout << joi << endl;
		cout << ioi << endl;
	}

	return 0;
}

Problem 0523 : Card Game / カードゲーム

カードの枚数分の配列（手持ちのカードはtrue）を２人分用意して、どちらかの配列が全てfalse（所持していないことを表す）になるまでシミュレーション。
今考えると配列２つもいらなかったかも。

#include <iostream>
#include <vector>

using namespace std;


bool is_end( vector<bool> a )
{
	int i;

	for( i=1; i<a.size(); i++ )
		if( a[i] ) break;
	if( i == a.size() ) return true;

	return false;
}

int count( vector<bool> a )
{
	int cnt = 0;

	for( int i=1; i<a.size(); i++ )
		if( a[i] ) cnt++;

	return cnt;
}

int main(void)
{
	int n, input, i, j;
	vector<bool> taro, hanako;
	
	while( cin >> n, n!=0 ){
		taro.clear(); hanako.clear();
		taro.resize( 2*n+1, false ); hanako.resize( 2*n+1, true );
		for( i=1; i<=n; i++ ){
			cin >> input;
			taro[input] = true;
			hanako[input] = false;
		}

		i = j = 0;
		while( !is_end(taro) && !is_end(hanako) ){
			for( i=j+1; i<taro.size(); i++ ){
				if( taro[i] ){
					taro[i] = false;
					break;
				}
			}
			if( is_end(taro) ) break;
			if( i == taro.size() ) i = 0;

			for( j=i+1; j<hanako.size(); j++ ){
				if( hanako[j] ){
					hanako[j] = false;
					break;
				}
			}
			if( j == hanako.size() ) j = 0;
		}

		cout << count( hanako ) << endl;
		cout << count( taro ) << endl;
	}

	return 0;
}