筆記國度

# 吳永輝老師培訓

# 第一章 程式設計技巧

  1. 簡單計算題
    • 輸入處理輸出
  2. 解題技巧
    • 離線計算方法
    • 實數精度處理
    • 二分法

# 浮點數精確度處理

int dzero( double da )
{
    const double delta = 1e-8;
    return ( da < -delta ) ? -1 : ( da > delta );
}

# 建表求質數

int p[100000] = {2,3,5,7}, p_cnt =4;

bool is_prime( int ia )
{
    for(int i=0;i<p_cnt && p[i]*p[i]<=ia;i++)
        if( ia % p[i] == 0 )
            return false;
    return true;
}

void build_prime()
{
    for( int i=11, j=2; i<1000000; i+=j, j=6-j )
        if( is_prime(i) )
            p[ p_cnt++ ] = i;
}

# 網站

# 實戰練習

  1. [POJ 1004] (opens new window) Financial Management
  2. [POJ 1552] (opens new window) Doubles
  3. [POJ 2739] (opens new window) Sum of Consecutive Prime Numbers
  4. [POJ 1005] (opens new window) I Think I Need a Houseboat
  5. [POJ 1003] (opens new window) Hangover
  6. [POJ 2262] (opens new window) Goldbach's Conjecture
  7. [POJ 3299] (opens new window) Humidex
  8. [POJ 3518] (opens new window) Prime Gap

# POJ 1004 Financial Management

http://poj.org/problem?id=1004 (opens new window)

這一題看似簡單，但是卻讓我 WA 了很多次，最後猜測很有可能是因為 Judge 的資料是用 %.2f 產生的，像我習慣使用 double，所以都會用 %.2lf 就吃了一大堆 WA (float 溢位)，改用純 C 的 Code 才終於 AC 了。

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

int main()
{
    float dsum = 0, da;
    for(int i=0;i<12;i++)
    {
        cin>>da;
        dsum += da;
    }
    cout<<"$"<<dsum/12<<endl;
}

# POJ 1552 Doubles

http://poj.org/problem?id=1552 (opens new window)

這一題比較奇怪的就是它的測資終止條件，很多人卡在這個奇怪的條件，這題的數字極少，所以倒是不需要考慮排序法，實作排序法反而會引此增加題目的 AC 時間，得不償失。

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

int arr1[15];

int main()
{
    int ia,cnt1=0,ans=0;
    while(cin>>ia,ia+1)
    {
        if(ia==0)
        {
            cout<<ans<<endl;
            cnt1=ans=0;
            continue;
        }
        arr1[cnt1++] = ia;
        for(int i=0;i<cnt1-1;i++)
        {
            if( ia%2==0 && arr1[i] == ia/2 )
                ans++;
            if( arr1[i] == ia*2 )
                ans++;
        }
    }
}

# POJ 2739 Sum of Consecutive Prime Numbers

http://poj.org/problem?id=2739 (opens new window)

這一題由於題目範圍不高，所以就考慮直接預先建表，然後在查表輸出。比較難的部分，可能就是要怎麼樣列舉出所有的區間的和。我是採用很像選擇排序法的迴圈，只不過改成計算加總就是了。

#include<iostream>
using namespace std;

int arr1[10001] = {};
int p[10000] = {2,3,5,7}, p_cnt =4;

bool is_prime( int ia )
{
    for(int i=0;i<p_cnt && p[i]*p[i]<=ia;i++)
        if( ia % p[i] == 0 )
            return false;
    return true;
}

void build_prime()
{
    for( int i=11, j=2; i<10000; i+=j, j=6-j )
        if( is_prime(i) )
            p[ p_cnt++ ] = i;
}

int main()
{
    build_prime();
    for(int i=0;i<p_cnt;i++)
    {
        int sum = p[i];
        arr1[ sum ]++;
        for(int j=i+1;j<p_cnt;j++)
        {
            sum += p[j];
            if(sum>10000)break;
            arr1[ sum ]++;
        }
    }
    int ia;
    while(cin>>ia,ia)
        cout<<arr1[ia]<<endl;
}

# POJ 1005 I Think I Need a Houseboat

http://poj.org/problem?id=1005 (opens new window)

這題是 $\pi$ 的基礎應用，只要有背 $\pi$ 的寫法，基本上就可以輕鬆拿分。 2.0 * acos(0.0)

#include<iostream>
#include<cmath>
#define PI 2.0 * acos(0.0)
using namespace std;

int main()
{
    int ta;
    cin>>ta;
    double da,db;
    for(int t1=0;t1<ta;t1++)
    {
        cin>>da>>db;
        cout<<"Property "<<t1+1<<": This property will begin eroding in year "<<ceil( PI * (da*da + db*db) / 100.0 )<<"."<<endl;
    }
    cout<<"END OF OUTPUT."<<endl;
}

# POJ 1003 Hangover

http://poj.org/problem?id=1003 (opens new window)

這一題我有做浮點數的精確度判斷，但是別人的程式碼好像沒有也會過，我就搞不太清楚了。

#include<iostream>
using namespace std;

double arr1[1000000] = {.5};

int dzero( double da )
{
    const double delta = 1e-8;
    return ( da < -delta ) ? -1 : ( da > delta );
}

int main()
{
    int cnt1=1;
    while( dzero( arr1[cnt1-1] - 5.20 ) <= 0 )
    {
        arr1[cnt1] = arr1[cnt1-1] + 1.0/(cnt1+2);
        cnt1++;
    }
    double da;
    while(cin>>da,dzero(da))
    {
        for(int i=0;i<cnt1;i++)
            if( dzero(arr1[i]-da) > 0 )
            {
                cout<<i+1<<" card(s)"<<endl;
                break;
            }
    }
}

# POJ 2262 Goldbach's Conjecture

http://poj.org/problem?id=2262 (opens new window)

恩... 這題我卡了很久，因為這題很要求執行時間，所以一直在修改優化，到最後終於成功 AC，我使用了建表法求質數，使用二分搜尋法加速質數表的搜尋，最後再用了 Cache 以後，才成功在時間內，AC 通關。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

int arr1[1000001];
int p[100000] = {2,3,5,7}, p_cnt =4;

bool is_prime( int ia )
{
    for(int i=0;i<p_cnt && p[i]*p[i]<=ia;i++)
        if( ia % p[i] == 0 )
            return false;
    return true;
}

void build_prime()
{
    for( int i=11, j=2; i<1000000; i+=j, j=6-j )
        if( is_prime(i) )
            p[ p_cnt++ ] = i;
}

int cmp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
bool bsearch_prime(int ia)
{
    return bsearch(&ia, p, p_cnt, sizeof (int), cmp)!=NULL;
}
int fa(int ia)
{
    if( arr1[ia] == -1 ) // No Cache
    {
        int ib = ia/2;
        bool ba = true;
        for(int i=0;i<p_cnt && p[i]<=ib;i++)
            if( bsearch_prime(ia-p[i]) )
            {
                ba = false;
                arr1[ia] = p[i];
                break;
            }
        if(ba) arr1[ia]=0;
    }
    return arr1[ia];
}

int main()
{
    memset(&arr1,-1,sizeof(arr1));
    build_prime();

    int ia;
    while(cin>>ia,ia)
    {
        int ib = fa(ia);
        if(ib==0) puts("Goldbach's conjecture is wrong.");
        else printf("%d = %d + %d\n", ia, ib, ia-ib);
    }
}

# POJ 3299 Humidex

http://poj.org/problem?id=3299 (opens new window)

這題... 我承認被那個很恐怖的數學式嚇到了，其實題目沒有很難，只要函式套對，方程式解對，這題就過了，我這題還學到經驗，用 float 才不會又白白送 WA ....

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

double toT( double d, double h )
{
    return h - 0.5555 * (( 6.11 * exp(5417.7530 * ( 1/273.16 - 1/(d+273.16)) )) - 10.0);
}
double toD( double h, double t )
{
    return 1/(1/273.16-log(((h - t)/0.5555+10.0)/6.11)/5417.7530)-273.16;
}
double toH( double d, double t )
{
    return t + 0.5555 * (( 6.11 * exp(5417.7530 * ( 1/273.16 - 1/(d+273.16)) )) - 10.0);
}

int main()
{
    double da, db, arr1[3];
    // T, D, H
    char ca, cb;
    while( cin>>ca )
    {
        if(ca=='E')break;
        cin>>da>>cb>>db;
        if( ca > cb )
        {
            char tmpc = ca;
            ca = cb;
            cb = tmpc;
            double tmpd = da;
            da = db;
            db = tmpd;
        }
        if( ca == 'D' && cb == 'H' )
        {
            printf("T %.1f D %.1f H %.1f\n",(float)toT(da,db),(float)da,(float)db);
        }
        if( ca == 'D' && cb == 'T' )
        {
            printf("T %.1f D %.1f H %.1f\n",(float)db,(float)da,(float)toH(da,db));
        }
        if( ca == 'H' && cb == 'T' )
        {
            printf("T %.1f D %.1f H %.1f\n",(float)db,(float)toD(da,db),(float)da);
        }
    }
}

# POJ 3518 Prime Gap

http://poj.org/problem?id=3518 (opens new window)

這題我也解頗久，因為我靈機一動，想用內建的 bsearch 改成可以直接搜尋區間，所以搞了一陣子，這次這樣玩，下次就有經驗了，哈哈。

另外，ptr[1] 其實會讀取到非法記憶體，雖然我目前是在最後面多加上一個值，但是這個只是治標不治本...

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;

int find_int;
int p[200000] = {2,3,5,7}, p_cnt =4;

bool is_prime( int ia )
{
    for(int i=0;i<p_cnt && p[i]*p[i]<=ia;i++)
        if( ia % p[i] == 0 )
            return false;
    return true;
}

void build_prime()
{
    for( int i=11, j=2; i<=1300000; i+=j, j=6-j )
        if( is_prime(i) )
            p[ p_cnt++ ] = i;
}

int cmp( const void * aa, const void * bb )
{
    int a = *(int*)aa;  // "aa" is always the value you are looking for.
    int *ptr = (int*)bb ;
    return ( a < ptr[0] ) ? -1 : ( a >= ptr[1] );
    // ptr[1] may cause "Run Time Error," Now I append a large data to solve the issue, But not good way...
}

int main()
{
    build_prime();
    while(cin>>find_int,find_int)
    {
        int *ptr = (int*)bsearch( &find_int, p, p_cnt-1, sizeof(int), cmp );
        if(ptr[0]==find_int)
            cout<<0<<endl;
        else cout<<ptr[1]-ptr[0]<<endl;
    }
}