1月 2011 | 已更站

2011年1月27日星期四

[Zerojudge]a016: 數獨(SUDOKU)

這題就硬爆，檢查每個部分是否符合數獨的要求即可。

P.S. 我的程式碼中寫了一個奇怪的函式check()XD""

[C++](6ms, 674KB)

	#include<iostream>
	using namespace std;

	bool check( int i, int sudoku[9][9] )
	{
	int centerx = (i%3)*3+1;
	int centery = (i/3)*3+1;
	bool remember[10] = {0};

	for( int iy = -1 ; iy <= 1 ; iy++ )
	for( int ix = -1 ; ix <= 1 ; ix++ )
	if( remember[sudoku[centery+iy][centerx+ix]] )
	return 1;
	else
	remember[sudoku[centery+iy][centerx+ix]] = 1;

	memset( remember, 0, sizeof(remember) );
	for( int row = 0 ; row < 9 ; row++ )
	if( remember[sudoku[row][i]] )
	return 1;
	else
	remember[sudoku[row][i]] = 1;

	memset( remember, 0, sizeof(remember) );
	for( int col = 0 ; col < 9 ; col++ )
	if( remember[sudoku[i][col]] )
	return 1;
	else
	remember[sudoku[i][col]] = 1;

	return 0;

	}

	int main()
	{
	while( 1 )
	{
	int sudoku[9][9] = {0};
	for( int i = 0 ; i < 9 ; i++ )
	for( int j = 0 ; j < 9 ; j++ )
	cin >> sudoku[i][j];
	if( cin.eof() )
	break;

	bool answer = 0;
	for( int i = 0 ; i < 9 ; i++ )
	answer \|= check( i, sudoku );
	if( answer )
	cout << "no\n";
	else
	cout << "yes\n";
	}
	return 0;
	}

view raw Zerojudgea016.cpp hosted with ❤ by GitHub

2011年1月22日星期六

每個數有有加或沒有加兩種狀況，
直接利用遞迴把所有狀況都跑出來看看即可得解。

P.S.
為了避免印出重複的組合，
在你有把某數加進去的情況，
重複再找相同值的數是OK的；
但是若你已經不打算把這個數字加進去的時候，
記得要跳掉所有跟這個數相同值的數。
例.
今天你找到+2，
那麼你可以再繼續遞迴+2沒關係，
這樣不會重複。
除非你是已經打算不再找+2了，
那麼之後都不要讓遞迴再遞到+2。

[C](0.012)

	#include<stdio.h>

	int sum( int t, int now, int nowsum, int suma[], int sump, int x[], int xlimit )
	{
	if( now == xlimit )
	return 0;
	nowsum += x[now];
	int i;
	if( nowsum > t )
	{
	for( i = now+1 ; i < xlimit ; i++ )
	if( x[now] != x[i] )
	break;

	return sum( t, i, nowsum-x[now], suma, sump, x, xlimit );
	}
	else if( nowsum < t )
	{
	if( now == xlimit-1 )
	return 0;
	suma[sump++] = x[now];
	int result = sum( t, now+1, nowsum, suma, sump, x, xlimit );

	for( i = now+1 ; i < xlimit ; i++ )
	if( x[now] != x[i] )
	break;

	result += sum( t, i, nowsum-x[now], suma, sump-1, x, xlimit );
	return result;
	}
	else
	{
	int print = 0;
	for( i = 0 ; i < sump ; i++ )
	{
	if( print )
	printf( "+" );
	printf( "%d", suma[i] );
	print = 1;
	}
	if( print )
	printf( "+" );
	printf( "%d", x[now] );
	printf( "\n" );
	for( i = now+1 ; i < xlimit ; i++ )
	if( x[now] != x[i] )
	break;
	return 1 + sum( t, i, nowsum-x[now], suma, sump, x, xlimit );
	}
	}

	int main()
	{
	int t;
	while( scanf( "%d", &t ) != EOF )
	{
	int n;
	scanf( "%d", &n );

	if( t == 0 && n == 0 )
	break;

	int x[20] = {0};
	int i;
	for( i = 0 ; i < n ; i++ )
	scanf( "%d", &x[i] );
	printf( "Sums of %d:\n", t );

	int suma[20] = {0};
	if( !sum( t, 0, 0, suma, 0, x, n ) )
	printf( "NONE\n" );
	}
	return 0;
	}

view raw UVa574.c hosted with ❤ by GitHub

[UVa]11121:Base -2

這題可以先將輸入的數字的絕對值換成2進位制，
例如：7 => 111、-7 => 111。
再來從小到大看看它由哪些2的幾次方組成，
如果該次方與輸入的數字同號時，換成base(-2)的時候，也一樣會有該次方；
如果該次方與輸入的數字不同號時，換成base(-2)的時候，就需要該次方與該次方+1兩個所組成。
例如：
7 = 111 有2^0、2^1、2^2。
2^0 -> (-2)^0 直接換過來即可。
2^1 -> ((-2)^1 + (-2)^2) 該次方+該次方的下一個次方即可組成。
2^2 -> (-2)^2 直接換過來即可。
加起來會有 1個(-2)^0，1個(-2)^1，2個(-2)^2，
2個(-2)^2要進位，但是對於base(-2)又得再利用(-2)^3+(-2)^4才能組起來，
所以答案就會是 11011 。

[C](0.044)

	#include<stdio.h>
	#include<stdlib.h>

	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int x;
	for( x = 1 ; x <= N ; x++ )
	{
	int n;
	scanf( "%d", &n );

	if( n == 0 )
	{
	printf( "Case #%d: 0\n", x );
	continue;
	}

	int b[50] = {0}, bnum = 0;
	int ntemp = abs( n );
	while( ntemp )
	{
	b[bnum++] = ntemp % 2;
	ntemp /= 2;
	}

	int negorpos = ( n > 0 )? 0 : 1;
	int carry = 0;
	int i;
	for( i = 0 ; i < bnum ; i++ )
	{
	int temp = carry;
	carry = ( b[i] + temp ) / 2;
	b[i] = ( b[i] + temp ) % 2;
	if( i % 2 != negorpos && b[i] )
	carry++;
	}
	if( carry )
	{
	if( i % 2 != negorpos )
	{
	b[bnum++] = 1;
	b[bnum++] = 1;
	}
	else
	b[bnum++] = 1;
	}

	printf( "Case #%d: ", x );
	for( i = bnum-1 ; i >= 0 ; i-- )
	printf( "%d", b[i] );
	printf( "\n" );
	}
	}
	return 0;
	}

view raw UVa11121.c hosted with ❤ by GitHub

2011年1月21日星期五

[UVa]755:487--3279

先將每一種不同格式的電話號碼全部換成7位數整數，
利用一個hash紀錄每一種電話號碼的出現的次數，
將出現兩次以上的電話號碼紀錄到一個陣列裡面，
再利用quicksort將這個陣列以電話號碼來排序，
最後從頭將電話號碼及其出現的次數輸出來即可。

[C](0.420)

	#include<stdio.h>
	#include<string.h>
	#include<ctype.h>

	void quicksort( int start, int end, int array[] )
	{
	if( start < end )
	{
	int change = start;
	int i;
	int temp;
	for( i = start+1 ; i < end ; i++ )
	if( array[i] < array[start] )
	{
	change++;

	temp = array[i];
	array[i] = array[change];
	array[change] = temp;
	}

	temp = array[start];
	array[start] = array[change];
	array[change] = temp;

	quicksort( start, change, array );
	quicksort( change+1, end, array );
	}
	}

	int hash_numbers[10000005] = {0};

	int main()
	{
	int datasets;
	int blank;
	while( scanf( "%d", &datasets ) != EOF )
	{
	blank = 0 ;
	int numbers;

	while( datasets-- )
	{
	scanf( "%d", &numbers );
	getchar();

	int i;
	memset( hash_numbers, 0, sizeof(hash_numbers) );
	int output[100005] = {0};
	int output_saved = 0;
	for( i = 0 ; i < numbers ; i++ )
	{
	char tempnum[1005];
	gets( tempnum );

	int templen = strlen( tempnum );
	int tempnumint = 0;
	int j;
	for( j = 0 ; j < templen ; j++ )
	{
	if( isalnum( tempnum[j] ) )
	{
	tempnumint *= 10;
	if( isdigit( tempnum[j] ) )
	tempnumint += (int)(tempnum[j] - '0');
	else
	{
	switch( tempnum[j] )
	{
	case 'A': case 'B': case 'C':
	tempnumint += 2;
	break;
	case 'D': case 'E': case 'F':
	tempnumint += 3;
	break;
	case 'G': case 'H': case 'I':
	tempnumint += 4;
	break;
	case 'J': case 'K': case 'L':
	tempnumint += 5;
	break;
	case 'M': case 'N': case 'O':
	tempnumint += 6;
	break;
	case 'P': case 'R': case 'S':
	tempnumint += 7;
	break;
	case 'T': case 'U': case 'V':
	tempnumint += 8;
	break;
	case 'W': case 'X': case 'Y':
	tempnumint += 9;
	break;
	}
	}
	}
	}
	hash_numbers[tempnumint]++;
	if( hash_numbers[tempnumint] == 2 )
	output[output_saved++] = tempnumint;
	}
	quicksort( 0, output_saved, output );

	if( blank )
	printf( "\n" );
	blank = 1;

	for( i = 0 ; i < output_saved ; i++ )
	printf( "%03d-%04d %d\n", output[i]/10000, output[i]%10000, hash_numbers[output[i]] );
	if( output_saved == 0 )
	printf( "No duplicates.\n" );
	}
	}
	return 0;
	}

view raw UVa755.c hosted with ❤ by GitHub

[UVa]10878:Decode the tape

解碼的依據就是二進位的ASCII碼這樣。

[C++](0.020)

	#include<iostream>
	using namespace std;

	int main()
	{
	string s;
	bool print = 0;
	while( getline( cin, s ) )
	{
	if( s[0] == '_' )
	{
	if( print )
	cout << '\n';
	}
	else
	{
	int letter = 0;
	for( int i = 0 ; i < s.length() ; i++ )
	{
	switch( s[i] )
	{
	case '.': case '\|':
	break;
	case 'o':
	letter *= 2;
	letter++;
	break;
	case ' ':
	letter *= 2;
	break;
	}
	}
	cout << static_cast<char>(letter);
	}
	}
	return 0;
	}

view raw Zerojudged351.cpp hosted with ❤ by GitHub

[UVa]10783:Odd Sum

照著題目所要求的奇數之和即可。

[C++](0.012)

	#include<iostream>
	using namespace std;

	int main()
	{
	int T;
	while( cin >> T )
	{
	for( int i = 1 ; i <= T ; i++ )
	{
	int a, b;
	cin >> a >> b;

	int sum = 0;
	for( int j = a ; j <= b ; j++ )
	if( j % 2 )
	sum += j;
	cout << "Case " << i << ": " << sum << endl;
	}
	}
	return 0;
	}

view raw Zerojudgec022.cpp hosted with ❤ by GitHub

[UVa]10699:Count the factors

直接從2開始到根號N去除除看能不能整除，
能整除就知道其質因數有此數，因此就把質因數個數加一，
接著把N中所有含有的這個質因數除乾淨，再往下一個搜尋。

[C++](0.012)

	#include<iostream>
	#include<cmath>
	using namespace std;

	int main()
	{
	int n;
	while( cin >> n && n != 0 )
	{
	int output = n;
	int factor = 0;
	int limit = static_cast<int>(sqrt(n));
	for( int i = 2 ; i <= limit ; i++ )
	if( n % i == 0 )
	{
	factor++;
	while( n % i == 0 ) n /= i;
	}
	if( n != 1 )
	factor++;
	cout << output << " : " << factor << endl;
	}
	return 0;
	}

view raw Zerojudged120.cpp hosted with ❤ by GitHub

[UVa]10696:f91

照著題目所說的去遞迴即可得解。

[C++](0.684)

	#include<iostream>
	using namespace std;

	int f91( int N )
	{
	if( N <= 100 )
	return f91( f91( N+11 ) );
	else
	return N-10;
	}

	int main()
	{
	int N;
	while( cin >> N && N != 0 )
	cout << "f91(" << N << ") = " << f91(N) << endl;
	return 0;
	}

view raw Zerojudgec002.cpp hosted with ❤ by GitHub

[UVa]100:The 3n + 1 problem

新站連結於http://knightzone.org/?p=1182。

[UVa]579:ClockHands

新站連結於http://knightzone.org/?p=1214。

[UVa]541:Error Correction

檢查每行與每列的1的個數是否為偶數，
如果有某一行與某一列不吻合，
則要換的那個位元就是(那行,那列)。
如果有多行多列，或是行有問題但是列沒問題，或者反過來，
則都沒辦法判斷要換那個位元。
如果都吻合，那就OK，沒什麼問題。

[C](0.016)

	#include<stdio.h>

	int main()
	{
	int n;
	while( scanf( "%d", &n ) != EOF && n != 0 )
	{
	int matrix[105][105] = {0};
	int i, j;

	int row = -1, col = -1, check;
	int fail = 0;
	for( i = 0 ; i < n ; i++ )
	{
	check = 0;
	for( j = 0 ; j < n ; j++ )
	{
	scanf( "%d", &matrix[i][j] );
	check ^= matrix[i][j];
	}
	if( check )
	{
	if( row == -1 )
	row = i;
	else
	fail = 1;
	}
	}

	if( !fail )
	{
	for( i = 0 ; i < n ; i++ )
	{
	check = 0;
	for( j = 0 ; j < n ; j++ )
	check ^= matrix[j][i];
	if( check )
	{
	if( col == -1 )
	col = i;
	else
	fail = 1;
	}
	}
	}

	if( fail )
	printf( "Corrupt\n" );
	else
	{
	if( row == -1 && col == -1 )
	printf( "OK\n" );
	else if( (row == -1 && col != -1) \|\| (row != -1 && col == -1) )
	printf( "Corrupt\n" );
	else
	printf( "Change bit (%d,%d)\n", row+1, col+1 );
	}
	}
	return 0;
	}

view raw UVa541.c hosted with ❤ by GitHub

2011年1月20日星期四

[UVa]591:Box of Bricks

新站連結於http://knightzone.org/?p=1217。

[UVa]11172:Relational Operator

照題意判斷大小輸出所求即可。

[C](0.012)

	#include<stdio.h>

	int main()
	{
	int total;
	while( scanf( "%d", &total ) != EOF )
	{
	int a, b;
	int i;
	for( i = 0 ; i < total ; i++ )
	{
	scanf( "%d%d", &a, &b );
	if( a > b )
	printf( ">\n" );
	else if( a < b )
	printf( "<\n" );
	else
	printf( "=\n" );
	}
	}
	return 0;
	}

view raw UVa11172.c hosted with ❤ by GitHub

[C++](0.016)

	#include<iostream>
	using namespace std;

	int main()
	{
	int total;
	while( cin >> total )
	{
	int a, b;
	for( int i = 0 ; i < total ; i++ )
	{
	cin >> a >> b;
	if( a > b )
	cout << '>' << endl;
	else if( a < b )
	cout << '<' << endl;
	else
	cout << '=' << endl;
	}
	}
	return 0;
	}

view raw Zerojudged143.cpp hosted with ❤ by GitHub

[UVa]10071:Back to High School Physics

這題只要套公式即可得解。

P.S. 因為是一等加速度，所以位移的公式就是平均速度 * 經過的時間，
而因為正好是要兩倍時間後的位移，所以此時的速度即為平均速度，再乘上2倍時間即得解。

[C](0.028)

	#include<stdio.h>

	int main()
	{
	int v, t;
	while( scanf( "%d%d", &v, &t ) != EOF )
	printf( "%d\n", 2vt );
	return 0;
	}

view raw UVa10071.c hosted with ❤ by GitHub

[C++](0.132)

	#include<iostream>
	using namespace std;

	int main()
	{
	int v, t;
	while( cin >> v >> t )
	cout << 2vt << endl;
	return 0;
	}

view raw Zerojudged226.cpp hosted with ❤ by GitHub

[UVa]10062:Tell me the frequencies!

這題的話，
我是先一個一個字看它的ASCII碼是多少，
把陣列中它的ASCII碼那格加1，
表示這個字多出現了一次。

我用了三個變數，
一個存最大出現的ASCII碼，
一個存最小出現的ASCII碼，
一個存最多出現的次數。

然後我就從出現一次開始搜尋，直到最多出現的次數，
每次搜尋都是從最大ASCII碼搜尋到最小ASCII碼這樣，
搜尋到次數一樣就輸出。

(當然這題用Sort也是OK啦XD)

[C](0.008)

	#include<stdio.h>
	#include<string.h>

	int min( int x, int y )
	{
	return ( x > y )? y : x;
	}

	int max( int x, int y )
	{
	return ( x > y )? x : y;
	}

	int main()
	{
	char s[1005];
	int blank = 0;
	while( gets(s) )
	{
	if( blank )
	printf( "\n" );
	int ASCII[130] = {0};
	int length = strlen(s);
	int i;

	int min_ASCII = 200;
	int max_ASCII = 0;
	int max_count = 0;

	for( i = 0 ; i < length ; i++ )
	{
	ASCII[ (int)s[i] ]++;
	min_ASCII = min( min_ASCII, (int)s[i] );
	max_ASCII = max( max_ASCII, (int)s[i] );
	max_count = max( max_count, ASCII[ (int)s[i] ] );
	}

	int j;
	for( i = 1 ; i <= max_count ; i++ )
	for( j = max_ASCII ; j >= min_ASCII ; j-- )
	if( ASCII[j] == i )
	printf( "%d %d\n", j , ASCII[j] );
	blank = 1;
	}
	return 0;
	}

view raw ACM10062.c hosted with ❤ by GitHub

[UVa]299:Train Swapping

其實就是問Bubble Sort交換的次數...

[C](0.012)

	#include<stdio.h>

	void swap( int a, int b )
	{
	(a) ^= (b) ^= (a) ^= (b);
	}

	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int L;
	int i;
	for( i = 0 ; i < N ; i++ )
	{
	scanf( "%d", &L );

	int order[55] = {0};
	int j;
	for( j = 0 ; j < L ; j++ )
	scanf( "%d", &order[j] );

	int k;
	int swaps = 0;
	for( j = 0 ; j < L ; j++ )
	for( k = L-1 ; k > j ; k-- )
	if( order[k] < order[k-1] )
	{
	swaps++;
	swap( &order[k], &order[k-1] );
	}
	printf( "Optimal train swapping takes %d swaps.\n", swaps );
	}
	}
	return 0;
	}

view raw ACM299.c hosted with ❤ by GitHub

[UVa]10055:Hashmat the Brave Warrior

新站連結於http://knightzone.org/?p=1233。

2011年1月19日星期三

[Zerojudge]d351: 10878 - Decode the tape

解碼的依據就是二進位的ASCII碼這樣。

[C++](8ms, 720KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	string s;
	bool print = 0;
	while( getline( cin, s ) )
	{
	if( s[0] == '_' )
	{
	if( print )
	cout << '\n';
	}
	else
	{
	int letter = 0;
	for( int i = 0 ; i < s.length() ; i++ )
	{
	switch( s[i] )
	{
	case '.': case '\|':
	break;
	case 'o':
	letter *= 2;
	letter++;
	break;
	case ' ':
	letter *= 2;
	break;
	}
	}
	cout << static_cast<char>(letter);
	}
	}
	return 0;
	}

view raw Zerojudged351.cpp hosted with ❤ by GitHub

[Zerojudge]c022: 10783 - Odd Sum

照著題目所要求的奇數之和即可。

[C++](4ms, 708KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int T;
	while( cin >> T )
	{
	for( int i = 1 ; i <= T ; i++ )
	{
	int a, b;
	cin >> a >> b;

	int sum = 0;
	for( int j = a ; j <= b ; j++ )
	if( j % 2 )
	sum += j;
	cout << "Case " << i << ": " << sum << endl;
	}
	}
	return 0;
	}

view raw Zerojudgec022.cpp hosted with ❤ by GitHub

[Zerojudge]d120: 10699 - Count the factors

直接從2開始到根號N去除除看能不能整除，
能整除就知道其質因數有此數，因此就把質因數個數加一，
接著把N中所有含有的這個質因數除乾淨，再往下一個搜尋。

[C++](8ms, 700KB)

	#include<iostream>
	#include<cmath>
	using namespace std;

	int main()
	{
	int n;
	while( cin >> n && n != 0 )
	{
	int output = n;
	int factor = 0;
	int limit = static_cast<int>(sqrt(n));
	for( int i = 2 ; i <= limit ; i++ )
	if( n % i == 0 )
	{
	factor++;
	while( n % i == 0 ) n /= i;
	}
	if( n != 1 )
	factor++;
	cout << output << " : " << factor << endl;
	}
	return 0;
	}

view raw Zerojudged120.cpp hosted with ❤ by GitHub

[Zerojudge]c002: f91

照著題目所說的去遞迴即可得解。

[C++](10ms, 698KB)

	#include<iostream>
	using namespace std;

	int f91( int N )
	{
	if( N <= 100 )
	return f91( f91( N+11 ) );
	else
	return N-10;
	}

	int main()
	{
	int N;
	while( cin >> N && N != 0 )
	cout << "f91(" << N << ") = " << f91(N) << endl;
	return 0;
	}

view raw Zerojudgec002.cpp hosted with ❤ by GitHub

[Zerojudge]c039: The 3n + 1 problem

照著題目所說的去遞迴即可得解。

[C++](34ms, 700KB)

	#include<iostream>
	using namespace std;

	int f( int n )
	{
	if( n == 1 )
	return 1;
	else if( n % 2 )
	return f( 3*n+1 )+1;
	else
	return f( n/2 )+1;
	}

	int main()
	{
	int i, j;
	while( cin >> i >> j )
	{
	int min_num = min( i, j );
	int max_num = max( i, j );
	int answer = 0;
	for( int n = min_num ; n <= max_num ; n++ )
	answer = max( answer, f(n) );
	cout << i << ' ' << j << ' ' << answer << endl;
	}
	return 0;
	}

view raw Zerojudgec039.cpp hosted with ❤ by GitHub

[Zerojudge]d095: 579 - ClockHands

先把時鐘刻劃360格，一格1度，
則再將時針指向的位置的度數去跟分針指向的位置的度數進行絕對值相減，
即可得解。
(若大於180度，就利用360去減其值的絕對值去把它減到小於180度為止)

P.S. 時針指的刻度算法：小時*30(一個小時30度) + 分/60 * 30(因為分針走一圈，時針就走30度)
分針指的刻度算法：分*6(五分鐘走30度，則一分鐘走6度)

[C++](12ms, 762KB)

	#include<iostream>
	#include<iomanip>
	#include<cmath>
	using namespace std;

	int main()
	{
	int H, M;
	char recycle;
	while( cin >> H >> recycle >> M )
	{
	if( H == 0 && M == 0 )
	break;
	double H_angle = static_cast<double>(H) * 30.0 + static_cast<double>(M) / 60.0 * 30.0;
	double M_angle = static_cast<double>(M) * 6.0;
	double angle = fabs( H_angle-M_angle );
	while( angle > 180 )
	angle = fabs( 360 - angle );
	cout << fixed << setprecision(3) << angle << endl;
	}
	return 0;
	}

view raw Zerojudged095.cpp hosted with ❤ by GitHub

[Zerojudge]c067: Box of Bricks

先找出平均數，就可以知道後來每一堆積木的個數。
將每一堆大於平均數的積木，將其個數減去平均數的數字(也就意味這堆要搬多少個盒子到別堆去)加起來就是答案。

[C++](8ms, 702KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int n;
	int boxh[55] = {0};
	int setnum = 0;
	while( cin >> n && n != 0 )
	{
	setnum++;
	int average = 0;
	int move = 0;
	for( int i = 0 ; i < n ; i++ )
	{
	cin >> boxh[i];
	average += boxh[i];
	}
	average /= n;
	for( int i = 0 ; i < n ; i++ )
	if( boxh[i] > average )
	move += boxh[i] - average;
	cout << "Set #" << setnum << endl;
	cout << "The minimum number of moves is " << move << ".\n\n";
	}
	return 0;
	}

view raw Zerojudgec067.cpp hosted with ❤ by GitHub

[Zerojudge]d143: Q11172: Relational Operators

照題意判斷大小輸出所求即可。

[C](8ms, 246KB)

	#include<stdio.h>

	int main()
	{
	int total;
	while( scanf( "%d", &total ) != EOF )
	{
	int a, b;
	int i;
	for( i = 0 ; i < total ; i++ )
	{
	scanf( "%d%d", &a, &b );
	if( a > b )
	printf( ">\n" );
	else if( a < b )
	printf( "<\n" );
	else
	printf( "=\n" );
	}
	}
	return 0;
	}

view raw UVa11172.c hosted with ❤ by GitHub

[C++](4ms, 686KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int total;
	while( cin >> total )
	{
	int a, b;
	for( int i = 0 ; i < total ; i++ )
	{
	cin >> a >> b;
	if( a > b )
	cout << '>' << endl;
	else if( a < b )
	cout << '<' << endl;
	else
	cout << '=' << endl;
	}
	}
	return 0;
	}

view raw Zerojudged143.cpp hosted with ❤ by GitHub

[Zerojudge]d226: 10071 - Back to High School Physics

這題只要套公式即可得解。

P.S. 因為是一等加速度，所以位移的公式就是平均速度 * 經過的時間，
而因為正好是要兩倍時間後的位移，所以此時的速度即為平均速度，再乘上2倍時間即得解。

[C](2ms, 264KB)

	#include<stdio.h>

	int main()
	{
	int v, t;
	while( scanf( "%d%d", &v, &t ) != EOF )
	printf( "%d\n", 2vt );
	return 0;
	}

view raw UVa10071.c hosted with ❤ by GitHub

[C++](12ms, 692KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int v, t;
	while( cin >> v >> t )
	cout << 2vt << endl;
	return 0;
	}

view raw Zerojudged226.cpp hosted with ❤ by GitHub

[Zerojudge]a017: 五則運算

利用stringstream將運算元及運算子以空白隔開，
並一一讀取。

讀到運算元就丟入運算元的堆疊中，
讀到運算子就丟入運算子的堆疊中，
並判斷上一個運算子的優先度是否大於等於它，
若是的話，就一直執行，直到遇到比它小的運算子才放進堆疊中。

唯'('和')'比較特別，
丟入堆疊時：
( > * = / = % > + > - > )，
判斷時：
* = / = % > + > - > ( 。

遇到')'，要一直輸出，只要輸出到'('，就把'('消去，也不把自己')'存進堆疊中。

這樣做完即可得解。

[C++](6ms, 766KB)

	#include<iostream>
	#include<sstream>
	#include<cctype>
	using namespace std;

	int main()
	{
	string s;
	while( getline( cin, s ) )
	{
	string oper;
	stringstream ss;
	char operators[1000] = {0};
	int operands[1000] = {0};
	int operators_length = 0;
	int operands_length = 0;
	ss.clear();
	ss.str(s);

	while( ss >> oper )
	{
	if( isdigit(oper[0]) )
	{
	int number = 0;
	for( int i = 0 ; i < oper.length() ; i++ )
	{
	number *= 10;
	number += oper[i]-'0';
	}
	operands[operands_length++] = number;
	}
	else
	{
	switch( oper[0] )
	{
	case '+': case '-':
	while( operators_length > 0 )
	{
	if( operators[operators_length-1] == '+' )
	{
	operands[operands_length-2] += operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	else if( operators[operators_length-1] == '-' )
	{
	operands[operands_length-2] -= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	else if( operators[operators_length-1] == '*' )
	{
	operands[operands_length-2] *= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	else if( operators[operators_length-1] == '/' )
	{
	operands[operands_length-2] /= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	else if( operators[operators_length-1] == '%' )
	{
	operands[operands_length-2] %= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	else break;
	}
	operators[operators_length++] = oper[0];
	break;
	case '*': case '/': case '%':
	while( operators_length > 0 )
	{
	if( operators[operators_length-1] == '*' )
	{
	operands[operands_length-2] *= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	else if( operators[operators_length-1] == '/' )
	{
	operands[operands_length-2] /= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	else if( operators[operators_length-1] == '%' )
	{
	operands[operands_length-2] %= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	else break;
	}
	operators[operators_length++] = oper[0];
	break;
	case '(':
	operators[operators_length++] = oper[0];
	break;
	case ')':
	for( int i = operators_length-1; operators[i] != '(' ; i-- )
	{
	if( operators[i] == '+' )
	{
	operands[operands_length-2] += operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	if( operators[i] == '-' )
	{
	operands[operands_length-2] -= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	if( operators[i] == '*' )
	{
	operands[operands_length-2] *= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	if( operators[i] == '/' )
	{
	operands[operands_length-2] /= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	if( operators[i] == '%' )
	{
	operands[operands_length-2] %= operands[operands_length-1];
	operands_length--;
	operators_length--;
	}
	}
	operators_length--;
	break;
	}
	}
	}
	for( operators_length-- ; operators_length >= 0 ; operators_length-- )
	{
	if( operators[operators_length] == '+' )
	{
	operands[operands_length-2] += operands[operands_length-1];
	operands_length--;
	}
	if( operators[operators_length] == '-' )
	{
	operands[operands_length-2] -= operands[operands_length-1];
	operands_length--;
	}
	if( operators[operators_length] == '*' )
	{
	operands[operands_length-2] *= operands[operands_length-1];
	operands_length--;
	}
	if( operators[operators_length] == '/' )
	{
	operands[operands_length-2] /= operands[operands_length-1];
	operands_length--;
	}
	if( operators[operators_length] == '%' )
	{
	operands[operands_length-2] %= operands[operands_length-1];
	operands_length--;
	}
	}
	cout << operands[0] << endl;
	}
	return 0;
	}

view raw Zerojudgea017.cpp hosted with ❤ by GitHub

2011年1月18日星期二

[Zerojudge]a015: 矩陣的翻轉

本題就是row和column倒過來輸出即可。

[C++](4ms, 728KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int A[105][105] = {0};
	int row, column;
	while( cin >> row >> column )
	{
	for( int i = 0 ; i < row ; i++ )
	for( int j = 0 ; j < column ; j++ )
	cin >> A[i][j];
	for( int i = 0 ; i < column ; i++ )
	{
	for( int j = 0 ; j < row ; j++ )
	{
	if( j )
	cout << ' ';
	cout << A[j][i];
	}
	cout << endl;
	}
	}
	return 0;
	}

view raw Zerojudgea015.cpp hosted with ❤ by GitHub

[Zerojudge]a013: 羅馬數字

這題可分成兩個部分來做，
一個是把羅馬數字變成阿拉伯數字，
另外一個是把阿拉伯數字變成羅馬數字。

羅馬數字變成阿拉伯數字就是，
遇到其羅馬字母就將結果加上其代表數值，
再判斷它前一個字母是不是小於它，
如果是就減掉前面那個小於它的值的兩倍。
(因為你在前面執行到它的時候有加的它的值，所以不僅要把多的去掉，
還要把它原本減一次的意思表示出來，導致要扣兩倍。)

P.S. 根據羅馬數字的規則，會有這種狀況的只有：IV、IX、XL、XC、CD、CM。

而把阿拉伯數字變成羅馬數字就以
M、CM、D、CD、C、XC、L、XL、X、IX、V、IV、I
這個順序把大於它的值一直減掉，然後一直輸出，即可得解。

[C++](4ms, 740KB)

	#include<iostream>
	using namespace std;

	int roman_to_number( string s )
	{
	int output = 0;
	for( int i = 0 ; i < s.length() ; i++)
	{
	switch( s[i] )
	{
	case 'I':
	output++;
	break;
	case 'V':
	output += 5;
	if( s[i-1] == 'I' )
	output -= 2;
	break;
	case 'X':
	output += 10;
	if( s[i-1] == 'I' )
	output -= 2;
	break;
	case 'L':
	output += 50;
	if( s[i-1] == 'X' )
	output -= 20;
	break;
	case 'C':
	output += 100;
	if( s[i-1] == 'X' )
	output -= 20;
	break;
	case 'D':
	output += 500;
	if( s[i-1] == 'C' )
	output -= 200;
	break;
	case 'M':
	output += 1000;
	if( s[i-1] == 'C' )
	output -= 200;
	break;
	}
	}
	return output;
	}

	string number_to_roman( int i )
	{
	string output = "";

	if( i == 0 )
	return (output = "ZERO");

	int temp;

	while( i > 0 )
	{
	if( i >= 1000 )
	{
	i -= 1000;
	output += "M";
	}
	else if( i >= 900 )
	{
	i -= 900;
	output += "CM";
	}
	else if( i >= 500 )
	{
	i -= 500;
	output += "D";
	}
	else if( i >= 400 )
	{
	i -= 400;
	output += "CD";
	}
	else if( i >= 100 )
	{
	i -= 100;
	output += "C";
	}
	else if( i >= 90 )
	{
	i -= 90;
	output += "XC";
	}
	else if( i >= 50 )
	{
	i -= 50;
	output += "L";
	}
	else if( i >= 40 )
	{
	i -= 40;
	output += "XL";
	}
	else if( i >= 10 )
	{
	i -= 10;
	output += "X";
	}
	else if( i >= 9 )
	{
	i -= 9;
	output += "IX";
	}
	else if( i >= 5 )
	{
	i -= 5;
	output += "V";
	}
	else if( i >= 4 )
	{
	i -= 4;
	output += "IV";
	}
	else
	{
	i -= 1;
	output += "I";
	}
	}
	return output;
	}


	int main()
	{
	string num1, num2;
	while( cin >> num1 )
	{
	if( num1 == "#" )
	break;
	cin >> num2;
	cout << number_to_roman( abs( roman_to_number( num1 ) - roman_to_number( num2 ) ) ) << endl;
	}
	return 0;
	}

view raw Zerojudgea013.cpp hosted with ❤ by GitHub

[Zerojudge]a012: Hashmat的戰役

這題只要將兩個數絕對值相減即可，
唯一的陷阱就是在於數值範圍，
剛好到2^32，就連unsigned int也會爆，
所以請用long long吧！

P.S. C語言的abs不太支援long long Orz...

[C](2ms, 272KB)

	#include<stdio.h>
	#include<stdlib.h>

	int main()
	{
	long long x, y;
	while( scanf( "%lld%lld", &x, &y ) != EOF )
	printf( "%lld\n", ( x-y > 0 )? x-y : y-x );
	return 0;
	}

view raw ACM10055.c hosted with ❤ by GitHub

[C++](4ms, 696KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	long long x, y;
	while( cin >> x >> y )
	cout << abs( x-y ) << endl;
	return 0;
	}

view raw Zerojudgeaa012.cpp hosted with ❤ by GitHub

[Zerojudge]a011: 幼稚園的算數遊戲

利用非字母與字母相間的關係，
找出總共有幾個Word。

[C++](2ms, 754KB)

	#include<iostream>
	#include<cctype>
	using namespace std;

	int main()
	{
	string s;
	while( getline( cin, s ) )
	{
	int num = 0;
	bool word = 0;
	for( int i = 0 ; i < s.length(); i++ )
	{
	if( isalpha( s[i] ) )
	{
	if( !word )
	{
	word = 1;
	num++;
	}
	}
	else
	word = 0;
	}
	cout << num << endl;
	}
	return 0;
	}

view raw Zerojudgeaa011.cpp hosted with ❤ by GitHub

[Zerojudge]a010: 因數分解

直接從2開始搜尋到輸入的值的根號，
看看能不能整除，
能整除就一直除到不能，
做完後再看看輸入的值是否已經被除到只剩下1，
如果不是，一定只是一個大於輸入的值的根號的質數，將之輸出即可。

[C++](6ms, 700KB)

	#include<iostream>
	#include<cmath>
	using namespace std;

	int main()
	{
	int x;
	while( cin >> x )
	{
	bool print = 0;
	int num;
	int limit = static_cast<int>(sqrt(x));
	for( int i = 2; i <= limit; i++ )
	{
	num = 0;
	while( x % i == 0 )
	{
	num++;
	x /= i;
	}
	if( num )
	if( print )
	{
	cout << " * " << i;
	if( num != 1 )
	cout << '^' << num;
	}
	else
	{
	print = 1;
	cout << i;
	if( num != 1 )
	cout << '^' << num;
	}
	}
	if( x != 1 )
	if( print )
	cout << " * " << x;
	else
	cout << x;
	cout << endl;
	}
	return 0;
	}

view raw Zerojudgeaa010.cpp hosted with ❤ by GitHub

[Zerojudge]a009: 解碼器

利用ASCII碼找出Sample Input和Sample Output相差的k值，
將輸入的每個字都以此k值做加減即可得解。

P.S. k值為7

[C++](6ms, 730KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	const int k = 7;
	string s;
	while( getline( cin, s ) )
	{
	for( int i = 0 ; i < s.length() ; i++ )
	s[i] -= 7;
	cout << s << endl;
	}

	return 0;
	}

view raw Zerojudgea009.cpp hosted with ❤ by GitHub

[Zerojudge]a007: 判斷質數

純粹尋找質數，
所以用個for從頭跑到尾就可以了。

為了省時，可以僅跑到輸入值的根號處即可。

[C++](20ms, 670KB)

	#include<iostream>
	#include<cmath>
	using namespace std;

	int main()
	{
	int x;
	while( cin >> x )
	{
	if( x == 2 )
	printf( "質數\n" );
	else if( x % 2 == 0 )
	printf( "非質數\n" );
	else
	{
	int primeis = 1;
	for( int i = 3 ; i <= sqrt(x); i++ )
	{
	if( x % i == 0 )
	{
	printf( "非質數\n");
	primeis = 0;
	}
	}
	if( primeis )
	printf( "質數\n" );
	}
	}

	return 0;
	}

view raw Zerojudgea007.cpp hosted with ❤ by GitHub

[Zerojudge]a008: 中文大寫數字

初次想會覺得比較難，
因為條件會感覺很多。

實際上就是先把輸入的數字每一位數存放於陣列每一格中，
再用一個for從高位數開始跑到低位數，
然後去判斷跑到的數字：
1.如果是1~9，就輸出它的值跟它的單位。
2.如果是0，而且是在萬位和億位，只要輸出它的單位即可。
3.如果是0，而且不在萬位和億位，但是比它低一位數的地方有數字，就輸出"零"。
4.非以上狀況，不輸出。

[C++](2ms, 730KB)

	#include<iostream>
	using namespace std;

	int main( void )
	{
	string number[15] = { "零", "壹", "貳", "參", "肆", "伍", "陸", "柒", "捌", "玖" };
	string value[15] = { "拾", "億", "仟", "佰", "拾", "萬", "仟", "佰", "拾", "" };

	int num;
	while( cin >> num )
	{
	int num_divide[15] = {0};
	int digit = 9;
	while( num )
	{
	num_divide[digit--] = num % 10;
	num /= 10;
	}
	for( int i = digit+1 ; i < 10 ; i++ )
	{
	if( num_divide[i] != 0 )
	cout << number[num_divide[i]] << value[i];
	else if( i == 1 \|\| i == 5 )
	cout << value[i];
	else if( num_divide[i+1] != 0 )
	cout << number[num_divide[i]];
	}
	cout << endl;
	}
	}

view raw Zerojudgea008.cpp hosted with ❤ by GitHub

[Zerojudge]d067: 文文的求婚--續集 (1 行版)

直接判斷是否為閏年即可，
每筆測資僅一行，不需用到無限輸入。

P.S. 閏年是能被4整除但不能被100整除的年份，以及能被400整除的年份。

[C++](4ms, 674KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int year;
	cin >> year;
	if( ( year % 4 == 0 && year % 100 != 0 ) \|\| year % 400 == 0 )
	cout << "a leap year\n";
	else
	cout << "a normal year\n";
	return 0;
	}

view raw Zerojudged067.cpp hosted with ❤ by GitHub

[Zerojudge]a006: 一元二次方程式

公式解，即可得。

P.S. 公式：(-b+sqrt(b*b-4*a*c))/(2*a) 以及 (-b-sqrt(b*b-4*a*c))/(2*a)

[C++](5ms, 704KB)

	#include<iostream>
	#include<cmath>
	using namespace std;

	int main()
	{
	int a, b, c;
	while( cin >> a >> b >> c )
	{
	if( bb - 4a*c < 0 )
	cout << "No real root\n";
	else if( bb - 4a*c == 0 )
	cout << "Two same roots x=" << -b/(2*a) << endl;
	else
	cout << "Two different roots x1=" << (-b + sqrt(bb-4ac)) / (2a) << " , x2=" << (-b - sqrt(bb-4ac)) / (2a) << endl;
	}
	return 0;
	}

view raw Zerojudgea006.cpp hosted with ❤ by GitHub

[Zerojudge]a005: Eva 的回家作業

找出所給陣列的規律究竟是等比還是等差，
之後即可找出第五個值。

[C++](2ms, 706KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int t;
	while( cin >> t )
	{
	for( int i = 0 ; i < t ; i++ )
	{
	int array[5] = {0};
	for( int j = 0 ; j <= 3 ; j++ )
	{
	cin >> array[j];
	cout << array[j] << ' ';
	}
	if( array[1] - array[0] == array[2] - array[1] )
	cout << array[3] + array[1] - array[0];
	else
	cout << array[3] * array[1] / array[0];
	cout << endl;
	}
	}
	return 0;
	}

view raw Zerojudgea005.cpp hosted with ❤ by GitHub

[Zerojudge]a004: 文文的求婚

直接判斷是不是閏年即可，
屬基礎題。

P.S. 閏年為可被4但不被100整除的年份，以及會被400整除的年份。

[C++](18ms, 672KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int year;
	while( cin >> year )
	{
	if( ( year % 4 == 0 && year % 100 != 0 ) \|\| year % 400 == 0 )
	cout << "閏年\n";
	else
	cout << "平年\n";
	}
	return 0;
	}

view raw Zerojudgea004.cpp hosted with ❤ by GitHub

[Zerojudge]a003: 兩光法師占卜術

屬基礎題，
照題目意思直接做即可。

[C++](4ms, 674KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int M, D, S;
	while( cin >> M >> D )
	{
	S = ( M * 2 + D ) % 3 ;
	switch( S )
	{
	case 0:
	cout << "普通\n";
	break;
	case 1:
	cout << "吉\n";
	break;
	case 2:
	cout << "大吉\n";
	break;
	}
	}
	return 0;
	}

view raw Zerojudgea003.cpp hosted with ❤ by GitHub

[Zerojudge]a002: 簡易加法

照著題目說的做即可，
這題屬基礎題。

[C++](6ms, 698KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	int i, j;
	while( cin >> i >> j )
	cout << i+j << endl;
	return 0;
	}

view raw Zerojudgea002.cpp hosted with ❤ by GitHub

[Zerojudge]a001: 哈囉

基本的範例題，
只要照著題目說的把要求的輸入，
輸出成限定的格式即可。

[C](0ms, 266KB)

	#include<stdio.h>

	int main( void )
	{
	char s[10000];
	while( scanf( "%s" , s ) != EOF )
	printf( "hello, %s\n", s );
	return 0;
	}

view raw Zerojudgea001.c hosted with ❤ by GitHub

[C++](4ms, 734KB)

	#include<iostream>
	using namespace std;

	int main()
	{
	string s;
	while( cin >> s )
	cout << "hello, " << s << endl;
	return 0;
	}

view raw Zerojudgea001.cpp hosted with ❤ by GitHub

2011年1月11日星期二

[生活趣事]好久沒更新了=口=！

超久沒更新了！

我還真的不知道該多打啥了XD"

待我期末考完，再來把這學期總結吧～

P.S. 我換大頭貼了呀XD！

訂閱：文章 (Atom)

連結

本站遷移

因為我最近租用了網路空間以及網域， 故本站已遷移至新網站~ 這邊的資訊已經正在進行搬移的工作~ 希望各位可以到新網站去逛XD New Website: http://knightzone.org/

搜尋此網誌

2011年1月27日 星期四

2011年1月22日 星期六

2011年1月21日 星期五

2011年1月20日 星期四

2011年1月19日 星期三

2011年1月18日 星期二

2011年1月11日 星期二

因為我最近租用了網路空間以及網域，
故本站已遷移至新網站~
這邊的資訊已經正在進行搬移的工作~
希望各位可以到新網站去逛XD

New Website:
http://knightzone.org/