Volume 5 / 0532->0535

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

Problem 0532 : Time Card / タイムカード

#include <iostream>

using namespace std;


int main(void)
{
	int h1, h2, m1, m2, s1, s2, t;

	for( int i=0; i<3; i++ ){
		cin >> h1 >> m1 >> s1 >> h2 >> m2 >> s2;
		t = (h2*60*60+m2*60+s2)-(h1*60*60+m1*60+s1);
		cout << t/(60*60) << " ";
		t %= 60*60;
		cout << t/60 << " ";
		t %= 60;
		cout << t << endl;
	}
	return 0;
}

Problem 0533 : Contest / コンテスト

#include <iostream>

using namespace std;


int main(void)
{
	int p[2][10], sum, n, i, j, k;

	for( i=0; i<2; i++ )
		for( j=0; j<10; j++ )
			cin >> p[i][j];


	for( i=0; i<2; i++ ){
		sum = 0;
		for( k=0; k<3; k++ ){
			n = 0;
			for( j=0; j<10; j++ )
				if( p[i][n] < p[i][j] )
					n = j;
			sum += p[i][n];
			p[i][n] = -1;
		}
		if( !i )
			cout << sum;
		else
			cout << " " << sum << endl;
	}

	return 0;
}

Problem 0534 : Chain / 連鎖

#include <iostream>
#include <vector>

using namespace std;


int calc( vector<int> src, int p, int q ){
	int i, j;

	do {
		for( i=0; src[p-i]==src[p] && p-i>0; i++ );
		for( j=0; src[q+j]==src[q] && q+j<src.size(); j++ );
		if( i+j < 4 ) return p+src.size()-q;
		p -= i; q += j;
	} while( src[p] == src[q] );

	return p+src.size()-q;
}

int main(void)
{
	int n, M, i, tmp, new_val;
	vector<int> chain;

	while( cin >> n, n!=0 ){
		chain.resize(n+1);

		chain[0] = chain[n] = 0;
		for( i=1; i<=n; i++ )
			cin >> chain[i];

		M = 10001;
		for( i=2; i<n; i++ ){
			if( chain[i]!=chain[i-1] ){
				tmp = chain[i];
				chain[i] = chain[i-1];
				new_val = calc( chain, i-1, i );
				if( M > new_val )
					M = new_val;
				chain[i] = tmp;
			}
			if( chain[i]!=chain[i+1] ){
				tmp = chain[i];
				chain[i] = chain[i+1];
				new_val = calc( chain, i, i+1 );
				if( M > new_val )
					M = new_val;
				chain[i] = tmp;
			}
		}

		cout << M << endl;
	}

	return 0;
}

Problem 0535 : Crossing Black Ice / 薄氷渡り

氷の状態を入れる配列をベクターでやったら時間切れだった。
動的じゃなくていいような場合は、普通に配列でやったほうがいいですね。

#include <iostream>

using namespace std;

#define MAX 90

int calc( int ice[MAX+2][MAX+2], int x, int y )
{
	int result, tmp;

	if( !ice[y-1][x] && !ice[y+1][x] && !ice[y][x-1] && !ice[y][x+1] )
		return 1;


	result = 0;
	if( ice[y-1][x] ){
		ice[y-1][x] = 0;
		tmp = calc( ice, x, y-1 );
		ice[y-1][x] = 1;
		if( result < tmp )
			result = tmp;
	}
	if( ice[y+1][x] ){
		ice[y+1][x] = 0;
		tmp = calc( ice, x, y+1 );
		ice[y+1][x] = 1;
		if( result < tmp )
			result = tmp;
	}
	if( ice[y][x-1] ){
		ice[y][x-1] = 0;
		tmp = calc( ice, x-1, y );
		ice[y][x-1] = 1;
		if( result < tmp )
			result = tmp;
	}
	if( ice[y][x+1] ){
		ice[y][x+1] = 0;
		tmp = calc( ice, x+1, y );
		ice[y][x+1] = 1;
		if( result < tmp )
			result = tmp;
	}

	return result+1;
}

int main(void)
{
	int m, n, max, tmp, i, j;
	int ice[MAX+2][MAX+2];

	while( cin >> m >> n, m!=0 && n!=0 ){
		for( i=0; i<=n+1; i++ )
			for( j=0; j<=m+1; j++ )
				ice[i][j] = 0;

		for( i=1; i<=n; i++ )
			for( j=1; j<=m; j++ )
				cin >> ice[i][j];

		max = -1;
		for( i=1; i<=n; i++ ){
			for( j=1; j<=m; j++ ){
				if( ice[i][j] ){
					ice[i][j] = 0;
					tmp = calc( ice, j, i );
					ice[i][j] = 1;
					if( max < tmp )
						max = tmp;
				}
			}
		}

		cout << max << endl;

	}

	return 0;
}