ZeroJudge：2010-09-21 資訊能力競賽校內加賽


(d789)==================== 第 1 題 ====================
 
 
//920 - Sunny Mountains (by Snail)
#include <iostream>
#include <algorithm>    //for sort()
#include <cmath>        //for sqrt()
#include <iomanip>      //for setprecision()
using namespace std;
 
struct point {double x, y;} l[100];             //l(andscape)[]--地形
inline bool xlt (point a, point b) {return a.x < b.x;}
            //xlt (x less than)--x 小於(按x 由小到大排序)
int main () {
    int n, i, tc;
    double len, y, dy, dx;
    cout << fixed << setprecision(2);           //小數以下兩位
    cin >> tc;
    while (tc--) {
        cin >> n;
        for (i=0; i<n; i++) 
            cin >> l[i].x >> l[i].y;
        sort (l, l+n, xlt);
        len = y = 0;                            //y--目前高度
        for (i=n-2; i>=0; i--) {
            if (l[i].y > y) {
                dy = l[i].y - y;                //d(elta)y--高度差
                dx = (l[i].x - l[i+1].x) * dy / (l[i].y - l[i+1].y);
                len += sqrt (dx*dx + dy*dy);
                y = l[i].y;
            }
        }
        cout << len << endl;
    }
}
 
 

(d790)==================== 第 2 題 ====================
 
 
//729 - The Hamming Distance Problem (by Snail) 0.228s
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main () {
    int tc, n, h;
    string s;
    cin >> tc;
    while (tc--) {
        cin >> n >> h;
        s.assign (n-h, '0');                    //設定為n-h 個'0'
        s.append (h, '1');                      //加上h 個'1'
        do {
            cout << s << endl;                  //輸出所有的排列
        } while (next_permutation (s.begin(), s.end()));
        if (tc) cout << endl;                   //測資間空一行
    }
}
 
 
 
(d791)==================== 第 3 題 ====================
 
 
//756 - Biorhythms (by Snail) 0.024s
#include <iostream>
using namespace std;
 
int main () {                       // 5544 = 28*33* 6 = 23*241 + 1
    int tc=1, p, e, i, d;           //14421 = 23*33*19 = 28*515 + 1
    while (cin >> p, p>=0) {        // 1288 = 23*28* 2 = 33* 39 + 1
        cin >> e >> i >> d;
        d = (p*5544 + e*14421 + i*1288 - d + 21251) % 21252 + 1;
        cout << "Case " << tc++ << ": the next triple peak occurs in " << d << " days.\n";
    }
}   //中國餘數定理(韓信點兵)
 
 
 
(d792)==================== 第 4 題 ====================

 
//11463 - Commandos (by Snail)
#include <iostream>
using namespace std;
 
int main () {
    int m[101][101], i, j, k, N, R, u, v, s, d, t, tc, ntc;
    cin >> ntc;
    for (tc=1; tc<=ntc; tc++) {
        cin >> N >> R;
        for (i=0; i<N; i++) {                   //初始化
            for (j=0; j<N; j++) 
                m[i][j] = 101;                  //101--無法到達
            m[i][i] = 0;
        }
        for (i=0; i<R; i++) {
            cin >> u >> v;
            m[u][v] = m[v][u] = 1;
        }
        for (k=0; k<N; k++)                     //Floyd-Warshall
            for (i=0; i<N; i++)
                for (j=0; j<N; j++)
                    m[i][j] = min(m[i][j], m[i][k]+m[k][j]);
        cin >> s >> d;
        t = 0;
        for (k=0; k<N; k++)
            t = max(t, m[s][k]+m[k][d]);        //s→k→d 的最大值
        cout << "Case " << tc << ": " << t << endl;
    }
}
 
 
 
(d793)==================== 第 5 題 ====================

 
//929 - Number Maze (by Snail) 2.068s
#include <iostream>
#include <queue>
using namespace std;
 
int cost[1000][1000];           //原本儲存該格所讀入的數字
                                //拜訪過後則以負數表示從原點到該格的距離
struct cell {
    int r, c;
    cell (int r, int c) : r(r), c(c) {}         //constructor--建構器
} p(0,0);
 
struct gt {                                     //給優先佇列用的Functor
    bool operator() (cell a, cell b) {
        return cost[a.r][a.c] < cost[b.r][b.c]; //依該格的Cost 來排序
    }
};
 
int main () {
    int tc, n, m, i, j, d;
    int dr[4]={0,0,1,-1}, dc[4]={1,-1,0,0};     //d(elta)--四個方向的座標差
    cin >> tc;
    while (tc--) {
        cin >> n >> m;
        for (i=1; i<=n; i++)                    //輸入cost
            for (j=1; j<=m; j++)
                cin >> cost[i][j];              
        priority_queue<cell, vector<cell>, gt> q;//建構新的優先佇列
        q.push (cell(1, 1));                    //將原點推入佇列
        cost[1][1] = ~cost[1][1];               //標示為拜訪過
        while (p=q.top(), p.r!=n || p.c!=m) {   //BFS + Priority Queue
            q.pop();                            //從佇列取出
            for (d=0; d<4; d++) {               //試四個方向
                i = p.r + dr[d];
                j = p.c + dc[d];
                if (i<1 || i>n || j<1 || j>m || cost[i][j]<0)
                    continue;                   //超出邊界或拜訪過則跳過
                cost[i][j] = cost[p.r][p.c] - cost[i][j];
                q.push (cell (i, j));           //↑計算從原點到此的距離
            }
        }
        cout << ~cost[n][m] << endl;
    }       //用- 無法把0 變負數，所以用~
}