3055.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:3055  User Id:fzk 
Memory:52K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>

int main() {
	int n, i, j, k;
	char mm[2][200], *w1 = &mm[0][0], *w2 = &mm[1][0], *t;
	int a[10], b[10], temp;
	bool key;
	
	scanf( "%d", &n );
	while( n-- ) {
		scanf( "%s %s", w1, w2 );
		for( i=0; i<10; i++ )
			a[i] = b[i] = 0;

		for( i=0; w1[i]; i++ )
			a[ w1[i] - '0' ]++;

		for( i=0; w2[i]; i++ )
			b[ w2[i] - '0' ]++;

		for( i=0; i<10; i++ )
			if( (a[i]==0) != (b[i]==0) )
				break;

		if( i == 10 ) {
			printf( "friends\n" );
			continue;
		}

		key = false;
		for( k=0; k<2; k++ ) {

			for( i=1; w1[i]; i++ ) {
				a[ w1[i-1] - '0' ] --;
				a[ w1[i] - '0' ] --;
				
				if( ( i != 1 || w1[0] > '1' ) && w1[i-1] > '0' && w1[i] < '9' ) {

					a[ w1[i-1] - '0' - 1 ] ++;
					a[ w1[i] - '0' + 1 ] ++;
					for( j=0; j<10; j++ )
						if( (a[j]==0) != (b[j]==0) )
							break;
					if( j == 10 ) {
						key = true;
						goto end;
					}
					
					a[ w1[i-1] - '0' - 1 ] --;
					a[ w1[i] - '0' + 1 ] --;
				}

				if( w1[i-1] < '9' && w1[i] > '0' ) {

					a[ w1[i-1] - '0' + 1 ] ++;
					a[ w1[i] - '0' - 1 ] ++;
					for( j=0; j<10; j++ )
						if( (a[j]==0) != (b[j]==0) )
							break;
					if( j == 10 ) {
						key = true;
						goto end;
					}
					
					a[ w1[i-1] - '0' + 1 ] --;
					a[ w1[i] - '0' - 1 ] --;
				}

				a[ w1[i-1] - '0' ] ++;
				a[ w1[i] - '0' ] ++;
			}

			t = w1;
			w1 = w2;
			w2 = t;
			for( i=0; i<10; i++ ) {
				temp = a[i];
				a[i] = b[i];
				b[i] = temp;
			}
		}
end:
		if( key )
			printf( "almost friends\n" );
		else
			printf( "nothing\n" );
	}
	return 0;
}