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