One more step ahead

很開心又跨出多一步，終於from C to C++了。

ACM: 121 - Pipe Fitters

這題是數學題，給矩形的長和寬，問最多可以擺幾個直徑為1單位的圓圈。只需考慮題目提供的grid或skew兩種排列方式。

值得一記的是，這題也算是我的第一個C++程式！

TIPS

測資 "0.9 10"，output是 "0 grid"

CODE

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

int skew(float width, float height);

int main()
{
  int p, count;
  char c, s[20];
  float side[2];
  
  p = count = 0;
  while( (c = getchar()) != EOF ){
    if( (c >= '0' && c <= '9') || c == '.' )
      s[p++] = c;
    else if( c == ' ' ){
      if( p > 0 ){
        s[p] = '\0';
        sscanf(s, "%f", &side[count++]);
        p = 0;
      }//if valid input
    }//else if c == '0'
    else if( c == '\n' ){
      if( p > 0 ){
        s[p] = '\0';
        sscanf(s, "%f", &side[count]);
        
        int max, mtype = 0, tmp;
        char type[2][5] = {"grid", "skew"};
        if( count == 0 ){
          max = (int)side[0] * (int)side[0];
          if( (tmp = skew(side[0], side[0])) > max ){
            max = tmp;
            mtype = 1;
          }
        }//if square
        else{
          max = (int)side[0] * (int)side[1];
          if( (tmp = skew(side[0], side[1])) > max ){
            max = tmp;
            mtype = 1;
          }
          if( (tmp = skew(side[1], side[0])) > max ){
            max = tmp;
            mtype = 1;
          }
        }//if rectangle
        
        cout << max << ' ' << type[mtype] << '\n';
        p = count = 0;
      }//if valid input
    }//else if c == '\n'
    else ;
  }//while input
  
  return 0;
}

int skew(float width, float height){  
  if( width < 1.0 || height < 1.0 )
    return 0;
  
  int dh, sum = 0;
  float th;//height of triangle
  
  th = sqrt(3)/2;
  dh = (int)( (height-1)/th );
  dh++;
  
  sum += (int)width * dh;
  if( (width - (int)width) < 0.5 )
    sum -= (int)( dh/2 );
    
  return sum;
}

烏龍派出所片尾曲

01〈スマイル〉

02〈いいことあるさ〉

03〈淑女の夢は万華鏡〉

04〈ブウェーのビヤビヤ〉

Ruby筆記

Ruby是一個跨平台的直譯式物件導向程式設計語言，訴求語法自然快捷，增進程式設計者的愉悅。
由Ruby寫成的Ruby on Rails(Rails/RoR)是open source的web application framework，由於能大幅減少網路應用服務的開發時間而受到歡迎。

安裝Ruby

http://www.ruby-lang.org/zh_TW/downloads/

IDE

RadRails: http://aptana.com/products/radrails
(跨平台的Ruby和Rails的IDE)

入門體驗

Try Ruby: 15分鐘的線上即時Ruby體驗
二十分鐘 Ruby 體驗: 官網的入門教學

書

Beginning Ruby: From Novice to Professional
Programming Ruby 1.9: The Pragmatic Programmers' Guide

中文線上資源

中文官方網站
Ruby Taiwan Community

幾本不錯的Ruby和Ruby On Rails電子書下載

My First Ruby Program

用Ruby試寫了一個找質數的程式，再加了簡單排版功能讓輸出比較好看。用到10000000只是想測試Ruby的陣列可以開到這麼大，而最能感受到Ruby快靚正的地方，應該就在 i.to_s.length 這句了，只要一行就能知道數字長度！

Max = 10000000
num = []
length = 0

(Max+1).times { |i| num << i }

2.upto(Max) do |i|
  if num[i] == i
    print i
    (i+i).step(Max, i) { |j| num[j] = 0 }
    
    #排版
    length += i.to_s.length
    if length > 40
      print "\n"
      length = 0
    else print " "
    end
  end
end

Software Engineering

軟體工程的目標在於在有限的時間、資源、人力下開發出達成預期目標的軟體。

Scope
From Wikipedia

1. Software requirements
2. Software design
3. Software development
4. Software testing
5. Software maintenance
6. Software configuration management
7. Software engineering management
8. Software development process
9. Software engineering tools
10. Software quality

書
轉自<前 100 名最佳軟體工程書籍>

1. Steve McConnell, Code Complete: A Practical Handbook of Software Construction
中文版：軟體建構之道

2. Elisabeth Freeman, etc., Head First Design Patterns
中文版：深入淺出設計模式

3. Steve McConnell, Rapid Development
中文版：軟體快速開發

4. Erich Gamma, Design Patterns: Elements of Reusable Object-Oriented Software
中文版：物件導向設計模式

5. Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code (2nd Edition)

6. Robert C. Martin, Agile Software Development: Principles, Patterns and Practices
中文版：敏捷軟體開發－原則、樣式及實務

7. Joel Spolsky, Joel on Software
中文版：約耳談軟體（網站）

8. Tom DeMarco, Timothy Lister, Peopleware: Productive Projects and Teams (2nd Edition)
中文版：Peopleware： 腦力密集產業的人才管理之道

9. Frederick P. Brooks, The Mythical Man-Month, Anniversary Edition (2nd Edition)
中文版：人月神話

10. Martin Fowler, Refactoring: Improving the Design of Existing Code
中文版：重構－改善既有程式的設計

ACM 20 題

寫到了第二個10題，讚。111 ~ 120因為有許多simulation題，比前10題相對輕鬆一點點，但還是學到了LIS、尤拉路徑、接觸到簡化的TSP(Travelling Salesman Problem)問題，也練習不少recurssive。加油，總有一天要寫出runtime 0.000的code！

ACM: 120 - Stacks of Flapjacks

這一題是給一疊大小不一的鬆餅，要用整個堆疊旋轉的方式，讓鬆餅從小到大排序。輸出結果不需是最佳解，只要能夠讓鬆餅排序就可以了。我覺得寫這題就是頭腦要清楚啊，因為input資料是從top開始，但要輸出的flip數字卻要從bottom算起！

CODE

#include <stdio.h>

#define MAX 30

int n, cake[MAX];

int makenum(int p, int *a);
void flipcake(int p);

int main(){
  int i, k, max, flag;
  int p, num[3];
  char c;

  n = p = flag = 0;
  while( (c = getchar()) != EOF ){
    if( c >= '0' && c <= '9' ){
      num[p++] = c - '0';
    }/*if '0'<= c <='9'*/
    else if( c == ' ' ){
      cake[n++] = makenum(p, num);
      p = 0;
    }/*if c == ' '*/
    else if( c == '\n' ){
      if( p > 0 )
        cake[n++] = makenum(p, num);
      
      if( n > 0 ){
        printf("%d", cake[0]);
        for(i=1; i<n; i++)
          printf(" %d", cake[i]);
        printf("\n");
        
        for(i=0; i<n; i++){
          max = 0;
          for(k=1; k<(n-i); k++){
            if( cake[k] > cake[max] )
              max = k;
          }/*k: find max pancake*/
          
          /*flip biggest pancake to top*/
          if( max>0 && max<(n-i-1) ){
            flipcake(max);
            if( flag == 1 ) printf(" ");
            else flag = 1;
            printf("%d", n-max);
          }
          /*flip biggest pancake to current bottom*/
          if( max<(n-i-1) ){
            flipcake(n-i-1);
            if( flag == 1 ) printf(" ");
            else flag = 1;
            printf("%d", i+1);
          }
        }/*j: sort the pancake*/
        
        if( flag == 1 ) printf(" ");
        printf("0\n");
      }/*if valid input*/
            
      n = p = flag = 0;
    }/*if c == '\n'*/
    else ;
  }/*while*/
  
  exit(0);
}

int makenum(int p, int *a){
  if( p == 3 )
    return 100;
  if( p == 2 )
    return (a[0]*10 + a[1]);
  return a[0];
}

void flipcake(int p){
  int i, j, tmp;
  
  for(i=0, j=p; i<=j; i++, j--){
    tmp = cake[i];
    cake[i] = cake[j];
    cake[j] = tmp;
  }
}

ACM: 119 - Greedy Gift Givers

也是很單純的simulation題，唯一要注意的是gift taker數量可能為0，要排除除以0的情況。

CODE

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

#define MAX_P 10
#define MAX_LEN 12

int n;
char names[MAX_P][MAX_LEN+1];

int findname(char *name);

int main(){
  int i, j, k, flag;
  int gift, taker, net[MAX_P];
  char s[MAX_LEN+1];
  
  flag = 0;
  while( scanf("%d", &n) != EOF ){
    if( flag == 1 )
      printf("\n");
    
    for(i=0; i<n; i++){
      scanf("%s", names[i]);
      net[i] = 0;
    }
    
    for(i=0; i<n; i++){
      scanf("%s %d %d", s, &gift, &taker);
      k = findname(s);
      
      if( taker != 0 ){
        net[k] -= gift;
        net[k] += (gift % taker);
        gift /= taker;
      }
      
      for(j=0; j<taker; j++){
        scanf("%s", s);
        k = findname(s);
        net[k] += gift;
      }/*j: give gift to taker*/
    }/*i*/
    
    for(i=0; i<n; i++)
      printf("%s %d\n", names[i], net[i]);
    
    flag = 1;
  }/*while more groups data*/
  
  exit(0);
}

int findname(char *s){
  int i;
  
  for(i=0; i<n; i++)
    if( strcmp(s, names[i]) == 0 )
      return i;
}

ACM: 118 - Mutant Flatworld Explorers

很單純的simulation題，就是照著規則去模擬。

CODE

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

#define MAX 50
#define MAX_LEN 100

int main(){
  int i, len;
  int mx, my, x, y, dir, t[MAX+1][MAX+1];
  int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
  char c, cmd[MAX_LEN], nesw[4]="NESW";
  
  scanf("%d %d", &mx, &my);
  while( scanf("%d %d %c", &x, &y, &c) != EOF ){
    scanf("%s", cmd);
    
    for(i=0; i<4; i++)
      if( c == nesw[i] )
        dir = i;
    
    len = strlen(cmd);
    for(i=0; i<len; i++){
      switch ( cmd[i] ){
        case 'L':
          dir--;
          break;
        case 'R':
          dir++;
          break;
        case 'F':
          while( dir < 0 )
            dir += 4;
          dir = dir % 4;
          if( (x+dx[dir])<0 || (x+dx[dir])>mx || (y+dy[dir])<0 || (y+dy[dir])>my ){
            if( t[x][y] != 1 ){
              t[x][y] = 1;
              i = len;
            }
          }
          else{
            x += dx[dir];
            y += dy[dir];
          }
          break;
        default: break;
      }/*switch*/
    }/*i*/
    
    while( dir < 0 )
      dir += 4;
    dir = dir % 4;
    printf("%d %d %c", x, y, nesw[dir]);
    if( i > len )
      printf(" LOST");
    printf("\n");
  }/*while*/
  
  exit(0);
}

ACM: 117 - The Postal Worker Rings Once

這一題是給許多條「街道」，找出將每條街至少走過一次，並回到原點的最短路徑，傳回路徑總長。可以視作一個graph，找出將每個邊至少走一次，並回到原點的最小路徑權重值。這題有以下背景知識：

Eulerian Circuit/Eulerian Path (尤拉路徑)

題目有兩個要點，將這題指向尤拉路徑:
1. In each postal route there will be a path between all intersections, i.e., the intersections are connected. (所有的道路可以接通，即是這是一個連通圖)
2. There will be at most two intersections with odd degree. All other intersections will have even degree, i.e., an even number of streets meeting at that intersection. (圖裡最多只有兩個點會有奇數個邊，其他點都會有偶數個邊)

Eulerian Circuit是判斷一個圖(無向圖)存不存在一個路徑，能從一點開始不經過重複的邊走完全圖，再回到原點。存在的條件如下:
圖形上每一個端點(vertex)皆有偶數個邊(degree為偶數)
因為若有一個端點有奇數個邊，勢必有一條路只能去不能回。

Eulerian Path(Eulerian Chain)則是一筆劃問題，找圖上是否存在一個路徑，從一點開始不經過重複的邊走完全圖，但不一定要回到原點。存在的條件如下:
圖形上最多只有兩個端點有奇數個邊，其餘端點皆有偶數個邊
而在有端點為奇數degree的情況下，Eulerian Path必定從奇數degree的端點開始，並且結束於奇數degree的端點。因為拿掉造成奇數degree的邊，圖形就可以回到原點，因此Eulerian Path可以想成是先走完一圈回到原點，再去特別走「多出來」的路徑，所以一定開始結束在奇數degree的端點。

因此這題是Eulerian Path的問題，當所有端點的degree皆為偶數時，最短路徑即是所有路徑的總和；而因為需要回到原點，當有奇數degree端點存在時，需再找出奇數degree端點之間的最小路徑，以回到原點。

 

Handshaking Lemma (握手定裡)

題目寫了"There will be at most two intersections with odd degree"，是「最多」兩個端點有奇數degree，但只有一個端點有奇數degree的情況是否可能存在呢？

從handshaking lemma可以了解這個情況是不可能的，因為好比兩人握手的時候，必然是兩個人都伸出手來，因此一個端點有奇數個邊，也必然有相應的點去連接那個邊，雙向計算的結果是，任何一個(無向)圖，擁有奇數個邊的端點數是偶數！

因此這個題目只有兩種情況：全部端點皆有偶數個邊，或只有兩個端點有奇數個邊。

 

寫出來Runtime 0.008，這題平均runtime超短的，要怎樣才能寫到0.000的境界呢！！我想也許在找shortest path的部分還可以再更快一點。

REFERENCES

117 - The Postal Worker Rings Once
Euler Circuit / Euler Path
Handshaking lemma

CODE

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

#define MAX 26
#define MAX_LEN 1000

int t[MAX][MAX], od[2];

void initialize(void);
int odegree(void);
int shortest(int a, int b);

int main(){
  int i, j;
  int sum, len;
  char s[MAX_LEN];
  
  sum = 0;
  initialize();
  while( scanf("%s", s) != EOF ){
    if( strcmp(s, "deadend") == 0 ){
      if( odegree() == 1 ){
        sum += shortest(od[0], od[1]);
        printf("%d\n", sum);
      }
      else
        printf("%d\n", sum);
      
      sum = 0;
      initialize();
    }/*output*/
    else{
      len = strlen(s);
      sum += len;
      t[ s[0]-'a' ][ s[len-1]-'a' ] = t[ s[len-1]-'a' ][ s[0]-'a' ] = len;
    }/*read data*/
  }/*while input data*/
  
  exit(0);
}

void initialize(void){
  int i, j;
  
  for(i=0; i<MAX; i++)
    for(j=0; j<MAX; j++)
      t[i][j] = 0;
  return;
}

int odegree(void){
  int i, j, k, d;
  
  d = 0;
  for(i=0; i<MAX; i++){
    k = 0;
    for(j=0; j<MAX; j++)
      if( t[i][j] > 0 )
        k++;
    if( k%2 == 1 )
      od[d++] = i;
  }
  
  if( d > 0 )
    return 1;
  return 0;
}

int shortest(int a, int b){
  int i, j, k, tmp;
  
  for(k=0; k<MAX; k++){
    for(i=0; i<MAX; i++){
      for(j=0; j<MAX; j++){
        if( t[i][k]*t[k][j] != 0 ){
          tmp = t[i][k] + t[k][j];
          if( tmp < t[i][j] || t[i][j] == 0 )
            t[i][j] = tmp;
        }
      }/*j*/
    }/*i*/
  }/*k*/
  
  return t[a][b];
}

ACM: 116 - Unidirectional TSP

這一題要找一個table從左走到右的最小和路徑。題目寫的很像可以用brute force，但用brute force會超過time limit。後來想到DP的方法，很開心。DP真是一種很神奇的概念。

寫出來後一直runtime error，看很久才發現是表格頭接尾，尾接頭的部分沒有用餘數的方法讓他自動接，造成有漏洞會陣列越界讀取。改成餘數的方法就解決了。果然越好的演算法越不會有奇怪的洞啊。

CODE

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

#define MAX_M 10
#define MAX_N 100

int main(){
  int i, j, k, min, tmp;
  int m, n, t[MAX_M][MAX_N], p[MAX_M][MAX_N];
  int mod[2] = {-1, 1};
  
  while( scanf("%d %d", &m, &n) == 2 ){
    for(i=0; i<m; i++)
      for(j=0; j<n; j++)
        scanf("%d", &t[i][j]);
    
    for(j=(n-2); j>=0; j--){
      for(i=0; i<m; i++){
        min = i;
        for(k=0; k<2; k++){
          tmp = (i+mod[k]+m) % m;
          if( t[tmp][j+1] < t[min][j+1] )
            min = tmp;
          else if( t[tmp][j+1] == t[min][j+1] )
            if( tmp < min )
              min = tmp;
        }/*k*/
        p[i][j] = min;
        t[i][j] += t[min][j+1];
      }/*i: row*/
    }/*j: col*/
    
    k = 0;
    for(i=1; i<m; i++)
      if( t[i][0] < t[k][0] )
        k = i;
    
    j = k;
    printf("%d", k+1);
    for(i=0; i<n-1; i++){
      printf(" %d", p[j][i]+1);
      j = p[j][i];
    }
    printf("\n%d\n", t[k][0]);
  }/*while input data*/ 
  
  exit(0);
}

ACM: 115 - Climbing Trees

這題寫出來也很感動，原因一是自己想到演算法解出了graph題！原因二是寫完以後de了超久的bug，明明自己測試output都正確，一直找不到runtime error的原因。看超久才發現原來是把一個變數放錯資料型別，改了以後總算AC了！

我用一個一維陣列存每個child的parent，再不斷trace。

CODE

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

#define MAX_NAMES 300
#define LEN_NAME 31

int tree[MAX_NAMES], maxn;
char name[MAX_NAMES][LEN_NAME+1];

int addname(char *s);
int findname(char *s);
void qry(int p, int q);
void showtrace(int t);
int isdescendent(int p, int q, char *s);
int iscousin(int p, int q);

int main(){
  int pk, qk;
  char p[LEN_NAME+1], q[LEN_NAME+1];
  
  maxn = 0;
  while( scanf("%s %s", p, q) == 2 ){
    if( strcmp(p, "no.child") == 0 )
      break;
    else{
      pk = addname(p);
      qk = addname(q);
      tree[pk] = qk;
    }
  }/*while parent-child pairs input*/
  
  /*read query*/
  while( scanf("%s %s", p, q) == 2 ){
    pk = findname(p);
    qk = findname(q);
    qry(pk, qk);
  }/*while query input*/
  
  exit(0);
}

int addname(char *s){
  int i;
  
  /*check if name exists*/
  for(i=0; i<maxn; i++)
    if( strcmp(s, name[i]) == 0 )
      return i;
  
  /*add new name*/
  strcpy(name[maxn], s);
  tree[maxn] = maxn;
  maxn++;
  
  return (maxn-1);
}

int findname(char *s){
  int i;
  
  for(i=0; i<maxn; i++)
    if( strcmp(s, name[i]) == 0 )
      return i;
  
  return -1;
}

void qry(int p, int q){ 
  if( p != -1 && q != -1 ){
    if( tree[p] == tree[q] ){
      printf("sibling\n");
      return;
    }
    if( isdescendent(p, q, "child") == 1 )
      return;
    if( isdescendent(q, p, "parent") == 1 )
      return;
    if( iscousin(p, q) == 1 )
      return;
  }/*if p, q != -1 */
  
  printf("no relation\n");
  return;
}

void showtrace(int t){
  int i;
  
  if( t == 0 )
    return;
  for(i=t; i>1; i--)
    printf("great ");
  printf("grand ");
}

int isdescendent(int p, int q, char *s){
  int tp, trace;
  
  tp = p;
  trace = 0;
  while( tree[tp] != tp ){
    tp = tree[tp];
    if( tp == q ){
      showtrace(trace);
      printf("%s\n", s);
      return 1;
    }
    trace++;
  }
  
  return 0;
}

int iscousin(int p, int q){
  int tp, tq, m, n;
  
  tp = p;
  tq = q;
  m = n = 0;
  while( tp != tree[tp] ){
    tp = tree[tp];
    while( tq != tree[tq] ){
      tq = tree[tq];
      if( tp == tq ){
        if( m > n ){
          printf("%d cousin ", n);
          printf("removed %d\n", (m-n));
        }
        else if( m == n )
          printf("%d cousin\n", m);
        else{
          printf("%d cousin ", m);
          printf("removed %d\n", (n-m));
        }
        return 1;
      }/*if common ancestor found*/
      n++;
    }/*while: trace q*/      
    tq = q;
    n = 0;
    m++;
  }/*while: trace p*/
  
  return 0;
}

ACM: 114 - Simulation Wizardry

相對輕鬆一點的有趣Simulation題目，就是要仔細把文字敘述看清楚，了解遊戲規則。我覺得最重要的應該是這句話:

"A ball ''hits'' an obstacle during a timestep when it would otherwise move on top of the bumper or wall grid point. A hit causes the ball to ``rebound'' by turning right (clockwise) 90 degrees, without ever moving on top of the obstacle and without changing position (only the direction changes as a result of a rebound)."

即是球撞到障礙物(牆或bumper)，都會留在原位不動，只改變下一步的方向。

其他就是照著遊戲規則simulation了。Runtime 0.044，Ranking進前100，開心開心。

CODE

#include <stdio.h>

#define MAX 50

#define GAME 0
#define VALUE 1
#define COST 2

#define RIGHT 0
#define UP 1
#define LEFT 2
#define DOWN 3

int m, n, g[3][MAX+1][MAX+1];

int pinball(int x, int y, int dir, int life);
void nextmove(int x, int y, int dir, int *arr);
int chgdir(int dir);

int main(){
  int i, j, t;
  int x, y, v1, v2, sum;
  
  scanf("%d %d", &m, &n);
  scanf("%d", &t); /*cost of hitting the wall*/
  
  /*initialize the pinball game & set walls*/
  for(i=1; i<=m; i++){
    g[GAME][1][i] = g[GAME][n][i] = 1;
    g[VALUE][1][i] = g[VALUE][n][i] = 0;
    g[COST][1][i] = g[COST][n][i] = t;
  }
  for(i=2; i<n; i++){
    for(j=1; j<=m; j++){
      if( j==1 || j==m ){
        g[GAME][i][j] = 1;
        g[VALUE][i][j] = 0;
        g[COST][i][j] = t;
      }
      else
        g[GAME][i][j] = g[VALUE][i][j] = g[COST][i][j] = 0;
    }/*j*/
  }/*i*/
  
  /*read bumpers*/
  scanf("%d", &t); /*number of bumpers*/
  for(i=0; i<t; i++){
    scanf("%d %d %d %d", &x, &y, &v1, &v2);
    
    g[GAME][x][y] = 1;
    g[VALUE][x][y] = v1;
    g[COST][x][y] = v2;
  }/*i*/
  
  /*read balls*/
  sum = t = 0;
  while( scanf("%d %d %d %d", &x, &y, &v1, &v2) != EOF ){
    t = pinball(x, y, v1, v2);
    sum += t;
    printf("%d\n", t);
  }/*while*/
  
  printf("%d\n", sum);
  exit(0);
}

int pinball(int x, int y, int dir, int life){
  int v, move[2];
  
  v = 0;
  while( life > 1 ){
    nextmove(x, y, dir, move);
    if( g[GAME][ move[0] ][ move[1] ] == 1 ){   
      life -= g[COST][ move[0] ][ move[1] ];
      v += g[VALUE][ move[0] ][ move[1] ];
      dir = chgdir(dir);
    }
    else{
      x = move[0];
      y = move[1];
    }
    
    life--;
  }/*while life > 1*/
  
  return v;
}

void nextmove(int x, int y, int dir, int *arr){
  arr[0] = x;
  arr[1] = y;
  
  switch (dir) {
    case RIGHT:
      arr[0]++;
      break;
    case UP:
      arr[1]++;
      break;
    case LEFT:
      arr[0]--;
      break;
    case DOWN:
      arr[1]--;
      break;
    default: break;
  }
}

int chgdir(int dir){
  if( dir == RIGHT )
    dir = DOWN;
  else
    dir--;
    
  return dir;
}

ACM: 111 – History Grading

這一題即是稍做變化的Longest Increasing Subsequence (LIS)問題，但要注意的是input資料。input資料是Event的Order:

Event: 1 2 3 4 5 6 7 8 9 10
Order: 3 1 2 4 9 5 10 6 8 7

即是Event by Order是: 2, 3, 1, 4, 6, 8, 10, 9, 5, 7。學生的回答也需要做如此的調整，比對出來才是正確的解答。原本沒有搞清楚，就想不通為什麼sample output跟自己算的答案不一樣了！

REFERENCE

Longest Increasing Subsequence

CODE

#include <stdio.h>

#define MAX 20

int main(){
  int i, j, t;
  int n, c[MAX+1], r[MAX+1], lis[MAX+1], max;
  
  scanf("%d", &n);
  
  /*Read Correct Order*/
  for(i=1; i<=n; i++)
    scanf("%d", &c[i]);
    
  /*Read Student Response*/
  while( scanf("%d", &t) != EOF){
    r[t] = 1;
    max = lis[1] = 1;
    for(i=2; i<=n; i++){
      scanf("%d", &t);
      r[t] = i;
      lis[i] = 1;
    }
    
    for(i=2; i<=n; i++){
      for(j=1; j<i; j++)
        if( c[ r[i] ] > c[ r[j] ] )
          if( lis[i] < (lis[j] + 1) )
            lis[i] = lis[j] + 1;
      
      if( max < lis[i] )
        max = lis[i];
    }/*i*/
       
    printf("%d\n", max);
  }/*while*/

  exit(0);
}

ACM: 112 - Tree Summing

這題要讀取以字串表現的binary tree，並找出是否有root-to-leaf path能產生指定的數字和。因為字串跟數字混在一起，如何處理字串可說是這題的罩門，但其實想清楚了這題S-expression的模式，字串處理起來就沒有想像中的複雜了。

因為原本卡在如何擷取字串，也是第一次寫bin tree的東西，所以寫出來很開心！再進了百大，超超興奮！

TIPS

1. 數字會有負數
2. 注意 0 () 的測資，output應該要是 no

CODE

#include <stdio.h>

int a, found;

int tree(int parent_sum);
int makenum(int *a, int n, int sign);

int main(){
  char c;
  
  while( scanf("%d", &a) != EOF ){
    while( (c = getchar()) !=EOF )
      if( c == '(' )
        break;
    
    found = 0;
    tree(0);
    if( found == 1 )
      printf("yes\n");
    else
      printf("no\n");
  }/*while*/
  
  exit(0);
}

/*return 0 if is empty node*/
int tree(int p){
  int sign, line[10], e, num;
  int flag, le, re;
  char c;
  
  flag = le = re = 1;
  sign = 1;
  e = num = 0;
  while( flag == 1 ){
    c = getchar();
    
    if( c == '-' )
      sign = -1;
    else if( c >= '0' && c <= '9' ){
      line[e] = c - '0';
      e++;
    }
    else if( c == '(' ){
      /*make number*/
      num = makenum(line, e, sign);
      
      /*left tree*/
      if ( tree( num+p ) == 0 )
        le = 0;

      /*read '('*/
      while( (c = getchar()) !=EOF )
        if( c == '(' )
          break;

      /*right tree*/
      if ( tree( num+p ) == 0 )
        re = 0;
    }
    else if( c == ')' )
      flag = 0;
    else ;
  }/*while flag is 1*/
  
  if( (le + re == 0) && ((num+p) == a) ){
    found = 1;
    return 1;
  }
  
  if( e == 0 )
    return 0;
    
  return 1;
}

int makenum(int *a, int n, int sign){
  int i, j, p, r;
  
  r = a[n-1];
  p = 1;
  for(i=0; i<(n-1); i++){
    for(j=1; j<=(n-i-1); j++)
      p *= 10;
    r += ( a[i] * p );
  }
  r *= sign;
  
  return r;
}

ACM 第一個10題

寫到了第一個10題！目前暫缺還找不到WA原因的107，不然就有100 - 110連號了！一步一腳印覺得學了很多，Floyd-Warshall、Kadane’s Algorithm、Graham Scan、Number Theory… 很有趣，也有嚐到一點小小的甜頭，繼續加油加油，要看到第二個10題。

ACM: 110 - Meta-Loopless Sorts

這題要寫出一個程式generate另一段程式碼。練習遞迴。Runtime 0.084，Ranking進入前100，超開心。

CODE

#include <stdio.h>

#define MAX 8

void showarr(int n, int *array);
void showspace(int sp);
void copyarr(int n, int *to, int *frm);
void insertarr(int n, int position, int end, int k, int *array);
void showmeta(int n, int pos, int *array);

int main(){
  int i, j;
  int m, n, a[MAX];
  
  scanf("%d", &m);
  
  for(i=0; i<m; i++){
    scanf("%d", &n);
    
    for(j=0; j<n; j++)
      a[j] = j;
    
    if( i > 0 )
      printf("\n");
        
    printf("program sort(input,output);\n");
    printf("var\n");
    showarr(n, a);
    printf(" : integer;\n");
    printf("begin\n");
    printf("  readln(");
    showarr(n, a);
    printf(");\n");
    
    if( n == 1 )
      printf("  writeln(a)\n");
    else
      showmeta(n, 1, a);
    printf("end.\n");
  }/*i: m inputs*/
  
  exit(0);
}

void showarr(int n, int *arr){
  int i;
  
  printf("%c", 'a'+arr[0]);
  for(i=1; i<n; i++)
    printf(",%c", 'a'+arr[i]);
}

void showspace(int sp){
  int i;
  
  for(i=1; i<=sp; i++)
    printf("  ");
}

void copyarr(int n, int *to, int *frm){
  int i;
  
  for(i=0; i<n; i++)
    to[i] = frm[i];
}

void insertarr(int n, int p, int e, int k, int *arr){
  int i;
  
  if( p == e )
    arr[p] = k;
  else{
    for(i=e; i>p; i--)
      arr[i] = arr[i-1];
    arr[p] = k;
  }
}

void showmeta(int n, int p, int *arr){
  int i, cpy[MAX];
  
  if( p == (n-1) ){
    for(i=p; i>=0; i--){
      copyarr(n, cpy, arr);
      insertarr(n, i, p, p, cpy);
      
      showspace(p);
      if( i == p )
        printf("if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      else if( i == 0 )
        printf("else\n");
      else
        printf("else if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      
      showspace(p+1);
      printf("writeln(");
      showarr(n, cpy);
      printf(")\n");
    }/*i*/
  }
  else{
    for(i=p; i>=0; i--){
      copyarr(n, cpy, arr);
      insertarr(n, i, p, p, cpy);
      
      showspace(p);
      if( i == p )
        printf("if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      else if( i == 0 )
        printf("else\n");
      else
        printf("else if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      
      showmeta(n, p+1, cpy);
    }/*i*/
  }
}

ACM: 109 – SCUD Buster

這題寫出來超想放煙火慶祝的！學了Convex Hull、Graham Scan。生平第一次覺得外積是這麼有用、了不起兼神奇的發明(發現?)啊。只需要乘法，就可以找出兩個向量的角度關係，因此可以避免用到除法的機器浮點數問題，這實在是太神奇了。

一次AC，感動。不過是超嫩的Runtime 0.016，我確定單在sorting就有很大的進步空間。但能夠把一組一組零散的座標，讓電腦連成一個圖形，再算出面積，相當有成就感。

REFERENCES

Graham Scan
Computational Geometry (ppt)

CODE

#include <stdio.h>

#define MAX_KINGDOM 20
#define MAX_VERTEX 100

int k, g[MAX_KINGDOM][MAX_VERTEX][2], gn[MAX_KINGDOM];

int findaim(int x, int y);
int isinside(int kingdom, int x, int y);
float findarea(int kingdom);

int main(){
  int i, j, s, tmp, min;
  int v, mx, my, at;
  int vx[MAX_VERTEX][2], attack[MAX_KINGDOM];
  float tot;
  
  /*Kingdom data*/
  v = 0;
  k = -1;
  while( scanf("%d", &v)!=EOF && v!=-1 ){
    k++;
    
    for(i=0; i<v; i++)
      scanf("%d %d", &vx[i][0], &vx[i][1]);
    
    /*find lowest point; if more than one point are the lowest, find the most left one*/
    min = 0;
    for(i=1; i<v; i++){
      if( vx[i][1] < vx[min][1] )
        min = i;
      else if( vx[i][1] == vx[min][1] )
        if( vx[i][0] < vx[min][0] )
          min = i;
    }
    if( min != 0 ){
      tmp = vx[min][0];
      vx[min][0] = vx[0][0];
      vx[0][0] = tmp;
      
      tmp = vx[min][1];
      vx[min][1] = vx[0][1];
      vx[0][1] = tmp;
    }
    
    /*sort rest points by counter clockwise with outer product*/
    for(i=1; i<v; i++){
      min = i;
      for(j=(i+1); j<v; j++){
        tmp = ( (vx[min][0]-vx[0][0])*(vx[j][1]-vx[0][1]) ) - ( (vx[j][0]-vx[0][0])*(vx[min][1]-vx[0][1]) );
        if( tmp < 0 )
          min = j;
      }/*j*/
      if( min != i ){
        tmp = vx[min][0];
        vx[min][0] = vx[i][0];
        vx[i][0] = tmp;
        
        tmp = vx[min][1];
        vx[min][1] = vx[i][1];
        vx[i][1] = tmp;
      }
    }/*i*/
    
    /*Graham Scan*/
    for(i=0; i<3; i++){
      g[k][i][0] = vx[i][0];
      g[k][i][1] = vx[i][1];
    }
    s = 2; /*s: current stack*/
    for(i; i<v; i++){
      tmp = ( (g[k][s][0]-g[k][s-1][0])*(vx[i][1]-g[k][s-1][1]) ) - ( (vx[i][0]-g[k][s-1][0])*(g[k][s][1]-g[k][s-1][1]) );
      if( tmp > 0 ){
        s++;
        g[k][s][0] = vx[i][0];
        g[k][s][1] = vx[i][1];
      }
      else if( tmp == 0 ){
        g[k][s][0] = vx[i][0];
        g[k][s][1] = vx[i][1];
      }
      else{
        s--;
        i--;
      }
    }
    s++;
    g[k][s][0] = g[k][0][0];
    g[k][s][1] = g[k][0][1];
    gn[k] = s;
    
  }/*while kingdom data input*/
  
  /*Missile attacks*/
  while( scanf("%d %d", &mx, &my) != EOF ){
    at = findaim(mx, my);
    if( at != -1 )
      attack[at] = 1;
  }/*while missile attacks input*/
  
  /*Output*/
  tot = 0.0;
  for(i=0; i<=k; i++)
    if( attack[i] == 1 )
      tot += findarea(i);
  printf("%.2f\n", tot);
  
  exit(0);
}

int findaim(int x, int y){
  int i;
  
  for(i=0; i<=k; i++){
    if( isinside(i, x, y) == 1 )
      return i;
  }/*i: scan through all kingdoms*/

  return -1;
}

int isinside(int kd, int x, int y){
  int i, tmp;
  
  if( y < g[kd][0][1] )
    return 0;
    
  for(i=0; i<gn[kd]; i++){
    tmp = ( ( g[kd][i+1][0]-g[kd][i][0] )*( y-g[kd][i][1] ) ) - ( ( x-g[kd][i][0] )*( g[kd][i+1][1]-g[kd][i][1] ) );
    if( tmp < 0 )
      return 0;
  }
  return 1;
}

float findarea(int kd){
  int i;
  float tmp, sum;
  
  sum = 0.0;
  for(i=1; i<=gn[kd]; i++){
    tmp = ( (g[kd][i-1][0])*(g[kd][i][1]) )-( (g[kd][i][0])*(g[kd][i-1][1]) );
    tmp /= 2;
    sum += tmp;
  }
  
  return sum;
}

ACM: 108 - Maximum Sum

這一題是給一個二維陣列，要找出有最大和的子陣列，傳回和的值。原本想不出更好的方法，只好用brute force搜尋所有子陣列 ，但預料之內的Time Limit Exceed(UVa好厲害啊)。查了資料，才知道解決之道在於 Kadane’s Algorithm。

Kadane’s Algorithm可以O(n)找到一維陣列的最大和子序列，Algorithmist上的pseudo code如下：

Kadane's Algorithm(arr[1..n])
begin
    (max, a, b) := (-INFINITY, 0, 0)
    curr := 0
    aa := 1
    for bb := 1 to n do
        curr := curr + arr[bb]
        if curr > max then
            (max, a, b) := (curr, aa, bb)
        endif

        if curr < 0 then
            curr := 0
            aa := bb + 1
        endif
    endfor

    return (max, a, b)
end

即是從陣列頭開始，不斷累加陣列元素值，同時不斷更新最大值，一旦累加和<0，就把累加變數歸零。因為一旦是負數，下一個元素值不管是正數或負數，都只會越加越小，所以不可能會是maximum了。如此，只需要讀過一次陣列就可以找到最大和子序列，真是神奇啊！

CODE

#include <stdio.h>

#define MAX 100

int main(){
  int i, j, k;
  int n, t[MAX][MAX], sum, max;
  
  scanf("%d", &n);
  for(i=0; i<n; i++)
    for(j=0; j<n; j++)
      scanf("%d", &t[i][j]);
  
  /*calculate vertical sum*/
  for(i=0; i<n; i++){
    for(j=1; j<n; j++){
      t[j][i] += t[j-1][i];
    }/*j: row*/
  }/*i: column*/
  
  max = t[0][0];
  /*find max sum*/
  for(i=0; i<n; i++){
    for(j=i; j<n; j++){
      sum = 0;
      for(k=0; k<n; k++){
        if( i==j || i==0 )
          sum += t[j][k];
        else
          sum += ( t[j][k] - t[i-1][k] );
        
        if( sum > max )
          max = sum;
        else if( sum < 0 )
          sum = 0;
      }
    }/*j: ending row*/
  }/*i: starting row*/
  
  printf("%d\n", max);
  exit(0);
}

ACM: 104 - Arbitrage

這一題我原先使用了brute force找出所有的換匯途徑，再檢查是否獲利，但這樣會超過time limit，有效率的解法必須使用Floyd-Warshall演算法。參考了Mat所轉錄的文章，研究了一陣，才了解Floyd-Warshall演算法一層層找最佳中繼點，最後再重建路徑回去的方法！但想通了真覺得Floyd-Warshall很美妙呢！

這題可說是找一個weighted graph從一點開始再回到一點的最短路徑，例如(0,.., 0)，先找第一個最佳中繼點(0, k1, 0)，紀錄下這個k1後，再找第二層中繼點(k1, k2, 0)，再紀錄下k2然後繼續…。最後，再從最後kn中繼點，重建回k1，便可以重建(0, k1, k2, .., kn, 0)的完整路徑了。

在我的code裡面，我一找到獲利的路徑後就跳出floyd-warshall。跟這題奮鬥多天的結果是Runtime 0.044，Rank 88！開心！

CODE

#include <stdio.h>

#define MAX 20

double profit[MAX][MAX][MAX];
int n, st, path[MAX][MAX][MAX];

int fw(void);

int main(){
  int i, j, s;
  int final[MAX];
  
  while( scanf("%d", &n) != EOF ){
    /*initialize profit array*/
    for(s=0; s<n; s++){
      for(i=0; i<n; i++){
        for(j=0; j<n; j++){
          profit[s][i][j] = 0.0;
        }/*j*/
      }/*i*/
    }/*s*/
    
    /*read rates table*/
    for(i=0; i<n; i++){
      for(j=0; j<n; j++){
        if( i==j )
          profit[0][i][j] = 1.0;
        else
          scanf("%lf", &profit[0][i][j]);
        path[0][i][j] = i;
      }
    }
    
    /*Floyd-Warshall*/
    if( (s = fw()) > 0 ){
      /*Re-construct path*/
      final[0] = j = st;
      i = s;
      for(i; i>0; i--){
        final[i] = path[i][st][j];
        j = final[i];
      }
      
      for(i=0; i<=s; i++){
        printf("%d ", final[i]+1);
      }
      printf("%d\n", st+1);
    }
    else{
      printf("no arbitrage sequence exists\n");
    }
  }/*while input data*/
  
  exit(0);
}

/*Return step when arbitrage exists; Return 0 when no arbitrage exists*/
int fw(void){
  int i, j, k, p;
  int s;
  double tmp;
  
  for(s=1; s<n; s++){
    for(k=0; k<n; k++){
      for(i=0; i<n; i++){
        for(j=0; j<n; j++){
          tmp = profit[s-1][i][k] * profit[0][k][j];
          if( tmp > profit[s][i][j] ){
            profit[s][i][j] = tmp;
            path[s][i][j] = k;
          }
        }/*j*/
      }/*i*/
    }/*k: intermediate node*/
    
    
    /*check if arbitrage exists*/
    for(p=0; p<n; p++){
      if( profit[s][p][p] > 1.01 ){
        st = p;
        return s;
      }
    }
  }/*s: step*/
  
  return 0;
}

106 - Fermat vs. Pythagoras

106 – Fermat vs. Pythagoras

這一題是給一個數字N：
1. 找出所有小於等於N的正整數中，互質的畢式組數(如: (3, 4, 5)是一組互質的畢式組數)數量。
2. 找出所有小於等於N的正整數中，不能構成畢式組數(不需是互質的畢式組數)的數字數量。

乍看之下只要用brute force找出所有的畢式數對即可，但由於N最大值是1,000,000，光要建立小於1,000,000的質數表就已經超過3秒鐘的Time Limit，所以一定要找其他方法。

參考Algorithmist，才發現使用畢式定理的通解，處理時間會大大的縮短。

X^2 + Y^2 = Z^2
( r^2 - s^2 )^2 + ( 2rs )^2 = ( r^2 + s^2 )^2

由於Z=(r^2+s^2)，要找出 Z<N 即是 (r^2+s^2)<N，因此r, s < N^(1/2)，搜尋數量縮減到根號N，也就是最大1000！

而互質且一奇一偶的(r, s)，可以產生所有互質的畢式組數。在乘上倍數後便可以找出其他非互質的畢式組數了。

TIPS

記錄數字是否為畢式組數的陣列要用char型別，int型別無法開到1,000,000

CODE

#include <stdio.h>

int p, prime[200];

void findprime(void);
int rp(int a, int b);

int main(){
  int i, j;
  int n, r, s, rsq, ssq, rpt;
  char num[1000002]="";
  
  /*Find all prime numbers between 1 and 1000*/
  findprime();
  
  while( scanf("%d", &n) != EOF ){
    rpt = 0;
    
    for(r=2; (rsq = r*r)<n; r++){
      for(s=1; s<r && (rsq+(ssq = s*s)<=n); s++){
        if( ((r%2 == 1) ^ (s%2 == 1)) && (rp(r,s) == 1) ){
          rpt++;
          
          /*time the triple pair*/
          for(i=1; (i*(rsq+ssq))<=n; i++)
            num[ i*(rsq - ssq) ] = num[ i*(2*r*s) ] = num[ i*(rsq + ssq) ] = 1;
        }/*(r, s) pair can generate relatively prime triple*/
      }/*s*/
    }/*r*/
    
    printf("%d ", rpt);
    j = 0;
    for(i=1; i<=n; i++){
      if( num[i] == 1 )
        num[i] = 0;
      else
        j++;
    }
    printf("%d\n", j);
  }/*while input data*/

  exit(0);
}

void findprime(void){
  int i, j, tmp[1001];
  
  for(i=2; i<1001; i++)
    tmp[i] = 1;
  
  p = 0;
  for(i=2; i<1001; i++){
    if( tmp[i] == 1 ){
      prime[p] = i;
      p++;
      
      for(j=(i+i); j<1001; j+=i)
        tmp[j] = 0;
    }
  }
}

int rp(int a, int b){
  int i;
  
  for(i=0; i<p && prime[i]<a ; i++)
    if( (a % prime[i] == 0) && (b % prime[i] == 0) )
      return 0;
  
  return 1;
}

ACM

從頭開始一題一題寫，目前為止11天寫了7題，很好，加油加油加油！

石田同學

我們這一家的石田同學，我行我素地太可愛了！冷面笑匠一流角色，但她自己卻不覺得有什麼好笑的，哈哈。以下幾集有石田：

『不可思議的孩子』
『石田的通心粉』
『石田不說謊』