2010-09-21 資訊能力競賽校內加賽
http://zerojudge.tw/ViewContest?contestid=382
==================== 第 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;
}
}
==================== 第 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; //測資間空一行
}
}
==================== 第 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";
}
} //中國餘數定理(韓信點兵)
==================== 第 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;
}
}
==================== 第 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 變負數，所以用~
}