Volume 1 / 0183->0189

2008年本選　解答

Problem 0183 : Black-and-White

#include <iostream>

using namespace std;


int main(void)
{
	char board[3][3], ch, center;
	int i, j;

	while( cin.get(ch) ){
		if( ch == '0' ) break;
		else cin.putback(ch);

		for( i=0; i<3; i++ ){
			for( j=0; j<3; j++ ){
				cin.get(ch);
				board[i][j] = ch;
			}
			cin.get(ch);
		}

		center = board[1][1];
		if( center != '+' && board[0][0] == center && board[2][2] == center )
			cout << center << endl;
		else if( center != '+' && board[0][2] == center && board[2][0] == center )
			cout << center << endl;
		else if( center != '+' && board[0][1] == center && board[2][1] == center )
			cout << center << endl;
		else if( center != '+' && board[1][0] == center && board[1][2] == center )
			cout << center << endl;
		else if( board[0][0] != '+' && board[0][0] == board[1][0] && board[1][0] == board[2][0] )
			cout << board[0][0] << endl;
		else if( board[0][2] != '+' && board[0][2] == board[1][2] && board[1][2] == board[2][2] )
			cout << board[0][2] << endl;
		else if( board[0][0] != '+' && board[0][0] == board[0][1] && board[0][1] == board[0][2] )
			cout << board[0][0] << endl;
		else if( board[2][0] != '+' && board[2][0] == board[2][1] && board[2][1] == board[2][2] )
			cout << board[2][0] << endl;
		else
			cout << "NA" << endl;

	}

	return 0;
}

Problem 0184 : Tsuruga Castle

#include <iostream>

using namespace std;


int main(void)
{
	int age[7], n, input, work, i;

	while( cin >> n ){
		if( n == 0 ) break;

		for( i=0; i<=6; i++ )
			age[i] = 0;

		while( n-- > 0 ){
			cin >> input;
			work = input/10;
			if( work > 6 ) work = 6;
			age[work]++;
		}

		for( i=0; i<=6; i++ )
			cout << age[i] << endl;
	}

	return 0;
}

Problem 0185 : Goldbach's Conjecture II

#include <iostream>

using namespace std;


bool primes[1000000];

void eratos(){
	int i, j;
	for( i=0; i<1000000; i++ )
		primes[i] = true;

	primes[0] = primes[1] = false;

	for( i=4; i<1000000; i+=2 )
		primes[i] = false;

	for( i=3; i<1000000; i+=2 ){
		if( !primes[i] ) continue;
		for( j=i+i; j<1000000; j+=i )
			primes[j] = false;
	}

	return;
}

int main(void)
{
	int n, cnt, i;
	eratos();

	while( cin >> n ){
		if( n == 0 ) break;

		cnt = 0;
		for( i=2; i<=n/2; i++ ){
			if( !primes[i] ) continue;
			if( primes[n-i] ) cnt++;
		}

		cout << cnt << endl;
	}

	return 0;
}

Problem 0186 : Aizu Chicken

#include <iostream>

using namespace std;


int main(void)
{
	int q1, b, c1, c2, q2;
	int work, n1, n2, i, j;
	while( cin >> q1 ){
		if( q1 == 0 ) break;
		cin >> b >> c1 >> c2 >> q2;

		for( n1=q2; n1>0; n1-- ){
			work = b - n1*c1;
			if( work < 0 ) continue;
			n2 = work/c2;
			if( n1 + n2 >= q1 ){
				cout << n1 << " " << n2 << endl;
				break;
			}
		}
		if( n1 == 0 ) cout << "NA" << endl;
	}

	return 0;
}

Problem 0188 : Search

#include <iostream>
#include <vector>

using namespace std;


vector<int> data;
int val;


void sort()
{
	int i, j, work;

	for( i=0; i<data.size(); i++ ){
		for( j=i+1; j<data.size(); j++ ){
			if( data[i] > data[j] ){
				work = data[i];
				data[i] = data[j];
				data[j] = work;
			}
		}
	}

	return;
}

int search( int begin, int end )
{
	if( begin > end ) return 0;
	int center = (begin+end)/2;
	if( val == data[center] || begin==end ) return 1;
	if( val < data[center] ) return 1+search( begin, center-1 );
	if( val > data[center] ) return 1+search( center+1, end );
}

int main(void)
{
	int n, input, i;

	while( cin >> n ){
		if( n == 0 ) break;

		data.clear();
		for( i=0; i<n; i++ ){
			cin >> input;
			data.push_back(input);
		}

		sort();
		cin >> val;
		cout << search( 0, n-1 ) << endl;

	}

	return 0;
}

Problem 0189 : Convenient Location

修正してAccepted（2009.11.09）

#include <iostream>
#include <limits.h>

using namespace std;


int l[11][11];
int city;

void init()
{
	int i, j;
	city = 0;
	for( i=0; i<11; i++ ){
		for( j=0; j<11; j++ ){
			if( i == j )
				l[i][j] = 0;
			else
				l[i][j] = -1;
		}
	}
	return;
}


void Floyd(){
	int i, j, k;
	for( i=0; i<=city; i++ ){
		for( j=0; j<=city; j++ ){
			if( l[i][j] == -1 ) continue;
			for( k=0; k<=city; k++ ){
				if( l[i][k] == -1 ) continue;
				if( l[j][k] == -1 || (l[j][i] + l[i][k]) < l[j][k] ){
					l[j][k] = l[k][j] = l[j][i]+l[i][k];
				}
			}
		}
	}
	//for( i=0; i<=city; i++ ){
	//	for( j=i+1; j<=city; j++ ){
	//		if( l[i][j] == -1 ) continue;
	//		for( k=0; k<=city; k++ ){
	//			if( l[j][k] == -1 ) continue;
	//			if( l[i][k] == -1 || (l[i][j] + l[j][k]) < l[i][k] ){
	//				l[i][k] = l[k][i] = l[i][j]+l[j][k];
	//			}
	//		}
	//	}
	//}
	return;
}

void calc()
{
	int sum, min, min_n, i, j;

	min = INT_MAX;
	for( i=0; i<=city; i++ ){
		sum = 0;
		for( j=0; j<=city; j++ ){
			sum += l[i][j];
		}
		if( sum < min ){
			min = sum; min_n = i;
		}
	}
	cout << min_n << " " << min << endl;

	return;
}


int main(void)
{
	int n, a, b, c;

	while( cin >> n ){
		if( n == 0 ) break;
		init();
		while( n-- > 0 ){
			cin >> a >> b >> c;
			if( city < a ) city = a;
			if( city < b ) city = b;
			if( l[a][b] == -1 || c < l[a][b] )
				l[a][b] = l[b][a] = c;
		}
		Floyd();
		calc();
	}

	return 0;
}