ACM: 990 – Diving for Gold

也是0/1 Knapsack Problem，要輸出最後「背包」放入物品的總價值、物品數量，和輸出被放入的所有物品。

CODE

#include <iostream>

enum { CAPACITY = 1000, TREASURE = 30 };

int main(){

    int t, w, n, d[TREASURE], td[TREASURE], v[TREASURE];

    int i, j, mval[CAPACITY+1], items[CAPACITY+1];

    bool grab[TREASURE][CAPACITY+1], flag = 0;

    while( scanf("%d%d%d", &t, &w, &n) != EOF ){

        for(i=0; i<n; ++i){

            scanf("%d%d", &d[i], &v[i]);

            td[i] = d[i] * 3 * w;

        }

        memset(mval, 0, sizeof(mval));

        memset(items, 0, sizeof(items));

        memset(grab, 0, sizeof(grab));

        for(i=n; i>=0; --i){

            for(j=t; j>=td[i]; --j){

                if( mval[j-td[i]]+v[i] > mval[j] ){

                    mval[j] = mval[j-td[i]] + v[i];

                    items[j] = items[j-td[i]] + 1;

                    grab[i][j] = 1;

                }

            }//j

        }//i

        if( flag ) printf("\n");

        else flag = 1;

        printf("%d\n%d\n", mval[t], items[t]);

        for(i=0, j=t; i<n; ++i){

            if( grab[i][j] ){

                printf("%d %d\n", d[i], v[i]);

                j -= td[i];

            }

        }

    }

    return 0;

}

ACM: 562 – Dividing Coins

一直想學的背包問題，這題是0/1 Knapsack Problem。要把一堆面額不等的錢幣分成兩堆，使得兩堆錢幣總額的差距最小，輸出兩堆的差額。

在用Knapsack的做法之前還是先嘗試了一下greedy method，想看看在什麼情況greedy method會失敗。想法是：把錢幣由大排到小，從最大的開始，分給A、B，若A>B，就分給B，否則就分給A。這個做法在有些情況可以找到正確答案，但這個例子就不行：{50, 50, 49, 49, 48, 48, 2}。用這個做法會得到

A:{50, 49, 48, 2}
B:{50, 49, 48}

最小差距為2，但其實另一種分法就可以平分，A:{50, 49, 49}, B:{50, 48, 48, 2}，差距為0。

所以還是要用背包問題的DP做法，把錢幣盡量湊到總額的一半。

REFERENCES

良葛格學習筆記
演算法筆記

CODE

#include <iostream>

using namespace std;

enum { MAX_M = 100, MAX_VAL = 500, MAX_SUM = MAX_VAL*MAX_M };

int main(){

    int n, m, c[MAX_M];

    int i, j, t, sum, half, p[MAX_SUM+1] = {};

    scanf("%d", &n);

    for(; n>0; --n){

        scanf("%d", &m);

        sum = 0;

        for(i=0; i<m; ++i){

            scanf("%d", &c[i]);

            sum += c[i];

        }

        half = sum / 2;

        for(i=0; i<m; ++i) //all coins

            for(j=half; j>=c[i]; --j)

                p[j] = max(p[j], p[j-c[i]]+c[i]);

        cout << (((t = 2 * p[half] - sum) > 0) ? t : -1*t ) << endl;

        memset(p, 0, sizeof(p));

    }//n inputs

    return 0;

}

ACM: 138 – Street Numbers

這題寫出來超開心！

要找到n, k，使得1 + 2 + 3 + … + (k-1) = (k+1) + (k+2) + … + n。這題是no input，要傳回前10對n, k。題目已經給出前2對，第一對是(6, 8)，因為1+2+3+4+5 = 7 + 8 = 15。

我一開始的做法是，left從1開始累加，當累加(k-1)時，right就從(k+1)開始往上加，直到right>=left為止，若right==left，則找到一對(n, k)。這個方法可以找到正確答案，但實在跑太久，我讓他跑了一個小時，才找到第8對。

想著想著突然間豁然開朗，發現更有效率的方法。新的想法是，已知第一對(n, k)，即是知道一對相等的left, right，從這裡開始。k每加一，left加入(k-1)，因為要納入原本的分隔點(k-1)，而right則減掉k，因為要扣掉新的分隔點k。接著right再從n+1開始累加上去，直到right>=left為止，若right==left，則找到一對(n, k)。然後n, k, left, right的值都保留繼續累加使用。

沒想到這樣的做法竟然快了非常多，馬上答案就出來了！在看到第10對(n, k)的時候簡直太感動了。用這個做法就不用先把答案算出來然後上傳hard code了，Runtime是0.328。

說回這個問題，1 + 2 + 3 + … + (k-1) = (k+1) + (k+2) + … + n，看起來好像是蠻容易滿足的條件，但第10對(n, k)竟然已經是8位數字了！數字真神奇啊。另外，查了資料也發現這個問題可以用數論的Pell’s equation直接求解，但看Wolfram Mathworld和Wikipedia都看不太懂，希望有天可以了解。

 

CODE

#include <iostream>

int main(){

    unsigned long long k, n, count, left, right;

    printf("%10d%10d\n%10d%10d\n", 6, 8, 35, 49);

    for(k=36, n=50, count=0, left=595, right=595; count!=8; ++k){

        left += (k - 1);

        right -= k;

        for(; right<left; ++n)

            right += n;

        if( left == right ){

            printf("%10llu%10llu\n", k, n-1);

            ++count;

        }

    }

    return 0;

}

ACM: 136 – Ugly Numbers

Ugly number 是質因數只有2或3或5的數字。這題要找出第1500個ugly number。

原本只是單純的一個數字一個數字檢查質因數，直到找到第1500個ugly number為止，但雖然可以找到正確答案，卻會花很久的時間。查了一下討論區，才恍然大悟可以直接用2,3,5去生成倍數，也想出來了生成的方法，真開心！

 

CODE

#include <iostream>

#include <climits>

int main(){

    int u[1500], p[3] = {2, 3, 5};

    int i, j, k, t;

    u[0] = 1;

    for(i=1; i<1500; ++i){

        u[i] = INT_MAX;

        for(j=0; j<3; ++j){

            for(k=0; (t = u[k] * p[j]) <= u[i-1]; ++k);

            if( t < u[i] )

                u[i] = t;

        }//j: 2,3,5

    }//i: i'th ugly number

    printf("The 1500'th ugly number is %d.\n", u[i-1]);

    return 0;

}

 

CODE (naive and slow version)

#include <iostream>

using namespace std;

bool otherprime(int n){

  while( n%2 == 0 )

    n /= 2;

  while( n%3 == 0 )

    n /= 3;

  while( n%5 == 0 )

    n /= 5;

  if( n == 1 )

    return false;

  return true;

}

int main() {

  int n = 1; //start from 2

  int count = 1; //the 1st ugly number is 1

  while( count < 1500 ){ 

    ++n;

    if( (n % 2 == 0) || (n % 3 == 0) || (n % 5 == 0) ){

      if( !otherprime(n) )

        ++count;

    }

  }

  cout << n << endl;

  return 0;

}

ACM: 135 – No Rectangles

要找到規律，畫一個k=6的解，就可以找到規律了。不過雖然找到了規律，卻還不知道為什麼規律是這樣。

CODE

#include <iostream>

int main(){
  int k, n;
  int block; //k-1
  bool flag = false;
  
  while( scanf("%d", &k) != EOF ) {
    if( flag )
      printf("\n");
    else
      flag = true;
      
    n = k * k - k + 1;
    block = k - 1;
    
    int i, j, t, p;
    int line = 0; //count total lines printed
    int starter = 1; //first number of every line
    int count = 2;
    
    //print first k lines
    for(i=0; i<k; ++i, ++line){
      printf("%d", starter);
      for(j=1; j<k; ++j, ++count){
        printf(" %d", count);
      }//j: k marks
      printf("\n");
    }//i: line
    
    //print (k-1) blocks, each block has (k-1) lines
    for(i=0; i<block && line<=n; ++i){
      ++starter;
      for(j=0; j<block; ++j, ++line){
        printf("%d", starter);
        p = j;
        printf(" %d", k+p+1);
        for(t=(k+block+1); t<n; t+=block){
          p = (p + i) % block;
          printf(" %d", t+p);
        }//t: go to starting point of each block
        printf("\n");
      }//j: lines
    }//i: blocks of lines
  }
  
  return 0;
}

Java Project: Reversi

黑白棋遊戲。可兩人對戰或一個玩家跟電腦玩，也可以看電腦跟電腦瞬間對決。目前寫的AI只是單純選擇可以翻轉最多對手棋子的下一步，因此還蠻容易贏這個AI的。

功能：

1. 提供兩個玩家、一個玩家和一個電腦玩家、或兩個電腦玩家進行黑白棋遊戲。
2. 遊戲進行時，當滑鼠移動到可以下子的格點，顯示圖示提示。
3. 遊戲進行時，即時顯示目前下子方(黑子或白子)和目前分數。
4. 可隨時改變玩家設定(選擇由電腦或人下棋)，設定將在下一次輪到該顏色棋子下棋時執行。
5. 可隨時開啟新遊戲。

執行畫面：

檔案下載：

Reversi_v_1_0.rar (155 kb)

Java Project: SimplePad

簡單的記事本軟體！

功能：
1. 可以選單或快速鍵執行開啟、儲存純文字檔案。
2. 開啟檔案或儲存檔案後，檔名顯示在標題列。
3. 可以選單或快速鍵執行剪下、複製、貼上功能。
4. 可開啟或關閉自動換行(Line Wrap)。
5. 可以讀寫中文！

執行畫面：

檔案下載：

SimplePad.rar (148 kb)