本站遷移

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

New Website:
http://knightzone.org/

搜尋此網誌

2011年2月28日 星期一

[UVa]424:Integer Inquiry

大數加法即可得解。

[C](0.012)
#include<stdio.h>
#include<string.h>
int main()
{
int answer[105] = {0};
char input[105] = {0};
while( scanf( "%s", input ) != EOF && !( input[0] == '0' && input[1] == '\0' ) )
{
int length = strlen( input );
int inputrev[105] = {0};
int i;
for( i = 0 ; i < length ; i++ )
inputrev[i] = input[length-i-1] - '0';
for( i = 0 ; i < 105 ; i++ )
{
answer[i] += inputrev[i];
answer[i+1] += answer[i]/10;
answer[i] %= 10;
}
}
int i;
for( i = 104 ; i >= 0 ; i-- )
if( answer[i] )
break;
if( i == -1 )
printf( "0" );
else
for( ; i >= 0 ; i-- )
printf( "%d", answer[i] );
printf( "\n" );
return 0;
}
view raw UVa424.c hosted with ❤ by GitHub

[UVa]412:Pi

直接硬爆,把所有組合都找出來看看有沒有互質,再求機率即可。

[C](0.108)
#include<stdio.h>
#include<math.h>
int gcd( int a, int b )
{
while( (a%=b) && (b%=a) );
return a+b;
}
int main()
{
int N;
while( scanf( "%d", &N ) != EOF && N != 0 )
{
int array[100];
int i;
for( i = 0 ; i < N ; i++ )
scanf( "%d", &array[i] );
int all = ( N * N - N ) / 2;
int sum = 0;
int j;
for( i = 0 ; i < N ; i++ )
for( j = i+1 ; j < N ; j++ )
if( gcd( array[i], array[j] ) == 1 )
sum++;
if( sum == 0 )
printf( "No estimate for this data set.\n" );
else
{
printf( "%.6lf\n", sqrt( ((double)all * 6.0) / (double)sum ) );
}
}
return 0;
}
view raw UVa412.c hosted with ❤ by GitHub

[幻想迷宮]第二關完工


首先當然是先來張第二關的開頭的圖啦!
第二關最特別的在於可以切換原本世界與鏡子世界,
透過切換來改變水深淺,藉而抵達終點。

再來隨著第二關完工,
將原本的支線改成搜尋盡頭,
這樣走到盡頭都不會覺得難過了XD


最後當然是要來張Clear的圖啦!
(但是卻沒拿到全部盡頭(死...))


還請各位期待下次的進度喔!>_O/

2011年2月27日 星期日

[幻想迷宮]遊戲企劃展開&教學關以及第一關完工


這是今天決定要做的新企劃,
基本上來說是一個簡單的迷宮遊戲,
唯一特別的是,
過河要利用木板!



目前教學關卡跟第一關卡都做完了~
預計大概只會做六關吧~XD



請期待下次的進度吧!

[UVa]458:The Decoder

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

[UVa]272:TEX Quotes

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

2011年2月26日 星期六

[Zerojudge]a042: 平面圓形切割

基本上來說,
我不知道該怎麼用幾何解釋會比較好。
因此很多人遇到這題我想就只能用猜測的方法,
假設圓的數量(x)與區域的數量(y)的關係是個二次函數:y = ax^2 + bx + c
那麼
x = 1 => y = a+b+c = 2 --(1)
x = 2 => y = 4a+2b+c = 4 --(2)
x = 3 => y = 9a+3b+c = 8 --(3)
x = 4 => y = 16a+4b+c = 14 --(4)
其實只需要3個就可以了,我就用(1)(2)(3)好了。
首先
(2) - (1) : 3a+b = 2 --(5)
(3) - (2) : 5a+b = 4 --(6)
再來
(6) - (5) : 2a = 2 => a = 1
a=1代入(5)
則b = 2-3 = -1
再將a=1和b=-1代入(1)
則c = 2

因此可以得出 y = x^2 - x + 2 的式子,即得解。

[C++](30ms, 704KB)
#include<iostream>
using namespace std;
int main()
{
int n;
while( cin >> n )
cout << n*(n-1)+2 << endl;
return 0;
}

[生活趣事]992大學生活開始!

大學在這禮拜開學了~

在這個寒假,
因為寒訓的關係,
又開始解題了XD"

結果整個網誌現在充滿了題目...
哈哈...
我也不知道該怎麼說了。

但是我還是想發幾篇心得呀!!

這禮拜開學,
程式設計教授換人,
不過接受度似乎不高,
等之後大家習慣這位教授才會漸漸喜歡他吧!

英文課的教授這學期第一次上課讓我覺得他比以前高興許多,
不知道是否是我的錯覺XD"

離散數學的教授正是TOI時的樹教授,
熟悉的聲音及熟悉的面孔啊XD
不過說到熟悉的聲音及熟悉的面孔,
這次系上我修的課唯一跟上學期一樣的教授,
就只有這學期的吳老大的數位邏輯,
期待這學期上他的課可以學到更多的東西!

至於邏輯概論,
教授講課講得非常棒!
有點像是在上空中英語教室一般!XD
那個口調、那個聲音(、那個內容XDDDDD)都像極了!!

國文課的話,
似乎跟上學期的上課方式一樣,
只是教授最近好愛講:「我再講下去,你們將不用看了。」XD
快變成口頭禪了呀!
還有一句就是:「我不是投資者。」XD

接著就要提到通識,
我修的是楊恩生教授的「自然探索」,
第一節課就讓我對這位教授感到喜歡!
他講的東西真的都很有一番道理在。
他在水彩界非常有名,
我後來也有查過,
真是太厲害的畫家了!!

本來要在多修「多元視野的道德判斷」,
只可惜沒加簽到Orz...
那教授看來很不錯的說QQ
明年教授休假,不會有這堂課,
怨念......

至於體育,
我這學期就不上了,
我不喜歡那位教授的上課方式,
我就不公布是哪堂課哪位教授了。

大概這樣,
這是我開學第一週對每堂課的感想XD
說到這裡就好,
各位晚安^^/

[Zerojudge]a040: 阿姆斯壯數

先找尋位數,接著再分解各個位數,
然後給它乘個位數次方,
接著加起來看看有沒有跟原來的數一樣,
就可以得解。

[C++](80ms, 714KB)
#include<iostream>
#include<cmath>
#define ERROR 0.0000001
using namespace std;
int main()
{
int n, m;
while( cin >> n >> m )
{
bool print = 0;
for( int i = n ; i <= m ; i++ )
{
int temp = i;
int sum = 0;
int digit = 0;
while( temp )
{
digit++;
temp /= 10;
}
temp = i;
while( temp )
{
sum += (int)( pow( (double)(temp%10) , (double)digit ) + ERROR );
temp /= 10;
}
if( sum == i )
{
if( print )
cout << ' ';
print = 1;
cout << i;
}
}
if( !print )
cout << "none";
cout << endl;
}
return 0;
}

[Zerojudge]a038: 數字翻轉

利用某個變數乘10加原數餘10,再把原數除10,
這樣反覆做就可以得到數字翻轉的結果。

[C++](4ms, 700KB)
#include<iostream>
using namespace std;
int main()
{
int n;
while( cin >> n )
{
int n_rev = 0;
while( n )
{
n_rev *= 10;
n_rev += n % 10;
n /= 10;
}
cout << n_rev << endl;
}
return 0;
}

[Zerojudge]a034: 二進位制轉換

利用while一直除2餘2,
再把每次得到的餘數存進陣列中,
再輸出即是答案。

[C++](2ms, 700KB)
#include<iostream>
using namespace std;
int main()
{
int n;
while( cin >> n )
{
int output[1000];
int outputrange = 0;
while( n )
{
output[outputrange++] = n % 2;
n /= 2;
}
if( outputrange )
{
for( int i = outputrange-1 ; i >= 0 ; i-- )
cout << output[i];
cout << endl;
}
else
cout << 0 << endl;
}
return 0;
}

[Zerojudge]a032: 階乘運算

利用迴圈即可得解。

[C++](4ms, 696KB)
#include<iostream>
using namespace std;
int main()
{
long long n;
while( cin >> n )
{
long long nf = 1;
for( long long i = 2 ; i <= n ; i++ )
nf *= i;
cout << nf << endl;
}
return 0;
}

[Zerojudge]a024: 最大公因數(GCD)

利用輾轉相除法即可過關。

[C++](6ms, 698KB)
#include<iostream>
using namespace std;
int main()
{
int a, b;
while( cin >> a >> b )
{
while( (a%=b) && (b%=a) );
cout << a+b << endl;
}
return 0;
}

[Zerojudge]a022: 迴文

利用字串處理,並且利用for來反轉字串,很快速即可過關。

[C++](0ms, 730KB)
#include<iostream>
using namespace std;
int main()
{
string str;
while( getline( cin, str ) )
{
string rev;
for( int i = str.length()-1 ; i >= 0 ; i-- )
rev += str[i];
if( rev == str )
cout << "yes\n";
else
cout << "no\n";
}
return 0;
}

2011年2月9日 星期三

[UVa]583:Prime Factors

建質數表去質因數分解即可。

[C](1.708)
#include<stdio.h>
#include<math.h>
#define ERROR 0.00000001
int main()
{
int prime[100005] = { 1, 1, 0 };
int i, j;
for( i = 2 ; i <= 100000 ; i++ )
if( !prime[i] )
for( j = i+i ; j <= 100000 ; j+=i )
prime[j] = 1;
int g;
while( scanf( "%d", &g ) != EOF && g != 0 )
{
printf( "%d =", g );
if( g < 0 )
{
printf( " -1 x" );
g = -g;
}
int print = 0;
int sqrt_g = (int)( sqrt((double)g) + ERROR );
for( i = 2 ; i <= sqrt_g ; i++ )
if( !prime[i] )
while( !(g % i) )
{
g /= i;
if( print )
printf( " x" );
print = 1;
printf( " %d", i );
}
if( g > 1 )
{
if( print )
printf( " x" );
printf( " %d", g );
}
printf( "\n" );
}
return 0;
}
view raw UVa583.c hosted with ❤ by GitHub

[UVa]10392:Factoring Large Numbers

建質數表去質因數分解,注意質數表最高要建到的範圍(題目有寫)。

[C](0.044)
#include<stdio.h>
#include<math.h>
#define ERROR 0.00000001
int prime[1000005] = { 1, 1, 0 };
int main()
{
long long i, j;
for( i = 2 ; i <= 1000000 ; i++ )
if( !prime[i] )
for( j = i+i ; j <= 1000000 ; j+=i )
prime[j] = 1;
long long value;
while( scanf( "%lld", &value ) != EOF && value >= 0 )
{
long long value_temp = (long long)(sqrt( (double)value ) + ERROR);
if( value_temp > 1000000 )
value_temp = 1000000;
for( i = 2 ; i <= value_temp ; i++ )
{
if( !prime[i] )
while( !(value % i) )
{
value /= i;
printf( " %lld\n", i );
}
}
if( value > 1 )
printf( " %lld\n", value );
printf( "\n" );
}
return 0;
}
view raw UVa10392.c hosted with ❤ by GitHub

[UVa]10042:Smith Numbers

建質數表硬爆,
把每個數字質因數分解然後再看看加起來有沒有相等這樣。
還有要去掉本身是質數的數字,
因為本身為質數的數字並不能是答案(題目有說)。

[C](0.096)
#include<stdio.h>
#include<math.h>
#define ERROR 0.00000001
int main()
{
int prime[100005] = { 1, 1, 0 };
int i, j;
for( i = 2 ; i <= 100000 ; i++ )
if( !prime[i] )
for( j = i+i ; j <= 100000 ; j+=i )
prime[j] = 1;
int testcase;
while( scanf( "%d", &testcase ) != EOF )
{
for( i = 1 ; i <= testcase ; i++ )
{
int n;
scanf( "%d", &n );
for( j = n+1 ; ; j++ )
{
int sum_left = 0, sum_right = 0;
int temp = j;
int sqrt_temp = (int)( sqrt((double)temp) + ERROR );
int k;
while( temp )
{
sum_left += temp % 10;
temp /= 10;
}
temp = j;
for( k = 2 ; k <= sqrt_temp ; k++ )
{
if( !prime[k] )
{
while( !( temp % k ) )
{
temp /= k;
int k_temp = k;
while( k_temp )
{
sum_right += k_temp % 10;
k_temp /= 10;
}
}
}
}
if( temp > 1 )
{
if( temp == j )
continue;
while( temp )
{
sum_right += temp % 10;
temp /= 10;
}
}
if( sum_left == sum_right )
{
printf( "%d\n", j );
break;
}
}
}
}
return 0;
}
view raw UVa10042.c hosted with ❤ by GitHub

[UVa]543:Goldbach's Conjecture

建質數表,從1開始找質數,看看能不能找到兩個質數加起來等於輸入值,
那麼第一組找到的即是b-a相差最大的一組,即是所求。

[C](0.060)
#include<stdio.h>
int prime[1000005] = { 1, 0, 0 };
int main()
{
int i, j;
for( i = 2 ; i <= 1000000 ; i++ )
if( !prime[i] )
for( j = i+i ; j <= 1000000 ; j+=i )
prime[j] = 1;
int n;
while( scanf( "%d", &n ) != EOF && n != 0 )
{
int print = 0;
for( i = 2 ; i <= n ; i++ )
if( !prime[i] && !prime[n-i] )
{
printf( "%d = %d + %d\n", n, i, n-i );
print = 1;
break;
}
if( !print )
printf( "Goldbach's conjecture is wrong.\n" );
}
return 0;
}
view raw UVa543.c hosted with ❤ by GitHub

[UVa]10235:Simply Emirp

這題就照題意,
建質數表,
檢查輸入值是否為質數,
再檢查倒轉過來是否跟原本的值是否不相同且還是質數。

P.S. 這題我因為題意沒看清楚爆了Orz
我沒仔細看到翻轉過來要另外一個質數,而不能跟原來一樣Orz...
可愛的different......

[C](0.036)
#include<stdio.h>
int prime[1000005] = { 1, 1, 0 };
int main()
{
int i, j;
for( i = 2 ; i <= 1000000 ; i++ )
if( !prime[i] )
for( j = i+i ; j <= 1000000 ; j+=i )
prime[j] = 1;
int N;
while( scanf( "%d", &N ) != EOF )
{
int N_origin = N;
int N_reverse = 0;
while( N )
{
N_reverse *= 10;
N_reverse += N % 10;
N /= 10;
}
if( prime[N_origin] )
printf( "%d is not prime.\n", N_origin );
else if( prime[N_reverse] || N_origin == N_reverse )
printf( "%d is prime.\n", N_origin );
else
printf( "%d is emirp.\n", N_origin );
}
return 0;
}
view raw UVa10235.c hosted with ❤ by GitHub

2011年2月8日 星期二

[UVa]10924:Prime Words

這題就是建質數表,然後根據所給公式計算單字的值是否為質數即可。

P.S. 1在這題屬於質數。

[C](0.012)
#include<stdio.h>
#include<ctype.h>
#include<string.h>
int letter_to_i( char c )
{
if( isupper(c) )
return c - 'A' + 27;
else if( islower(c) )
return c - 'a' + 1;
else
return 0;
}
int main()
{
int prime[10005] = { 1, 0, 0 };
int i, j;
for( i = 2 ; i <= 10000 ; i++ )
if( !prime[i] )
for( j = i+i ; j <= 10000 ; j+=i )
prime[j] = 1;
char word[25];
while( gets(word) )
{
int L = strlen(word);
int sum = 0;
for( i = 0 ; i < L ; i++ )
sum += letter_to_i( word[i] );
if( prime[sum] )
printf( "It is not a prime word.\n" );
else
printf( "It is a prime word.\n" );
}
return 0;
}
view raw UVa10924.c hosted with ❤ by GitHub

2011年2月7日 星期一

[UVa]406:Prime Cuts

建立質數表,找出要輸出的上界和下界,
再藉著上界和下界把質數都輸出來。

P.S. 這題1也算是要輸出的東西之一。

[C](0.064)
#include<stdio.h>
int main()
{
int prime[1005] = { 1, 0};
int prime_count[1005] = {0, 1};
int count = 1;
int i, j;
for( i = 2 ; i <= 1000 ; i++ )
{
if( !prime[i] )
{
count++;
for( j = i+i ; j <= 1000 ; j += i )
prime[j] = 1;
}
prime_count[i] = count;
}
int N, C;
while( scanf( "%d%d", &N, &C ) != EOF )
{
int start, end;
if( !( prime_count[N] % 2 ) )
{
start = prime_count[N]/2 - C + 1;
if( start < 1 )
start = 1;
end = prime_count[N]/2 + C;
if( end > prime_count[N] )
end = prime_count[N];
}
else
{
start = (prime_count[N]/2 + 1) - C + 1;
if( start < 1 )
start = 1;
end = (prime_count[N]/2 + 1) + C - 1;
if( end > prime_count[N] )
end = prime_count[N];
}
printf( "%d %d:", N, C );
count = 0;
for( i = 1 ; i <= N ; i++ )
{
if( !prime[i] )
{
count++;
if( count <= end && count >= start )
printf( " %d", i );
}
}
printf( "\n\n" );
}
return 0;
}
view raw UVa406.c hosted with ❤ by GitHub

2011年2月6日 星期日

[UVa]160:Factors and Factorials

這題不用先乘出答案,把階乘的每一項一個一個因式分解再加起來即可得解。

P.S. 我沒用到質數XD"" 我直接除到根號這樣XDDDDDDD

[C](0.012)
#include<stdio.h>
#include<math.h>
#define ERROR 0.000000001
int main()
{
int N;
while( scanf( "%d", &N ) != EOF && N != 0 )
{
int i;
int prime_count[105] = {0};
for( i = N ; i >= 2 ; i-- )
{
int temp = i;
int j;
int sqrt_i = (int)( sqrt( (double)temp ) + ERROR );
for( j = 2 ; j <= sqrt_i ; j++ )
while( !(temp % j) )
{
prime_count[j]++;
temp /= j;
}
if( temp > 1 )
prime_count[temp]++;
}
printf( "%3d! =", N );
int count = 0;
for( i = 2 ; i <= N ; i++ )
{
if( prime_count[i] )
{
if( !(count % 15) && count != 0 )
printf( "\n " );
count++;
printf( "%3d", prime_count[i] );
}
}
printf( "\n" );
}
return 0;
}
view raw Uva160.c hosted with ❤ by GitHub

[UVa]516:Prime Land

這題我沒用質數去解,直接走硬爆到根號的風格XD

P.S. pow函式的小數變成整數會有微小的誤差,要記得加個非常小的值修正過來。

[C](0.048)
#include<stdio.h>
#include<math.h>
#define ERROR 0.00000001
int main()
{
int p, e;
while( ( scanf( "%d", &p ) != EOF )&& p != 0 )
{
scanf( "%d", &e );
int product = 1;
product *= (int)(pow( (double)p, (double)e ) + ERROR);
while( getchar() == ' ' )
{
scanf( "%d", &p );
scanf( "%d", &e );
product *= (int)(pow( (double)p, (double)e ) + ERROR);
}
product -= 1;
int output[50000] = {0};
int i;
int sqrt_num = (int)sqrt((double)product);
int max_prime = 0;
for( i = 2 ; i <= sqrt_num ; i++ )
{
while( !(product % i) )
{
product /= i;
output[i]++;
max_prime = ( max_prime < i )? i : max_prime;
}
}
int print = 0;
if( product > 1 )
{
print = 1;
printf( "%d %d", product, 1 );
}
for( ; max_prime >= 2 ; max_prime-- )
{
if( output[max_prime] )
{
if( print )
printf( " " );
print = 1;
printf( "%d %d", max_prime, output[max_prime] );
}
}
printf( "\n" );
}
return 0;
}
view raw UVa516.c hosted with ❤ by GitHub

2011年2月3日 星期四

[UVa]155:All Squares

利用遞迴找出每一個正方形,然後確定點是否有在此正方形內。
有的話,就加一;
沒有的話,就不用加任何數字。
這樣即可得解。

[C](0.028)
#include<stdio.h>
#define SIDE_X_AND_Y 2048
int squares( int k, int cenx, int ceny, int surx, int sury )
{
if( k <= 0 )
return 0;
int left = cenx - k;
int right = cenx + k;
int top = ceny - k;
int bottom = ceny + k;
if( left < 0 || right < 0 || top < 0 || bottom < 0 )
return 0;
int result = 0;
if( surx >= left && surx <= right && sury <= bottom && sury >= top )
result++;
result += squares( k/2, left, top, surx, sury );
result += squares( k/2, right, top, surx, sury );
result += squares( k/2, left, bottom, surx, sury );
result += squares( k/2, right, bottom, surx, sury );
return result;
}
int main()
{
int k, surx, sury;
while( scanf( "%d%d%d", &k, &surx, &sury ) != EOF )
{
if( k == 0 && surx == 0 && sury == 0 )
break;
int cenx = 1024, ceny = 1024;
printf( "%3d\n", squares( k, cenx, ceny, surx, sury ) );
}
return 0;
}
view raw UVa155.c hosted with ❤ by GitHub

[Zerojudge]a020: 身分證檢驗

照著題目做即可。

[C++](4ms, 748KB)
#include<iostream>
using namespace std;
int changenum( char letter )
{
if( letter >= 'A'&& letter <= 'H' )
return (int)letter - (int)'A' + 10;
if( letter == 'I' )
return 34;
if( letter >= 'J' && letter <= 'N' )
return (int)letter - (int)'J' + 18;
if( letter == 'O' )
return 35;
if( letter >= 'P' && letter <= 'V' )
return (int)letter - (int)'P' + 23;
if( letter == 'W' )
return 32;
if( letter >= 'X' && letter <= 'Y' )
return (int)letter - (int)'X' + 30;
if( letter == 'Z' )
return 33;
}
int main()
{
char letter;
unsigned int number;
while( cin >> letter >> number )
{
int sum = 0;
int temp = changenum(letter);
sum += temp/10;
sum += temp%10 * 9;
sum += number % 10;
number /= 10;
int inc = 1;
while( number )
{
sum += number%10 * inc;
inc++;
number /= 10;
}
if( sum % 10 )
cout << "fake\n";
else
cout << "real\n";
}
return 0;
}